Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have this question.

Can we use generating functions to solve the recurrence relation $$\begin{align*} a_1 &= 1,\\ a_2 &= 2,\\ a_n &= a_{n-1} + a_{n-2} \end{align*}$$ Thanks

share|cite|improve this question
Of course, this is just the Fibonacci sequence with the first few entries (depending on one's exact favorite definition) cut off. Which kind of "solution" are you envisaging here? Something like the $\frac{\phi^n-(\phi-1)^n}{\sqrt 5}$ formula? – Henning Makholm Feb 8 '12 at 22:50
No, he wants a function whose Taylor expansion contains the terms of the sequence. – dot dot Feb 8 '12 at 22:51
A harder problem of this type is solved in detail at… – Gerry Myerson Feb 8 '12 at 23:44

Yes, it is possible to use generating functions to solve the recurrence

$$\begin{align*} a_1 &= 1,\\ a_2 &= 2,\\ a_n &= a_{n-1} + a_{n-2} \end{align*}$$

to get a closed form for $a_n$.

My preferred way is first to back the recurrence up to get $a_0=a_2-a_1=1$ and rewrite the recurrence proper as $$a_n=a_{n-1}+a_{n-2}+[n=0]\;,\tag{1}$$ where the last term uses the Iverson bracket: $(1)$ holds for all $n$ if one makes the blanket assumption that $a_n=0$ for $n<0$.

Now multiply $(1)$ by $x^n$ and sum over $n\ge 0$:

$$\begin{align*} \sum_na_nx^n&=\sum_na_{n-1}x^n+\sum_na_{n-2}x^n+\sum_n[n=0]x^n\\ &=x\sum_na_{n-1}x^{n-1}+x^2\sum_na_{n-2}x^{n-2}+x^0\\ &=x\sum_na_nx^n+x^2\sum_na_nx^n+1\;. \end{align*}$$

Letting $g(x)=\sum_na_nx^n$ be the generating function, we have $g(x)=xg(x)+x^2g(x)+1$ and hence $$g(x)=\frac1{1-x-x^2}=\frac1{(1-\varphi x)(1-\hat\varphi x)}\;,$$ where $\varphi=\frac12(1+\sqrt5)$ and $\hat\varphi=\frac12(1-\sqrt5)$. Decomposing this into partial fractions yields $$\begin{align*}g(x)&=\frac1{5+\sqrt5}\left(\frac{3+\sqrt5}{1-\varphi x}+\frac2{1-\hat\varphi x}\right)\\ &=\frac1{5+\sqrt5}\left((3+\sqrt5)\sum_n\varphi^nx^n+2\sum_n\hat\varphi^nx^n\right)\\ &=\frac1{5+\sqrt5}\sum_n\Big((3+\sqrt5)\varphi^n+2\hat\varphi^n\Big)x^n\;, \end{align*}$$ and we can now equate coefficients to see that

$$\begin{align*}a_n&=\frac1{5+\sqrt5}\Big((3+\sqrt5)\varphi^n+2\hat\varphi^n\Big)\\ &=\frac{5+\sqrt5}{10}\varphi^n+\frac{5-\sqrt5}{10}\hat\varphi^n\\ &=\frac{\sqrt5+1}{2\sqrt5}\varphi^n+\frac{\sqrt5-1}{2\sqrt5}\hat\varphi^n\\ &=\frac1{\sqrt5}\left(\varphi^{n+1}-\hat\varphi^{n+1}\right)\;. \end{align*}$$

This is of course the expected solution, since it’s clear from the original recurrence that $a_n=F_{n+1}$, the $(n+1)$-st Fibonacci number in the usual indexing.

share|cite|improve this answer

You are looking for an infinite sum. You should do $$F(x)=[\sum_{k=0}^{\infty}( A(k)x^k )]$$ Then $$[\sum_{k=0}^{\infty}( A(k)x^k )] = [\sum_{k=0}^{\infty}( (A(k-1)+A(k-2))x^k )]$$ and express this last expression in terms of $F(x)$. Then you will get the generating function. In this case, you could do $$1+2+[\sum_{k=3}^{\infty}(A(k)x^k)]=F(x)$$

For example, the coefficients of the Taylor expansion of $x/(1-x-x^2)$ are the terms of Fibonacci sequence.

share|cite|improve this answer

Short and sweet. Define $A(z) = \sum_{n \ge 0} a_n z^n$, and write: $$ a_{n + 2} = a_{n + 1} + a_n \qquad a_1 = 1 a_2 = 2 $$ From here we infer $a_0 = 1$.

Multiply the recurrence by $z^n$, add for $n \ge 0$ to get: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = \frac{A(Z) - a_0}{z} + A(z) $$ Thus: $$ A(z) = \frac{1}{1 - z - z^2} $$ Define: $$ \begin{align*} \phi &= \frac{1 + \sqrt{5}}{2} \\ \hat{\phi} &= \frac{1 - \sqrt{5}}{2} \end{align*} $$ so that $1 - z - z^2 = (1 - \phi z) (1 - \hat{\phi} z)$. By partial fractions: $$ A(z) = \frac{\phi}{\sqrt{5}} \cdot \frac{1}{1 - \phi z} + \frac{\hat{\phi}}{\sqrt{5}} \cdot \frac{1}{1 - \hat{\phi} z} $$ Two geometric series: $$ a_n = \frac{1}{\sqrt{5}} \left( \phi^{n + 1} + \hat{\phi}^{n + 1} \right) $$ (Really, after seeing the recurrence you'd know that $a_n = F_{n + 1}$, Fibonacci numbers, and be done).

share|cite|improve this answer

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.