General Fibonacci Number in terms of Fibonacci Numbers

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $r$ and $s$ be numbers, usually integers but not necessarily so limited.

Let $\sequence {a_n}$ be the general Fibonacci sequence :

$a_n = \begin{cases} r & : n = 0 \\ s & : n = 1 \\ a_{n - 2} + a_{n - 1} & : n > 1 \end{cases}$

Then $a_n$ can be expressed in Fibonacci numbers as:

$a_n = F_{n - 1} r + F_n s$


Proof

The proof proceeds by induction.

For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:

$a_n = F_{n - 1} r + F_n s$


Basis for the Induction

$\map P 0$ is the case:

\(\ds F_{-1} r + F_0 s\) \(=\) \(\ds \paren {-1}^0 F_1 r + F_0 s\) Fibonacci Number with Negative Index
\(\ds \) \(=\) \(\ds 1 \times r + 0 \times s\) Definition of Fibonacci Number: $F_0 = 0, F_1 = 1$
\(\ds \) \(=\) \(\ds r\)
\(\ds \) \(=\) \(\ds a_0\) Definition of General Fibonacci Sequence

Thus $\map P 0$ is seen to hold.


$\map P 1$ is the case:

\(\ds F_0 r + F_1 s\) \(=\) \(\ds 0 \times r + 1 \times s\) Definition of Fibonacci Number: $F_0 = 0, F_1 = 1$
\(\ds \) \(=\) \(\ds s\)
\(\ds \) \(=\) \(\ds a_1\) Definition of General Fibonacci Sequence

Thus $\map P 1$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $\map P {k - 1}$ and $\map P k$ are true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.


So this is the induction hypothesis:

$a_{k - 1} = F_{k - 2} r + F_{k - 1} s$
$a_k = F_{k - 1} r + F_k s$


from which it is to be shown that:

$a_{k + 1} = F_k r + F_{k + 1} s$


Induction Step

This is the induction step:


\(\ds a_{k + 1}\) \(=\) \(\ds a_{k - 1} + a_k\)
\(\ds \) \(=\) \(\ds \paren {F_{k - 2} r + F_{k - 1} s} + \paren {F_{k - 1} r + F_k s}\) Induction Hypothesis
\(\ds \) \(=\) \(\ds \paren {F_{k - 2} + F_{k - 1} } r + \paren {F_{k - 1} + F_k} s\)
\(\ds \) \(=\) \(\ds F_k r + F_{k + 1} s\) Definition of Fibonacci Number

So $\map P {k - 1} \land \map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\forall n \in \Z_{\ge 0}: a_n = F_{n - 1} r + F_n s$

$\blacksquare$


Sources