, 2019

Algebra Difficulty 6.6 National olympiad Prove it Netherlands

The sequence of Fibonacci numbers $F_0, F_1, F_2, \ldots$ is defined by $F_0 = F_1 = 1$ and $F_{n+2} = F_n + F_{n+1}$ for all $n \ge 0$ . For example, we have
$F_2 = F_0 + F_1 = 2, \quad F_3 = F_1 + F_2 = 3, \quad F_4 = F_2 + F_3 = 5, \quad F_5 = 8.$
The sequence $a_0, a_1, a_2, \ldots$ is defined by
$a_n = \frac{1}{F_n F_{n+2}} \quad \text{for all } n \ge 0.$
Prove that for all $m \ge 0$ we have:
$a_0 + a_1 + a_2 + \cdots + a_m < 1.$

Solution

Note that for all $n \ge 0$ the number $a_n$ can be rewritten as follows:
$\begin{aligned} a_n &= \frac{1}{F_n F_{n+2}} = \frac{F_{n+1}}{F_n F_{n+2}} \cdot \frac{1}{F_{n+1}} = \frac{F_{n+2} - F_n}{F_n F_{n+2}} \cdot \frac{1}{F_{n+1}} \\ &= \left( \frac{1}{F_n} - \frac{1}{F_{n+2}} \right) \cdot \frac{1}{F_{n+1}} = \frac{1}{F_n F_{n+1}} - \frac{1}{F_{n+1} F_{n+2}}. \end{aligned}$
We now get that for each $m \ge 0$ the sum $a_0 + a_1 + a_2 + \cdots + a_m$ equals
$\left( \frac{1}{F_0 F_1} - \frac{1}{F_1 F_2} \right) + \left( \frac{1}{F_1 F_2} - \frac{1}{F_2 F_3} \right) + \cdots + \left( \frac{1}{F_m F_{m+1}} - \frac{1}{F_{m+1} F_{m+2}} \right).$
In this sum all terms cancel, except the first and last. In this way, we get

a_0 + a_1 + a_2 + \cdots + a_m = \frac{1}{F_0 F_1} - \frac{1}{F_{m+1} F_{m+2}} = 1 - \frac{1}{F_{m+1} F_{m+2}} < 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.