# How to solve those recurrences with generating functions?

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.

-
So 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? –  Marc van Leeuwen Oct 27 '12 at 9:03

## 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*}

-
I think the very last equation has the wrong sign for the $1-\sqrt3$ term. –  joriki Oct 27 '12 at 12:52
ah, yes my fault. –  user46090 Oct 27 '12 at 12:58

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}

-
What's wrong with using partial fractions to obtain the closed form? –  wj32 Oct 27 '12 at 8:20
@wj32: Nothing, the only thing that was wrong was me :-) I've added the partial fraction expansion and the explicit forms. –  joriki Oct 27 '12 at 12:49