# can we use generating functions to solve the recurrence relation $a_n = a_{n-1} + a_{n-2}$, $a_1=1$, $a_2=2$?

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

-
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 math.stackexchange.com/questions/45111/… –  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.

-

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.

-

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).

-