1996 Paper 2 Q3

Year: 1996
Paper: 2
Question Number: 3

Course: LFM Pure
Section: Proof by induction

Difficulty: 1600.0 Banger: 1500.0

proof by induction Fibonacci numbers recurrence relation sequences Cassini identity addition formula

Problem

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\).

No solution available for this problem.

Rating Information

Difficulty Rating: 1600.0

Difficulty Comparisons: 0

Banger Rating: 1500.0

Banger Comparisons: 0

Show LaTeX source

Problem source

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

Back to List