Welcome to mathimatikoi.org;a forum of university mathematics. Enjoy your stay here.

Fibonacci closed form

General Mathematics
Post Reply
User avatar
Tolaso J Kos
Administrator
Administrator
Articles: 2
Posts: 854
Joined: Sat Nov 07, 2015 6:12 pm
Location: Larisa
Contact:

Fibonacci closed form

#1

Post by Tolaso J Kos » Tue Jan 05, 2016 10:31 am

Let $F_n$ denote the $n$-th Fibonacci number. Evaluate (in a closed form) the sum:

$$\sum_{n=0}^{N} \frac{1}{F_{2^n}}$$
Imagination is much more important than knowledge.
User avatar
Grigorios Kostakos
Founder
Founder
Articles: 0
Posts: 460
Joined: Mon Nov 09, 2015 1:36 am
Location: Ioannina, Greece

Re: Fibonacci closed form

#2

Post by Grigorios Kostakos » Tue May 01, 2018 4:51 pm

Because
\begin{align*}
\mathop{\lim}\limits_{{n}\rightarrow{+\infty}}\frac{\frac{1}{F_{2^{n+1}}}}{\frac{1}{F_{2^n}}}&=\mathop{\lim}\limits_{{n}\rightarrow{+\infty}}\frac{F_{2^n}}{F_{2^{n+1}}}\\
&=\mathop{\lim}\limits_{{n}\rightarrow{+\infty}}\frac{\phi^{2^n}-(-\phi)^{-2^n}}{\phi^{2^{n+1}}-(-\phi)^{-2^{n+1}}}\\
&=\mathop{\lim}\limits_{{n}\rightarrow{+\infty}}\frac{\phi^{2^n}-\phi^{-2^n}}{\phi^{2\cdot2^n}-\phi^{-2\cdot2^n}}\\
&=\mathop{\lim}\limits_{{n}\rightarrow{+\infty}}\frac{\phi^{2^n}\big(1-\phi^{-2\cdot2^n}\big)}{\phi^{2\cdot2^n}\big(1-\phi^{-4\cdot2^n}\big)}\\
&=\mathop{\lim}\limits_{{n}\rightarrow{+\infty}}\frac{1}{\phi^{2^n}}\mathop{\lim}\limits_{{n}\rightarrow{+\infty}}\frac{1-\phi^{-2\cdot2^n}}{1-\phi^{-4\cdot2^n}}\\
&=0\,\frac{1-0}{1-0}\\
&=0<1\,,
\end{align*}
by D' Alembert's criterion, we have that the series $\sum_{n=0}^{\infty}\frac{1}{F_{2^n}}$ converges.
We'll prove indyctively that, for every $n\in{\mathbb{N}}$, holds \begin{align}
\mathop{\sum}\limits_{k=0}^{n}\frac{1}{F_{2^{k}}}=3-\frac{F_{2^n-1}}{F_{2^{n}}}\label{1}
\end{align} $\bullet$ For $n=1$ we have $\frac{1}{F_1}+\frac{1}{F_2}=2=3-\frac{F_1}{F_2}$.
$\bullet$ Assuming that it holds for $n=m$ ; i.e. \begin{align}
\mathop{\sum}\limits_{k=0}^{m}\frac{1}{F_{2^{k}}}=3-\frac{F_{2^{m}-1}}{F_{2^{m}}}\label{2}
\end{align}
we''ll prove it for $n=m+1$ : \begin{align*}
\mathop{\sum}\limits_{k=0}^{m+1}\frac{1}{F_{2^{k}}}&=\frac{1}{F_{2^{m+1}}}+\mathop{\sum}\limits_{k=0}^{m}\frac{1}{F_{2^{k}}}\\
&\stackrel{\eqref{2}}{=}\frac{1}{F_{2^{m+1}}}+3-\frac{F_{2^{m}-1}}{F_{2^{m}}}\\
&=3-\frac{F_{2^{m}-1}F_{2^{m+1}}-F_{2^{m}}}{F_{2^{m}}F_{2^{m+1}}}\\
&=3-\frac{F_{2^{m}-1}F_{2^{m}}\big(F_{2^{m}+1}+F_{2^{m}-1}\big)-F_{2^{m}}}{F_{2^{m}}F_{2^{m+1}}}\\
&=3-\frac{F_{2^{m}-1}F_{2^{m}+1}+F_{2^{m}-1}^2-1}{F_{2^{m+1}}}\\
&\stackrel{(*)}{=}3-\frac{F_{2^{m}}^2+(-1)^{2^n}+F_{2^{m}-1}^2-1}{F_{2^{m+1}}}\\
&=3-\frac{F_{2^{m}}^2+F_{2^{m}-1}^2}{F_{2^{m+1}}}\\
&=3-\frac{F_{2^{m+1}-1}}{F_{2^{m+1}}}\,.\qquad\qquad{\text{q.e.d.}}
\end{align*} So \begin{align*}
\mathop{\sum}\limits_{n=0}^{\infty}\frac{1}{F_{2^n}}&=\mathop{\lim}\limits_{{n}\rightarrow{+\infty}}\mathop{\sum}\limits_{k=0}^{n}\frac{1}{F_{2^{k}}}\\
&\stackrel{\eqref{1}}{=}\mathop{\lim}\limits_{{n}\rightarrow{+\infty}}\Big(3-\frac{F_{2^n-1}}{F_{2^{n}}}\Big)\\
&=3-\frac{1}{\mathop{\lim}\limits_{{n}\rightarrow{+\infty}}\frac{F_{2^n}}{F_{2^{n}-1}}}\\
&\stackrel{(**)}{=}3-\frac{1}{\phi}\\
&=\dfrac{7-\sqrt{5}}{2}\,.
\end{align*}

$(*)\quad F_{n-1}F_{n+1}-F_n^2=(-1)^n\,. $

$(**)\quad\lim_{{n}\rightarrow{+\infty}}\frac{F_{{n}+1}}{F_{{n}}}=\phi\,.$
Grigorios Kostakos
Post Reply