Sum of nth Fibonacci Number over nth Power of 2

From ProofWiki
Jump to navigation Jump to search

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$