Proving ${\sum_{n=1}^\infty {1\over F_n}} <4$ I'm trying to prove the sum of Fibonacci numbers' reciprocals is less than 4, which is:
$${\sum_{n=1}^\infty {1\over F_n}} <4$$
It makes me confused because the only information I know about Fibonacci numbers that might be useful are its recurrence relation and general formula. But when dealing with reciprocals, I found the info hard to use.
I also thought of induction: maybe turning this into:
 $${\sum_{n=1}^\infty {1\over F_n}} <4-A$$
where A is related to $F_n$. But this method also seems to be not working.
Could anyone please give me some hints?
 A: Inverse Fibonacci sequence:
$$\frac{1}{1}, \frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \frac{1}{5}\ldots$$
Geometric series beginning with $1$ and ratio of $3/4$:
$$\frac{1}{1}, \frac{3}{4}, \frac{9}{16}, \frac{27}{64}, \frac{81}{256}, \ldots$$
Summing, the latter yields a series that is greater than the former; moreover, observe that
$$\sum_{n \geq 0} \Big(\frac{3}{4}\Big)^n = 4$$
thereby establishing the desired inequality.
Details that remain to fill in: Show that everything converges. Prove that the effect of the first couple terms will not be disastrous.
A: $$S={1\over1}+{1\over1}+{1\over2}+{1\over3}+{1\over5}+{1\over8}+\cdots=2+{1\over1+1}+{1\over1+2}+{1\over2+3}+{1\over3+5}+\cdots\\\lt2+{1\over1+1}+{1\over1+1}+{1\over2+2}+{1\over3+3}+\cdots\\
=2+{1\over2}\left({1\over1}+{1\over1}+{1\over2}+{1\over3}+\cdots \right)=2+{1\over2}S$$
so ${1\over2}S\lt2$, or $S\lt4$.
Remark:  As B. Mehta points out, this argument only works if the sum converges.  So here's a cheap way to show convergence.  By induction, if $F_n\ge cn^2$ and $F_{n-1}\ge c(n-1)^2$, which is true for $n\lt4$ if $c$ is sufficiently small, then
$$F_{n+1}=F_n+F_{n-1}\ge c(n^2+(n-1)^2)=c(n^2+(n^2-2n)+1)\ge c(n^2+2n+1)=c(n+1)^2$$
since $n^2-2n\ge2n$ if $n\ge4$. It follows that $\sum{1\over F_n}\le{1\over c}\sum{1\over n^2}$, which converges.
A: Prove by induction that 
$$2^n\leq F_{2n}$$ and 
$$2^{n}\leq F_{2n+1}$$
A: We know the Fibonacci series is very close to geometric, so we can sum the reciprocals of a similar series as an upper bound.  Recall Binet's formula $$F_n=\frac {\phi^n-\psi^n}{\sqrt 5}$$
where $\phi=\frac 12(1+\sqrt 5)\approx 1.618, \psi=\frac 12(1-\sqrt 5)\approx -0.618$  
The first three terms of the inverse Fibonacci series are $\frac 11+\frac 11 + \frac 12=2.5$.  After that we have $|\psi^n| \lt 0.03 \phi^n$, so $\frac 1{F_n} \lt \frac 1{0.94\phi^n}$ so
$$\sum_{n=1}^\infty\frac 1{F_n}=2.5+\sum_{n=4}^\infty\frac 1{F_n}\\
\lt 2.5+\frac 1{0.94}\sum_{n=4}^\infty\frac {\sqrt 5}{\phi^n}\\
=2.5+\frac {\sqrt 5}{0.94\phi^3(\phi-1)}\lt 2.5+0.9087=3.4087\lt 4$$
A: Another attempt: separate the series into two partial series:
$$
\small \begin{array} {r|r}
 1 & 1 \\ 
 1/2 & 1/3 \\ 
 1/5 & 1/8 \\ 
 1/13 & 1/21 \\ 
 1/34 & 1/55 \\ 
 ... & ... \\
 s_1 & s_2
 \end{array}
$$
Each sum $s_1,s_2$ is obviously smaller than $1,1/2,1/4,1/8,...$ (easily provable considering two steps in the Fibonacci-sequence) so the sum must be smaller than $2 \times (1+1/2+1/4+...) = 4 $
A: This solution uses only simple arithmetic and some recursion.
First we prove that $F_{n+1}-\dfrac{3}{2}F_n\gt 0$ for all $n\ge 4$. Simplify the left hand part:
$$
F_{n+1}-\dfrac{3}{2}F_n = F_{n}+F_{n-1}-\dfrac{3}{2}F_n = F_{n-1}-\dfrac{1}{2}F_n = F_{n-1}-\dfrac{1}{2}(F_{n-1}+F_{n-2}) = \dfrac{1}{2}(F_{n-1}-F_{n-2}) = \dfrac{1}{2}F_{n-3}
$$
Since $F_{n-3}$ is positive for all $n\ge 4$, the statement is true.
Now rearrange the inequality: $F_{n+1}\gt\dfrac{3}{2}F_n$
Invert both sides: $\dfrac{1}{F_{n+1}}\lt\dfrac{2}{3}\dfrac{1}{F_n}$
This holds for all $n\ge 4$, so we can recursively expand the right-hand side:
$$
\dfrac{1}{F_{n+1}}\lt\dfrac{2}{3}\dfrac{1}{F_n}\lt\left(\dfrac{2}{3}\right)^2 \dfrac{1}{F_{n-1}}\lt\cdots\lt\left(\dfrac{2}{3}\right)^{n-3} \dfrac{1}{F_4}
$$
This provides an upper bound for the sum since each term is smaller than a corresponding term in a convergent geometric series. It could also be used as an alternative proof of convergence for Barry Cipra's excellent answer, but using finite descent rather than induction.
The rest just involves calculating this upper bound. First a partial sum of $\dfrac{1}{F_n}$ where $n>4$:
$$
\sum\limits_{n=5}^\infty \dfrac{1}{F_n} \lt \sum\limits_{k=1}^\infty \left(\dfrac{2}{3}\right)^{k} \dfrac{1}{F_4}=\dfrac{1}{3}\cdot\dfrac{2}{3}\sum\limits_{k=0}^\infty \left(\dfrac{2}{3}\right)^{k} = \dfrac{2}{9}\cdot\dfrac{1}{1-\frac{2}{3}} = \dfrac{2}{3}
$$
Then to complete the proof we add the first four terms to both sides:
$$
\sum\limits_{n=1}^\infty \dfrac{1}{F_n} = \dfrac{1}{F_1}+\dfrac{1}{F_2}+\dfrac{1}{F_3}+\dfrac{1}{F_4}+\sum\limits_{n=5}^\infty \dfrac{1}{F_n} \lt 1+1+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{2}{3} = \frac{7}{2} \lt 4
$$
A: By double-counting the number of subsets of $\{1,2,\ldots n\}$ that do not contain $2$ consecutive numbers, we can show that $F_{n+2} = \displaystyle \sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-k+1}{k}$. Since $0\leq k \leq \bigg\lfloor \dfrac{n+1}{2}\bigg\rfloor$ we have $\bigg\lfloor \dfrac{n+1}{2}\bigg\rfloor \leq n-k+1.$ Using the falling factorial notation we then get:
$\Rightarrow F_{n+2}= \displaystyle \sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-k+1}{k} = \displaystyle \sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\dfrac{(n-k+1)_k}{k!}\geq \displaystyle \sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\dfrac{\left(\bigg\lfloor \dfrac{n+1}{2}\bigg\rfloor\right)_k}{k!}= \displaystyle \sum_{k=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{\bigg\lfloor \dfrac{n+1}{2}\bigg\rfloor}{k}= 2^{\lfloor\frac{n+1}{2}\rfloor}$
$\Rightarrow \forall \, n \, \in \mathbb{N}, F_{n+2} \geq 2^{\lfloor\frac{n+1}{2} \rfloor}$
$\Rightarrow \displaystyle \sum_{n=1}^{\infty}\dfrac{1}{F_n} \leq 2+ \displaystyle \sum_{n=1}^{\infty}\dfrac{1}{2^{\lfloor\frac{n+1}{2} \rfloor}}=4$ 
A: By induction,
if $F_N \ge b^N$ and $b+1 \ge b^2$, then 
$F_n \ge b^n$ for $n \ge N$.
Therefore, 
$$
\sum_{n=1}^\infty {1\over F_n}
\le
\sum_{n=1}^{N-1} {1\over F_n}
+
\sum_{n=N}^\infty {1\over b^n}
=
\sum_{n=1}^{N-1} {1\over F_n}
+
\frac{1}{b^{N-1}(b-1)}
$$
When $b=\frac43$, we get $N=5$ and 
$$
\sum_{n=1}^\infty {1\over F_n}
\le
\sum_{n=1}^{4} {1\over F_n}
+
\frac{1}{b^4(b-1)}
=
\frac{17}{6}+\frac{243}{256}
=
\frac{2905}{768}
=
3.78255208333\cdots
< 4
$$
The value $b=\frac43\approx 1.33$ is about the simplest one for which this argument works. It fails for $b=1.3$ because $F_N \ge b^N$ is never true, but it works for $b=1.31$ with $N=4$.
The answer by @Rene Shippers uses $b=\sqrt2\approx 1.41$, for which $N=7$. The corresponding bound for the sum is $3.461$.
Larger $b$ give better bounds for the sum but need larger $N$. For instance, $b=1.6$ needs $N=72$ but give a bound of $3.3598856662432$, quite close to the actual value.
