Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

enter image description here

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.

share|improve this question
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 2

up vote 2 down vote accepted

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

share|improve this answer
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} $$

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.