## 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

0

0

0

0

0

0

0

0

0

0