Linear Recurrence Relations and the Fibonacci Numbers

Videos (~10 mins)

Review:

The Fibonacci Sequence (6:22)

Reading (~30 mins)

Useful Review:

Warmup (~50 mins)

Problem 1

Use the characteristic root technique to find a closed-formula for the Fibonacci numbers. Your formula should look like:

\[ \begin{aligned} F_n = ar_1^n + br_2^n \end{aligned} \]

for some numbers \(a, b, r_1, r_2 \in \mathbb{R}\) that you determine.

Hint: A complete solution involves both using the quadratic formula and solving a \(2 \times 2\) system of linear equations.

Note: This is a famous result with an easily-researched answer. So, the important part is showing your work and making sure you are familiar with tools like the quadratic formula.

Problem 2

Use the recursive definition of the Fibonacci numbers to write an inductive proof that, for any \(n \in \mathbb{Z}\) with \(n \geq 1\),

\[ \begin{aligned} \sum_{i = 1}^n F_i = F_{n+2} - 1\;. \end{aligned} \]

Note: Don’t forget to include both a base case and an inductive step!