Fibonacci general term: How do I mend this broken derivation?

Question

I am working on a derivation of the general term for the Fibonacci Sequence. Here's where I want to be:

$$F(n)=\frac{1}{\sqrt5}(\phi^n-\overline{\phi}^n)$$

Here, $F(n)$ is the $n^\text{th}$ term, $\phi = \frac{1}{2}(1+\sqrt5)$ and $\overline{\phi}=\frac{1}{2}(1-\sqrt5)$

My generating function and power series for $|x|\lt 1$:

$$f(x)=\frac{x}{1-x-x^2}=x+x^2+2x^3+3x^4+5x^5+\cdots$$

By factoring the quadratic and rewriting as partial fractions, I'm left with:

$$f(x)=\tfrac{1}{\sqrt5}\cdot x\left(\frac{1}{x+\phi}-\frac{1}{x+\overline{\phi}}\right)$$

I think I go off track with the binomial expansion. Here's what I have:

$$f(x)=\frac{1}{\sqrt5}\cdot x\left[(x+\phi)^{-1}-(x+\overline{\phi})^{-1}\right]=\frac{1}{\sqrt5}\cdot x \sum_{k=0}^{\infty}\binom{-1}{k} x^{-1-k}(\phi^k-\overline{\phi}^k)$$ The $x$ before the $\sum$ means the $x$ term is $x^{-k}$. Also $\binom{-1}{k}=(-1)^k$. This leaves us with: $$f(x)=\frac{1}{\sqrt5}\left(-\frac{\phi-\overline{\phi}}{x}+\frac{\phi^2-\overline{\phi}^2}{x^2}-\frac{\phi^3-\overline{\phi}^3}{x^3}+\frac{\phi^4-\overline{\phi}^4}{x^4}-...\right)$$

This is almost right, but every other term is negative. My result:

$$F(n)=\frac{(-1)^n}{\sqrt5}\left(\phi^n-\overline{\phi}^n\right)$$

The intrusive $(-1)^n$ leads me to suspect my handling of the coefficient, $\binom{-1}{k}$.

I'd appreciate help troubleshooting this. Thanks.

Answer 1

Your approach seems overly complicated to me since it is not necessary to use the binomial series.

If you must use a generating function approach, let $$f(z) = \sum_{n=0}^\infty F_n z^n.$$ Note that $F_0 = 0$ according to your formula. Then since $$F_n = F_{n-1} + F_{n-2},$$ we have $$\begin{align} f(z) &= 0 z^0 + 1 z^1 + z^2 \sum_{n=0}^\infty F_{n+2} z^n \\ &= z + z \sum_{n=0}^\infty F_{n+1} z^{n+1} + z^2 \sum_{n=0}^\infty F_n z^n \\ &= z + z f(z) + z^2 f(z). \end{align}$$ Then $$f(z) = \frac{z}{1-z-z^2},$$ as you obtained. However, from here, we proceed differently. We observe the factorization $$1 - z - z^2 = (1 - \phi z)(1 - \bar \phi z).$$ Therefore, $$f(z) = \frac{1}{\sqrt{5}} \left( \frac{1}{1 - \phi z} - \frac{1}{1 - \bar \phi z}\right).$$ Then we simply use the formula for a geometric series: $$f(z) = \frac{1}{\sqrt{5}} \left( \sum_{n=0}^\infty (\phi z)^n - (\bar \phi z)^n \right).$$ Equating coefficients gives $$F_n = \frac{1}{\sqrt{5}} \left( \phi^n - \bar \phi^n\right),$$ as claimed.

---

If you do not need to use generating functions, then the approach I would use is as follows. Observe $\phi + \bar \phi = 1$, and $\phi \bar \phi = -1$. Then consider the identity $$(a^n - b^n)(a + b) = (a^{n+1} - b^{n+1}) - (ab)(a^{n-1} - b^{n-1}),$$ which is true for any $a, b$. Then substituting $a = \phi$, $b = \bar \phi$, we obtain $$(\phi^n - \bar \phi^n)(1) = (\phi^{n+1} - \bar \phi^{n+1}) - (-1)(\phi^{n-1} - \bar\phi^{n-1}).$$ If we let $G_n = \phi^n - \bar \phi^n$ and rearranging terms, we get $$G_{n+1} = G_n + G_{n-1}.$$ Since $G_0 = 0$ and $G_1 = \sqrt{5}$, it follows that $F_n = G_n/\sqrt{5}$ for all $n$ and we are done.

Answer 2

$\dfrac1{x+\phi}=\dfrac1{\phi\left(1+\dfrac x\phi\right)}=\dfrac1\phi\left(1-\dfrac x\phi + \dfrac{x^2}{\phi^2}-\dfrac{x^3}{\phi^3}+\cdots\right)$

so $f(x)=\dfrac x{\sqrt5}\left(\dfrac1{x+\phi}-\dfrac1{x+\overline\phi}\right)$

$=\dfrac x{\sqrt5}\left(\dfrac1\phi-\dfrac1{\overline{\phi}}\right)-\dfrac{x^2}{\sqrt5}\left(\dfrac1{\phi^2}-\dfrac1{\overline\phi^2}\right)+\dfrac{x^3}{\sqrt5}\left(\dfrac1{\phi^3}-\dfrac1{\overline\phi^3}\right)-\dfrac{x^4}{\sqrt5}\left(\dfrac1{\phi^4}-\dfrac1{\overline\phi^4}\right)\cdots$,

whence $F_n=(-1)^{n+1}\dfrac1{\sqrt5}\left(\dfrac1{\phi^n}-\dfrac1{\overline{\phi}^n}\right)$.

Also, $\dfrac1{\phi^n}=(-1)^n\overline{\phi}^n$, so $F_n=\dfrac1{\sqrt5}\left(\phi^n-\overline{\phi}^n\right)$.