20
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ Sometimes known as the Prévost Constant. $\endgroup$
    – PM 2Ring
    Nov 29, 2017 at 5:04
  • 1
    $\begingroup$ Short proof idea: Note that $F_{n+1}/F_n$ converges to the golden section $\frac{1}{2}(1+\sqrt{5}) = 1.618...$. Apart from the first five elements, this means that an upper limit can be estimated by summing up a geometric series $q^n$ with $q=1/1.6$, yielding $2.666...$ Correct for the first five elements and see that the sum is still less than 4. $\endgroup$
    – Thern
    Nov 29, 2017 at 10:46
  • $\begingroup$ There are a few related posts. One of the answers here gives $4$ as an upper bound: Sum of reciprocals of Fibonacci numbers convergence. You could be also interested in What is the sum of Fibonacci reciprocals? and Sum of inverse of Fibonacci numbers $\endgroup$ Nov 29, 2017 at 13:30
  • $\begingroup$ @PM2Ring Interestingly, Wikipedia Reciprocal Fibonacci constant says the irrationality was proved by Richard André-Jeannin in 1989, while your link says it was shown by Marc Prévost c. 1977. It would be nice to find out which source is wrong. $\endgroup$ Nov 29, 2017 at 14:28
  • $\begingroup$ @JeppeStigNielsen Indeed! When I was investigating this constant a decade or so ago, Wikipedia mentioned Marc Prévost, but his name is now absent from that page. Maybe he did have an irrationality proof, but it was flawed. $\endgroup$
    – PM 2Ring
    Nov 29, 2017 at 14:34

8 Answers 8

41
$\begingroup$

$$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.

$\endgroup$
4
  • 4
    $\begingroup$ This doesn't show convergence but I still really like the argument! +1 $\endgroup$
    – B. Mehta
    Nov 29, 2017 at 4:27
  • 1
    $\begingroup$ @B.Mehta, good point, I was taking convergence for granted. $\endgroup$ Nov 29, 2017 at 4:31
  • 3
    $\begingroup$ @B.Mehta, I've added a proof of convergence. Thanks again for pointing out the oversight. $\endgroup$ Nov 29, 2017 at 4:55
  • $\begingroup$ Damn that was really elegant. +1 $\endgroup$
    – clathratus
    Oct 30, 2018 at 17:08
22
$\begingroup$

Prove by induction that $$2^n\leq F_{2n}$$ and $$2^{n}\leq F_{2n+1}$$

$\endgroup$
1
16
$\begingroup$

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$$

$\endgroup$
11
$\begingroup$

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 $

$\endgroup$
2
  • 2
    $\begingroup$ This is my favorite approach, in part due to its simplicity. $\endgroup$
    – Mala
    Nov 29, 2017 at 19:23
  • $\begingroup$ This is Rene Schipperus' suggestion, but with the details filled in. +1 $\endgroup$ Dec 2, 2017 at 16:24
6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ The second term of the inverse Fibonacci series is greater than your geometric series $\endgroup$ Nov 29, 2017 at 4:11
  • $\begingroup$ @RossMillikan Good point! Thank you; I will edit. $\endgroup$ Nov 29, 2017 at 4:12
1
$\begingroup$

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 $$

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.