Sum of Sequence of Fibonacci Numbers
Jump to navigation
Jump to search
Theorem
Let $F_n$ denote the $n$th Fibonacci number.
Then:
- $\ds \forall n \in \Z_{\ge 0}: \sum_{j \mathop = 0}^n F_j = F_{n + 2} - 1$
Proof
Proof by induction:
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
- $\ds \sum_{j \mathop = 0}^n F_j = F_{n + 2} - 1$
$\map P 0$ is the case:
\(\ds F_0\) | \(=\) | \(\ds 0\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1 - 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds F_2 - 1\) |
which is seen to hold.
Basis for the Induction
$\map P 1$ is the case:
\(\ds F_1\) | \(=\) | \(\ds 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 2 - 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds F_3 - 1\) |
which is seen to hold.
This is our basis for the induction.
Induction Hypothesis
Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
- $\ds \sum_{j \mathop = 1}^k F_j = F_{k + 2} - 1$
Then we need to show:
- $\ds \sum_{j \mathop = 1}^{k + 1} F_j = F_{k + 3} - 1$
Induction Step
This is our induction step:
\(\ds \sum_{j \mathop = 1}^{k + 1} F_j\) | \(=\) | \(\ds \sum_{j \mathop = 1}^k F_j + F_{k + 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds F_{k + 2} - 1 + F_{k + 1}\) | Induction Hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds F_{k + 3} - 1\) | Definition of Fibonacci Number |
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\ds \forall n \in \Z_{\ge 0}: \sum_{j \mathop = 0}^n F_j = F_{n + 2} - 1$
$\blacksquare$
Also presented as
This can also be seen presented as:
- $\ds \sum_{j \mathop = 1}^n F_j = F_{n + 2} - 1$
which is seen to be equivalent to the result given, as $F_0 = 0$.
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {1-1}$ Principle of Mathematical Induction: Exercise $7$
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $5$
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers: Exercise $20$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $5$