¿Cómo resolver esas recurrencias con funciones generadoras?

Question

Sé que podemos resolver estas recurrencias con funciones generadoras, pero no estoy familiarizado con eso, así que espero que haya una solución detallada para el problema.

Answer 1

Dejemos que $q(x)=\sum_nQ_nx^n$ y $r(x)=\sum_nR_nx^n$ . Entonces, sumando la recurrencia de la izquierda de $1$ a $\infty$ da

$$ q=2xr+\frac x{1-x}\;, $$

y sumando la recurrencia de la derecha de $1$ a $\infty$ da

$$ r=q+xq+\frac x{1-x}\;. $$

Sustituyendo la segunda ecuación en la primera se obtiene

$$ q=2xq+2x^2q+\frac{2x^2}{1-x}+\frac x{1-x}\;, $$

con solución

$$ q=\frac{x(1+2x)}{(1-x)(1-2x-2x^2)}\;. $$

Entonces, sustituyendo esto en la segunda ecuación se obtiene

$$ r=\frac{x(1+x)}{(1-x)(1-2x-2x^2)}\;. $$

Como bien ha señalado wj32, podemos utilizar fracciones parciales para obtener los coeficientes de forma cerrada. Factorización $1-2x-2x^2$ como $(1-(1-\sqrt3)x)(1-(1+\sqrt3)x)$ obtenemos

$$ q=x\left(\frac{1-2/\sqrt3}{1-(1-\sqrt3)x}+\frac{1+2/\sqrt3}{1-(1+\sqrt3)x}-\frac1{1-x}\right) $$

y por lo tanto

$$ \begin{align} Q_n&=\left(1-\frac2{\sqrt3}\right)(1-\sqrt3)^{n-1}+\left(1+\frac2{\sqrt3}\right)(1+\sqrt3)^{n-1}-1 \\ &=\frac{(1+\sqrt3)^{n+1}-(1-\sqrt3)^{n+1}}{2\sqrt3}-1 \end{align} $$

para $n\ge1$ y

$$ \begin{align} R_n&=Q_n+Q_{n-1}+1\\ &=\frac{(2+\sqrt3)(1+\sqrt3)^n-(2-\sqrt3)(1-\sqrt3)^n}{2\sqrt3}-1\\ &=\frac{(1+\sqrt3)^{n+2}-(1-\sqrt3)^{n+2}}{4\sqrt3}-1\;. \end{align} $$

Answer 2

Este es el problema 1.10 del libro de Knuth "Concrete Mathematics".

Doy una solución para $Q_n$ utilizando las notaciones de Knuth.

Primero tenemos $$Q_n=\left\{\begin{array}{ll}0,&n\leq0\\1,&n=1\\2Q_{n-1}+2Q_{n-2}+3,&n\geq2\end{array}\right.$$ Así que, en general, tenemos $$Q_n=2Q_{n-1}+2Q_{n-2}+3[n\geq2]+[n=1]$$

Supongamos que $q(z)$ es la función generadora, reescribiendo la recurrencia, tenemos $$q(z)=2z\cdot q(z)+2z^2\cdot q(z)+\frac{3z^2}{z-1}+z$$

Resolver para $q(z)$ obtenemos $$q(z)=\frac{u(z)}{v(z)}=\frac{z+2z^2}{(1-z)(1-2z-2z^2)}=\frac{z+2z^2}{(1-z)[1-(1+\sqrt{3})z][1-(1-\sqrt{3})z]}$$

Según el teorema (7.29) de "Matemáticas concretas", si tenemos $q(z)=u(z)/v(z)$ y $v(z)=\rho_0(1-\rho_1z)\ldots(1-\rho_lz)$ y $\rho_1,\ldots,\rho_l$ son distinto y $u(z)$ es un polunomio de grado inferior a $l$ entonces $$Q_n=[z^n]q(z)=a_1\rho_1^k+\cdots+a_l\rho_l^k$$ donde $$a_k=\frac{-\rho_ku(1/\rho_k)}{\frac{d}{dz}v(1/\rho_k)}$$

Aplicando este teorema, obtenemos $\rho_1=1$ , $\rho_2=1+\sqrt{3}$ , $\rho_3=1-\sqrt{3}$ y $a_1=-1$ , $a_2=\frac{3+\sqrt{3}}{6}$ , $a_3=\frac{3-\sqrt{3}}{6}$

Así que tenemos \begin{eqnarray*} Q_n &=& a_1\rho_1^k+a_2\rho_2^k+a_3\rho_3^k\\ &=&\frac{3+\sqrt{3}}{6}(1+\sqrt{3})^n+\frac{3-\sqrt{3}}{6}(1-\sqrt{3})^n-1\\ &=&\frac{(1+\sqrt{3})^{n+1}-(1-\sqrt{3})^{n+1}}{2\sqrt{3}}-1 \end{eqnarray*}