I know we can solve these recurrences with generating functions, but I'm not familiar with that, so I hope there is a detailed solution for the problem.
How to solve those recurrences with generating functions?
-
0So what are _you_ asking for? The cited question asks to establish the relations, not to solve them. Are you asking to solve them nonetheless? Should the answer use generating functions, or should it avoid them because you are not familiar? – 2012-10-27
2 Answers
This the problem 1.10 in Knuth's book "Concrete Mathematics".
I give a solution for $Q_n$ using Knuth's notations.
First we have $Q_n=\left\{\begin{array}{ll}0,&n\leq0\\1,&n=1\\2Q_{n-1}+2Q_{n-2}+3,&n\geq2\end{array}\right.$ So in general, we have $Q_n=2Q_{n-1}+2Q_{n-2}+3[n\geq2]+[n=1]$
Suppose $q(z)$ is the generating function, re-writing the recurrence, we have $q(z)=2z\cdot q(z)+2z^2\cdot q(z)+\frac{3z^2}{z-1}+z$
Solving for $q(z)$, we obtain $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]}$
According to Theorem (7.29) in "Concrete Mathematics", if we have $q(z)=u(z)/v(z)$, and $v(z)=\rho_0(1-\rho_1z)\ldots(1-\rho_lz)$, and $\rho_1,\ldots,\rho_l$ are distinct, and $u(z)$ is a polunomial of degree less than $l$, then $Q_n=[z^n]q(z)=a_1\rho_1^k+\cdots+a_l\rho_l^k$ where $a_k=\frac{-\rho_ku(1/\rho_k)}{\frac{d}{dz}v(1/\rho_k)}$
Applying this theorem, we get $\rho_1=1$, $\rho_2=1+\sqrt{3}$, $\rho_3=1-\sqrt{3}$ and $a_1=-1$, $a_2=\frac{3+\sqrt{3}}{6}$, $a_3=\frac{3-\sqrt{3}}{6}$
So we have \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*}
-
0ah, yes my fault. – 2012-10-27
Let $q(x)=\sum_nQ_nx^n$ and $r(x)=\sum_nR_nx^n$. Then summing the left-hand recurrence from $1$ to $\infty$ gives
$ q=2xr+\frac x{1-x}\;, $
and summing the right-hand recurrence from $1$ to $\infty$ gives
$ r=q+xq+\frac x{1-x}\;. $
Substituting the second equation into the first yields
$ q=2xq+2x^2q+\frac{2x^2}{1-x}+\frac x{1-x}\;, $
with solution
$ q=\frac{x(1+2x)}{(1-x)(1-2x-2x^2)}\;. $
Then substituting that into the second equation yields
$ r=\frac{x(1+x)}{(1-x)(1-2x-2x^2)}\;. $
As wj32 rightly pointed out, we can use partial fractions to obtain the coefficients in closed form. Factoring $1-2x-2x^2$ as $(1-(1-\sqrt3)x)(1-(1+\sqrt3)x)$ we get
$ q=x\left(\frac{1-2/\sqrt3}{1-(1-\sqrt3)x}+\frac{1+2/\sqrt3}{1-(1+\sqrt3)x}-\frac1{1-x}\right) $
and thus
$ \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} $
for $n\ge1$, and
$ \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} $
-
0@wj32: Nothing, the only thing that was wrong was me :-) I've added the partial fraction expansion and the explicit forms. – 2012-10-27