Subscribe to the weekly news from TrueShelf

0

Fibonacci numbers and Induction

The Fibonacci numbers, \(F_0, F_1, F_2, \dots\) , are defined recursively by the equations \(F_0 = 0\), \(F_1 = 1\), and \(F_n = F_{n-1} + F_{n-2},\) for \(n > 1\).

  • Prove that

\({F_1}^2 + {F_2}^2 + \dots + {F_n}^2 ={F_n}F_{n+1}\)

for all positive integers \(n\).

  • Prove, using strong induction, the following closed-form formula for \(F_n\).

\(F_n = \frac{p^n - q^n}{\sqrt{5}}\)

where \(p = \frac{1+\sqrt{5}}{2}\) and \(q = \frac{1-\sqrt{5}}{2}\).

  • Let \(T_n\) count the number of ways to tile a \(1 \times n\) board with squares (\(1 \times 1\) tiles) and dominoes (\(1 \times 2\) tiles). Prove that \(T_n = F_{n+1}\).

  • Prove that \(\displaystyle \sum_{i=0}^{\lfloor{n/2}\rfloor} {n-i \choose i} = F_{n+1}\)

Source: folklore

Related Content