Sum of nth Fibonacci Number over nth Power of 2
Theorem
- $\ds \sum_{n \mathop = 0}^\infty \frac {F_n} {2^n} = 2$
where $F_n$ is the $n$th Fibonacci number.
Proof 1
Let us define a sample space which satisfies the Kolmogorov Axioms such that it is the set of all combinations of flipping a fair coin until you receive two heads in a row.
Let $X_n$ be the event of some outcome from flipping $n$ fair coins in a row, then $\Pr(X_n) = \dfrac 1 {2^n}$.
In the sample space defined above, we now demonstrate that for a given number of flips $n$, there are exactly $F_{n - 1}$ outcomes contained in the sample space.
Illustration
- $\begin{array}{c|c|cc}
n & \map f n & \text {Sample Space}: \Omega \\ \hline
1 & 0 & \text {impossible} \\
2 & 1 & HH \\
3 & 1 & THH \\
4 & 2 & (HTHH), (TTHH) \\
5 & 3 & (THTHH), (HTTHH), (TTTHH) \\
6 & 5 & (HTHTHH), (TTHTHH), (THTTHH), (HTTTHH), (TTTTHH) \\
\hline
\cdots & \cdots & \cdots \\
\hline
n & F_{n - 1} & \cdots \\
\hline
\end{array}$
Reviewing the illustration above, for any given value of $n$:
For ALL combinations displayed in row $n$ (that is $\map f n$) , we can place a $T$ in front and that new combination would exist in the sample space for $\paren {n + 1}$.
For example:
- $\paren {HTHH}, \paren {TTHH} \to \paren {THTHH}, \paren {TTTHH}$
However, we also see that for only those combinations starting with a $T$ (that is $\map f {n - 1}$), can we place an $H$ in front and that new combination will also exist in the sample space for $\paren {n + 1}$.
For example:
- $\paren {TTHH} \to \paren {HTTHH}$
Therefore, we have:
| \(\ds \map f n\) | \(=\) | \(\ds F_{n - 1}\) | ||||||||||||
| \(\ds \map f {n + 1}\) | \(=\) | \(\ds \map f n + \map f {n - 1}\) | $\map f n$ is adding a $T$ in front and $\map f {n - 1}$ is adding an $H$ in front | |||||||||||
| \(\ds \) | \(=\) | \(\ds F_{n - 1} + F_{n - 2}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds F_n\) |
The sum of the probabilities of outcomes in a sample space is one by the second Kolmogorov Axiom.
| \((\text {II})\) | $:$ | \(\ds \map \Pr \Omega \) | \(\ds = \) | \(\ds 1 \) |
Hence:
| \(\ds \sum_{n \mathop = 1}^\infty \frac {F_{n - 1} } {2^n}\) | \(=\) | \(\ds 1\) | $2$nd Kolmogorov Axiom | |||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \sum_{n \mathop = 0}^\infty \frac {F_n} {2^{n + 1} }\) | \(=\) | \(\ds 1\) | reindexing the sum | ||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \sum_{n \mathop = 0}^\infty \frac {F_n} {2^n}\) | \(=\) | \(\ds 2\) | multiplying both sides by $2$ |
$\blacksquare$
Proof 2
From the Euler-Binet Formula, we have:
- $F_n = \dfrac {\phi^n - \paren {1 - \phi}^n} {\sqrt 5}$
Therefore:
| \(\ds \sum_{n \mathop = 0}^\infty \frac{F_n} {2^n}\) | \(=\) | \(\ds \sum_{n \mathop = 0}^\infty \dfrac {\phi^n - \paren {1 - \phi}^n} {\sqrt 5 \times 2^n}\) | Euler-Binet Formula | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{n \mathop = 0}^\infty \dfrac {\paren {\dfrac {1 + \sqrt 5} 2}^n - \paren {1 - \paren {\dfrac {1 + \sqrt 5} 2 } }^n} {\sqrt 5 \times 2^n}\) | Definition of Golden Mean | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{n \mathop = 0}^\infty \dfrac {\paren {\dfrac {1 + \sqrt 5} 2}^n - \paren {\dfrac {1 - \sqrt 5} 2 }^n} {\sqrt 5 \times 2^n}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \dfrac 1 {\sqrt 5} \sum_{n \mathop = 0}^\infty \paren {\dfrac {1 + \sqrt 5} 4}^n - \dfrac 1 {\sqrt 5} \sum_{n \mathop = 0}^\infty \paren {\dfrac {1 - \sqrt 5} 4}^n\) | Product of Powers and $2^2 = 4$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \dfrac {1 + \sqrt 5 } 4} } - \dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \dfrac {1 - \sqrt 5} 4} }\) | Sum of Infinite Geometric Sequence | |||||||||||
| \(\ds \) | \(=\) | \(\ds \dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \dfrac {1 + \sqrt 5} 4} } \times \dfrac 4 4 - \dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \dfrac {1 - \sqrt 5} 4} } \times \dfrac 4 4\) | multiplying top and bottom by $4$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \dfrac 4 {\sqrt 5} \paren {\dfrac 1 {3 - \sqrt 5} } - \dfrac 4 {\sqrt 5} \paren {\dfrac 1 {3 + \sqrt 5} }\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \dfrac 4 {\sqrt 5} \paren {\dfrac 1 {3 - \sqrt 5} } \times \paren {\dfrac {3 + \sqrt 5} {3 + \sqrt 5} } - \dfrac 4 {\sqrt 5} \paren {\dfrac 1 {3 + \sqrt 5} } \times \paren {\dfrac {3 - \sqrt 5} {3 - \sqrt 5} }\) | multiplying top and bottom by $\paren {3 + \sqrt 5}$ and by $\paren {3 - \sqrt 5}$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \dfrac 4 {\sqrt 5} \paren {\dfrac {3 + \sqrt 5} 4} - \dfrac 4 {\sqrt 5} \paren {\dfrac {3 - \sqrt 5} 4}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {\dfrac {3 + \sqrt 5} {\sqrt 5} } - \paren {\dfrac {3 - \sqrt 5} {\sqrt 5} }\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 2\) |
$\blacksquare$
Proof 3
| \(\ds \sum_{k \mathop = 0}^{\infty} F_k z^k\) | \(=\) | \(\ds \dfrac z {1 - z - z^2}\) | Generating Function for Fibonacci Numbers | |||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \sum_{k \mathop = 0}^{\infty} \frac {F_k} {2^k}\) | \(=\) | \(\ds \dfrac {\dfrac 1 2} {1 - \dfrac 1 2 - \paren {\dfrac 1 2}^2}\) | substituting $z = \dfrac 1 2$ | ||||||||||
| \(\ds \) | \(=\) | \(\ds \dfrac {1 / 2} {1 / 4}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 2\) |
$\blacksquare$
Proof 4
First, let:
- $S = \ds \sum_{n \mathop = 0}^\infty \frac {F_n} {2^n}$
Some sundry results:
| \(\ds \sum_{k \mathop = 0}^n F_k\) | \(=\) | \(\ds F_{n + 2} - 1\) | Sum of Sequence of Fibonacci Numbers | |||||||||||
| \(\text {(1)}: \quad\) | \(\ds \leadsto \ \ \) | \(\ds F_{n + 2}\) | \(=\) | \(\ds \paren {\sum_{k \mathop = 0}^n F_k} + 1\) |
and:
| \(\ds \sum_{n \mathop = 0}^\infty \frac 1 {2^n}\) | \(=\) | \(\ds \frac 1 {1 - \frac 1 2}\) | Sum of Infinite Geometric Sequence | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 {1 / 2}\) | ||||||||||||
| \(\text {(2)}: \quad\) | \(\ds \) | \(=\) | \(\ds 2\) |
We have:
| \(\ds S\) | \(=\) | \(\ds \sum_{n \mathop = 0}^\infty \frac {F_n} {2^n}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \frac {F_0} {2^0} + \frac {F_1} {2^1} + \sum_{n \mathop = 2}^\infty \frac {F_n} {2^n}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 0 1 + \frac 1 2 + \sum_{n \mathop = 2}^\infty \frac {F_n} {2^n}\) | Definition of Fibonacci Numbers: $F_0 = 0$ and $F_1 = 1$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 2 + \sum_{n \mathop = 2}^\infty \frac {F_n} {2^n}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 2 + \sum_{n \mathop = 0}^\infty \frac{F_{n + 2} } {2^{n + 2} }\) | Translation of Index Variable of Summation | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 2 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \frac {F_{n + 2} } {2^n} }\) | as $2^{n + 2} = 2^2 \times 2^n = 4 \times 2^n$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 2 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \frac 1 {2^n} \paren {\paren {\sum_{k \mathop = 0}^n F_k} + 1} }\) | from $(1)$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 2 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac {F_k} {2^n} } + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \frac 1 {2^n} }\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 2 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac {F_k} {2^n} } + \frac 2 4\) | from $(2)$ | |||||||||||
| \(\text {(3)}: \quad\) | \(\ds \) | \(=\) | \(\ds 1 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac {F_k} {2^n} }\) |
We have:
| \(\ds 1 + \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac {F_k} {2^n} }\) | \(=\) | \(\ds S\) | ||||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \frac 1 4 \paren {\sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac{F_k} {2^n} }\) | \(<\) | \(\ds S\) |
Hence we can show that $S$ is absolutely convergent by the Ratio Test:
For $S$ we get $a_n = \dfrac {F_n} {2^n}$ therefore
| \(\ds \lim_{n \mathop \to \infty} \size {\frac {a_{n + 1} } {a_n } }\) | \(=\) | \(\ds \lim_{n \mathop \to \infty} \size {\frac {\frac {F_{n + 1 } } {2^{n + 1 } } } {\frac {F_n } {2^n } } }\) | substituting $a_n$ and $a_{n + 1}$ from above | |||||||||||
| \(\ds \) | \(=\) | \(\ds \lim_{n \mathop \to \infty} \size {\frac {2^n F_{n + 1 } } {2^{n + 1 } F_n} }\) | reformatting division of fractions | |||||||||||
| \(\ds \) | \(=\) | \(\ds \lim_{n \mathop \to \infty} \size {\frac {F_{n + 1} } {2F_n} }\) | cancelling $2^n$ from top and bottom | |||||||||||
| \(\ds \) | \(=\) | \(\ds \lim_{n \rightarrow \infty} \size {\frac {F_n + F_{n - 1} } {F_n + F_n} }\) | Definition of Fibonacci Numbers: $F_{n + 1} = F_n + F_{n - 1}$ and $2F_n = F_n + F_n$ | |||||||||||
| \(\ds \) | \(<\) | \(\ds 1\) | $F_n > F_{n - 1}$ so $F_n + F_n > F_n + F_{n - 1}$ |
Therefore the double summation is absolutely convergent and we can exchange the order of the sums.
We note that:
- $0 \le k \le n < \infty$
Therefore by Fubini's Theorem for Infinite Sums:
- $\ds \sum_{n \mathop = 0}^\infty \sum_{k \mathop = 0}^n \frac {F_k} {2^n} = \sum_{k \mathop = 0}^\infty \sum_{n \mathop = k}^\infty \frac{F_k} {2^n}$
and it follows that:
| \(\ds S\) | \(=\) | \(\ds 1 + \frac 1 4 \paren {\sum_{k \mathop = 0}^\infty \sum_{n \mathop = k}^\infty \frac {F_k} {2^n} }\) | continuing from $(3)$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds 1 + \frac 1 4 \paren {\sum_{k \mathop = 0}^\infty \paren {F_k \sum_{n \mathop = 0}^\infty \paren {\frac 1 {2^k} } \frac 1 {2^n} } }\) | reindexing the sum | |||||||||||
| \(\ds \) | \(=\) | \(\ds 1 + \frac 1 4 \paren {\sum_{k \mathop = 0}^\infty \paren {\frac 1 {2^k} F_k \sum_{n \mathop = 0}^\infty \paren {\frac 1 {2^n} } } }\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds 1 + \frac 1 4 \paren {2 \sum_{k \mathop = 0}^\infty \frac {F_k} {2^k} }\) | from $(2)$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds 1 + \frac S 2\) | as $S = \ds \sum_{k \mathop = 0}^\infty \frac {F_k} {2^k}$ by hypothesis | |||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \dfrac S 2\) | \(=\) | \(\ds 1\) | |||||||||||
| \(\ds \leadsto \ \ \) | \(\ds S\) | \(=\) | \(\ds 2\) |
Hence the result.
$\blacksquare$