Recurrence Relations

Videos

Recurrence Relations 5:39
Solving Recurrence Relations by Guess-and-Check (7:28)
Proving Solutions of Recurrence Relations (7:19)
A Quick Hello to the Fibonacci Numbers (8:05)

Readings

Warmup

Problem 1

Consider the recurrence relation \(a_n = 3a_{n-1} - 2\) with initial condition \(a_0 = 2\). This recurrence relation has closed formula solution \(a_n = 3^n + j\) for some mystery integer \(j\).

Part A

Write out \(a_1\), \(a_2\), \(a_3\), and \(a_4\).

Part B

Based on your answer in Part A, what is the value of the mystery integer \(j\)?

Part C

Write a careful proof by induction that that \(a_n = 3^n + j\) for all \(n \geq 0\), using your choice of \(j\) from Part B.

Problem 2

Consider a recursion relation of the form \[ \begin{aligned} a_n = p a_{n-1} + 1 \end{aligned} \]

with initial condition \(a_0\).

Part A

Write a function in Python or Java that computes \(a_n\) using recursion. Your function should accept 3 arguments: \(p\), \(a_0\), and \(n\). Use your function to compute \(a_{10}\) when \(p = 2\) and \(a_0 = -1\).

Part B

Use your function to experiment. Find values of \(p\) and \(a_0\) such that:

\(a_n\) becomes closer and closer to some fixed, finite number as \(n\) grows large.
\(a_n\) “blows up” (gets very big) as \(n\) grows large.
\(a_n\) flips between positive and negative values as \(n\) grows large.

Problem 3

Let \(F_i\) be the \(i\)th Fibonacci number. Prove that, for all \(n \geq 1\),

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