Recurrence Relations

Videos (~20-30 mins)

New

The formal definition of a sequence (3:49)
Recursive Sequences (7:36)
The Fibonacci Sequence (6:22)

Useful Review

Introduction to sequences (6:13)
The sum and product of finite sequences (9:20)

Reading (~40 mins)

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