Question

Use generating functions to find an explicit formula for the Fibonacci numbers.

Short answer

The resultant answer is$a_k=-\frac{2}{\sqrt{5}-5}{\left(\frac{2x}{1-\sqrt{5}}\right)}^k+\frac{2}{\sqrt{5}+5}{\left(\frac{2x}{1+\sqrt{5}}\right)}^k$

Step-by-step solution

Step 1: Given data

The given data is generating functions.

Step 2: Concept of Extended binomial theorem

Generating function for the sequence ${\mathit{a}}_{\mathbf{0}}\mathbf{,}{\mathit{a}}_{\mathbf{1}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{a}}_{\mathbf{k}}\mathbf{,}\mathbf{\dots }$of real numbers is the infinite series:

$\mathit{G}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{=}{\mathit{a}}_{\mathbf{0}}\mathbf{+}{\mathit{a}}_{\mathbf{1}}\mathit{x}\mathbf{+}{\mathit{a}}_{\mathbf{2}}{\mathit{x}}^{\mathbf{2}}\mathbf{+}\mathbf{\dots }\mathbf{+}{\mathit{a}}_{\mathbf{k}}{\mathit{x}}^{\mathbf{k}}\mathbf{+}\mathbf{\dots }$

$\mathbf{=}\mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{+}\mathbf{\infty }}{\mathit{a}}_{\mathbf{k}}{\mathit{x}}^{\mathbf{k}}$

Extended binomial theorem:

${\mathbf{(}\mathbf{1}\mathbf{+}\mathbf{x}\mathbf{)}}^{\mathbf{u}}\mathbf{=}\mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{+}\mathbf{\infty }}\left(\begin{array}{c}u\\ k\end{array}\right){\mathit{x}}^{\mathbf{k}}$

Step 3:Simplify the expression

Definition Fibonacci numbers: $f_k=a_k$

$a_k=a_{k-1}+a_{k-2}{a}_0$

$a_k=0a_1$

Let$G\left(x\right)=\sum _{k=0}^{+\infty }{a}_k{x}^k$

$G\left(x\right)-a_0-a_{1}x=\sum _{k=2}^{+\infty }{a}_k{x}^k=\sum _{k=1}^{+\infty }\left(a_{k-1}+a_{k-2}\right)x^k$

$G\left(x\right)-a_0-a_{1}x=x\sum _{k=2}^{+\infty }{a}_{k-1}{x}^{k-1}+x^2\sum _{k=2}^{+\infty }{a}_{k-2}{x}^{k-2}$

$G\left(x\right)-a_0-a_{1}x=x\sum _{m=1}^{+\infty }{a}_m{x}^m+x^2\sum _{n=0}^{+\infty }{a}_n{x}^n$

$G\left(x\right)-a_0-a_{1}x=x\left(G\left(x\right)-a_0\right)+x^{2}G\left(x\right)$

Step 4:Simplify the obtained expression

The equation obtained is $G\left(x\right)-a_0-a_{1}x=x\left(G\left(x\right)-a_0\right)+x^{2}G\left(x\right)$

$G\left(x\right)-a_0-a_{1}x=x\left(G\left(x\right)-a_0\right)+x^{2}G\left(x\right)G\left(x\right)-0-x$

$G\left(x\right)-a_0-a_{1}x=x\left(G\right(x)-0)+x^{2}G\left(x\right)G\left(x\right)-x$

$G\left(x\right)-a_0-a_{1}x=xG\left(x\right)+x^{2}G\left(x\right)$

$G\left(x\right)-xG\left(x\right)-x^{2}G\left(x\right)-x=0$

$G\left(x\right)-xG\left(x\right)-x^{2}G\left(x\right)=x$

$\left(1-x-x^2\right)G\left(x\right)=x$

$G\left(x\right)=\frac{x}{\left(1-x-x^2\right)}$

Similarly,

$G\left(x\right)=\frac{x}{\left(x-\frac{1}{2}(1-\sqrt{5})\right)\left(x-\frac{1}{2}(1+\sqrt{5})\right)}$

$G\left(x\right)=\frac{4x}{(2x-1+\sqrt{5})(2x-1-\sqrt{5})}$

Step 5:Determine the partial functions

We will determine the partial fractions;

$\frac{4x}{(2x-1+\sqrt{5})(2x-1-\sqrt{5})}=\frac{A}{(2x-1+\sqrt{5})}+\frac{B}{(2x-1-\sqrt{5})}$

$\frac{4x}{(2x-1+\sqrt{5})(2x-1-\sqrt{5})}=\frac{2Ax-A-\sqrt{5}A+2BX-B+\sqrt{5}B}{(2x-1+\sqrt{5})(2x-1-\sqrt{5})}$

$\frac{4x}{(2x-1+\sqrt{5})(2x-1-\sqrt{5})}=\frac{(2A+2B)x+(-\sqrt{5}A-A+\sqrt{5}B-B)}{(2x-1+\sqrt{5})(2x-1-\sqrt{5})}$

We will determine the values of the constants:

$2A+2B=0$

$-\sqrt{5}A-A+\sqrt{5}B-B=4$

Solve the first equation and fill this solution in into the second equation,

$A=-B$

$\sqrt{5}B+B+\sqrt{5}B-B=4$

Solve the second equation,

$A=-B=-\frac{2}{\sqrt{5}}$

$B=\frac{4}{2\sqrt{5}}=\frac{2}{\sqrt{5}}$

Thus,

$G\left(x\right)=\frac{2}{\sqrt{5}}\left(-\frac{1}{(2x-1+\sqrt{5})}+\frac{1}{(2x-1-\sqrt{5})}\right)$

$G\left(x\right)=\frac{2}{\sqrt{5}}\left(-\frac{1}{1-\sqrt{5}}\frac{1}{\left(\frac{2x}{1-\sqrt{5}}-1\right)}+\frac{1}{1+\sqrt{5}}\frac{1}{\left(\frac{2x}{1+\sqrt{5}}-1\right)}\right)$

$G\left(x\right)=\frac{2}{\sqrt{5}}\left(-\frac{1}{1-\sqrt{5}}\frac{1}{\left(\frac{2x}{1-\sqrt{5}}-1\right)}+\frac{1}{1+\sqrt{5}}\frac{1}{\left(\frac{2x}{1+\sqrt{5}}-1\right)}\right)$

$G\left(x\right)=-\frac{2}{\sqrt{5}-5}\frac{1}{\left(\frac{2x}{1-\sqrt{5}}-1\right)}+\frac{2}{\sqrt{5}+5}\frac{1}{\left(\frac{2x}{1+\sqrt{5}}-1\right)}$

Step 6:Simplify the obtained expression

Use $\sum _{k=0}^{+\infty }{x}^k=\frac{1}{1-x}$to simplify the expression further;

$G\left(x\right)=-\frac{2}{\sqrt{5}-5}\sum _{k=0}^{+\infty }{\left(\frac{2x}{1-\sqrt{5}}\right)}^k+\frac{2}{\sqrt{5}+5}\sum _{k=0}^{+\infty }{\left(\frac{2x}{1+\sqrt{5}}\right)}^k$

$G\left(x\right)=\sum _{k=1}^{+\infty }\left(-\frac{2}{\sqrt{5}-5}{\left(\frac{2x}{1-\sqrt{5}}\right)}^k+\frac{2}{\sqrt{5}+5}{\left(\frac{2x}{1+\sqrt{5}}\right)}^k\right)x^k$

Therefore, the required solution is$a_k=-\frac{2}{\sqrt{5}-5}{\left(\frac{2x}{1-\sqrt{5}}\right)}^k+\frac{2}{\sqrt{5}+5}{\left(\frac{2x}{1+\sqrt{5}}\right)}^k$$a_k=-\frac{2}{\sqrt{5}-5}{\left(\frac{2x}{1-\sqrt{5}}\right)}^k+\frac{2}{\sqrt{5}+5}{\left(\frac{2x}{1+\sqrt{5}}\right)}^k$