Second Order Fibonacci Number in terms of Fibonacci Numbers

From ProofWiki
Jump to navigation Jump to search

Theorem

The second order Fibonacci number $\FF_n$ can be expressed in terms of Fibonacci numbers as:

$\dfrac {3 n + 3} 5 F_n - \dfrac n 5 F_{n + 1}$


Proof

Let $\map \GG z = \ds \sum_{n \mathop \ge 0} \mathop F_n z^n$ be a generating function for $\FF_n$.

Then we have:

\(\ds \paren {1 - z - z^2} \map \GG z\) \(=\) \(\ds \paren {\FF_0 + \FF_1 z + \FF_2 z^2 + \FF_3 z^3 + \FF_4 z^4 + \cdots}\)
\(\ds \) \(\) \(\, \ds - \, \) \(\ds \paren {\FF_0 z + \FF_1 z^2 + \FF_2 z^3 + \FF_3 z^4 + \FF_4 z^5 + \cdots}\)
\(\ds \) \(\) \(\, \ds - \, \) \(\ds \paren {\FF_0 z^2 + \FF_1 z^3 + \FF_2 z^4 + \FF_3 z^5 + \FF_4 z^6 + \cdots}\)
\(\ds \) \(=\) \(\ds \FF_0 + \paren {\FF_1 - \FF_0} z + \paren {\FF_2 - \FF_1 - \FF_0} z^2 + \paren {\FF_3 - \FF_2 - \FF_1} z^3 + \cdots\)
\(\ds \) \(=\) \(\ds \FF_0 + \paren {\FF_1 - \FF_0} z + F_0 z^2 + F_1 z^3 + \cdots\) Definition of Second Order Fibonacci Number: $\FF_n - \FF_{n - 1} - \FF_{n - 2} = F_{n - 2}$
\(\ds \) \(=\) \(\ds z + z^2 \sum_{k \mathop \ge 0} F_k z^k\) Definition of Second Order Fibonacci Number: $\FF_0 = 0$, $\FF_1 = 1$
\(\ds \) \(=\) \(\ds z + z^2 \map G z\) where $\map G z$ is a generating function for the Fibonacci numbers


Thus:

\(\ds \map \GG z\) \(=\) \(\ds \dfrac {z + z^2 \map G z} {1 - z - z^2}\)
\(\ds \) \(=\) \(\ds \dfrac z {1 - z - z^2} + \dfrac z {1 - z - z^2} z \map G z\)
\(\ds \) \(=\) \(\ds \map G z + z \paren {\map G z}^2\) Generating Function for Fibonacci Numbers: $\map G z = \dfrac z {1 - z - z^2}$


Then from Summation over k to n of Product of kth with n-kth Fibonacci Numbers, the coefficient of $z^n$ in $\paren {\map G z}^2$ is:

$\dfrac {\paren {n - 1} F_n + 2n F_{n - 1} } 5$

Thus the coefficient of $z^{n + 1}$ in $z \paren {\map G z}^2$ is likewise:

$\dfrac {\paren {n - 1} F_n + 2n F_{n - 1} } 5$

and so the coefficient of $z^n$ in $\map G z + z \paren {\map G z}^2$ is:

$F_n + \dfrac {\paren {n - 2} F_{n - 1} + 2 \paren {n - 1} F_{n - 2} } 5$

Hence:

\(\ds F_n + \dfrac {\paren {n - 2} F_{n - 1} + 2 \paren {n - 1} F_{n - 2} } 5\) \(=\) \(\ds F_n + \dfrac {\paren {2 n - 2} F_{n - 1} - n F_{n - 1} + \paren {2 n - 2} F_{n - 2} } 5\)
\(\ds \) \(=\) \(\ds F_n + \dfrac {\paren {2 n - 2} F_n - n F_{n - 1} } 5\) Definition of Fibonacci Number
\(\ds \) \(=\) \(\ds \dfrac {5 F_n + \paren {2 n - 2} F_n - n F_{n - 1} } 5\) common denominator
\(\ds \) \(=\) \(\ds \dfrac {\paren {2 n + 3} F_n - n F_{n - 1} } 5\)
\(\ds \) \(=\) \(\ds \dfrac {\paren {2 n + 3} F_n + n F_n - n F_n - n F_{n - 1} } 5\)
\(\ds \) \(=\) \(\ds \dfrac {\paren {2 n + 3} F_n + n F_n - n \paren {F_n + F_{n - 1} } } 5\)
\(\ds \) \(=\) \(\ds \dfrac {\paren {2 n + 3} F_n + n F_n - n F_{n + 1} } 5\) Definition of Fibonacci Number
\(\ds \) \(=\) \(\ds \dfrac {\paren {3 n + 3} F_n} 5 - \dfrac {n F_{n + 1} } 5\) simplifying

$\blacksquare$


Sources