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$
  • 1
    $\begingroup$ Sometimes known as the Prévost Constant. $\endgroup$ – PM 2Ring Nov 29 '17 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 '17 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$ – Martin Sleziak Nov 29 '17 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$ – Jeppe Stig Nielsen Nov 29 '17 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 '17 at 14:34
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.

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

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

| cite | improve this answer | |
$\endgroup$
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$$

| cite | improve this answer | |
$\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 $

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is my favorite approach, in part due to its simplicity. $\endgroup$ – Mala Nov 29 '17 at 19:23
  • $\begingroup$ This is Rene Schipperus' suggestion, but with the details filled in. +1 $\endgroup$ – Benjamin Dickman Dec 2 '17 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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The second term of the inverse Fibonacci series is greater than your geometric series $\endgroup$ – Ross Millikan Nov 29 '17 at 4:11
  • $\begingroup$ @RossMillikan Good point! Thank you; I will edit. $\endgroup$ – Benjamin Dickman Nov 29 '17 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 $$

| cite | improve this answer | |
$\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$

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

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.