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