Problems

The Fibonacci numbers are defined by \(F_0 = 0\), \(F_1 = 1\) and, for \(n \geqslant 0\), \(F_{n+2} = F_{n+1} + F_n\).

1. Prove that \(F_r \leqslant 2^{r-n} F_n\) for all \(n \geqslant 1\) and all \(r \geqslant n\).
2. Let \(S_n = \displaystyle\sum_{r=1}^{n} \frac{F_r}{10^r}\). Show that \[\sum_{r=1}^{n} \frac{F_{r+1}}{10^{r-1}} - \sum_{r=1}^{n} \frac{F_r}{10^{r-1}} - \sum_{r=1}^{n} \frac{F_{r-1}}{10^{r-1}} = 89S_n - 10F_1 - F_0 + \frac{F_n}{10^n} + \frac{F_{n+1}}{10^{n-1}}\,.\]
3. Show that \(\displaystyle\sum_{r=1}^{\infty} \frac{F_r}{10^r} = \frac{10}{89}\) and that \(\displaystyle\sum_{r=7}^{\infty} \frac{F_r}{10^r} < 2 \times 10^{-6}\). Hence find, with justification, the first six digits after the decimal point in the decimal expansion of \(\dfrac{1}{89}\).
4. Find, with justification, a number of the form \(\dfrac{r}{s}\) with \(r\) and \(s\) both positive integers less than \(10000\) whose decimal expansion starts \[0.0001010203050813213455\ldots\,.\]

The Fibonacci numbers \(F_{n}\) are defined by the conditions \(F_{0}=0\), \(F_{1}=1\) and \[F_{n+1}=F_{n}+F_{n-1}\] for all \(n\geqslant 1\). Show that \(F_{2}=1\), \(F_{3}=2\), \(F_{4}=3\) and compute \(F_{5}\), \(F_{6}\) and~\(F_{7}\). Compute \(F_{n+1}F_{n-1}-F_{n}^{2}\) for a few values of \(n\); guess a general formula and prove it by induction, or otherwise. By induction on \(k\), or otherwise, show that \[F_{n+k}=F_{k}F_{n+1}+F_{k-1}F_{n}\] for all positive integers \(n\) and \(k\).