Back to the on-screen lesson ·
Sequences defined by a rule that refers back to itself, how a counting problem produces one, and why a guessed closed form still needs an induction.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to run a recurrence forward without losing count of the steps, check that its initial conditions match its order, and find the recurrence a counting problem obeys by splitting the objects according to their last step. You will also be able to guess a closed form from the first few terms and prove it by induction, using the recurrence itself as the inductive step, and say why the guessing works for some rules and not for Fibonacci.
Induction from lesson 10, which is the same idea seen from the other end: induction proves a statement about $n$ from the statement about $n-1$, and a recurrence computes a value at $n$ from the value at $n-1$. And unit 4's habit of splitting a count into exhaustive cases, which is how a recurrence is found in the first place.
A recurrence relation defines $a_n$ in terms of earlier terms; its order is how far back it looks. Initial conditions are the terms given outright, and there must be as many as the order. A closed form gives $a_n$ from $n$ alone, with no earlier term in it. A recurrence is linear when the earlier terms appear only multiplied by constants.
$a_0 = 3$ and $a_n = 2a_{n-1} + 1$ determines the whole sequence: $3, 7, 15, 31, 63, \ldots$ Every term is computable and no term is computable without the ones before it, which is both the strength and the weakness of the definition.
Order and initial conditions go together. A rule looking back one place needs one starting value; one looking back two places needs two. Fibonacci — $F_n = F_{n-1} + F_{n-2}$ — with only $F_1$ given is not a sequence at all, because nothing decides $F_2$. Counting the initial conditions against the order is the first check to make on any recurrence you meet.
Where recurrences come from. Rarely from algebra; almost always from a count. The method is always the same four moves:
Step 2 is lesson 9's exhaustive case split, and it is where the thinking is. For binary strings with no two adjacent $1$s: a string ending in $0$ is any valid string of length $n-1$ with a $0$ stuck on; a string ending in $1$ must have a $0$ before it, so it is any valid string of length $n-2$ with $01$ stuck on. Hence $a_n = a_{n-1} + a_{n-2}$ — Fibonacci, from a problem that never mentioned it.
Why a closed form is wanted. Running the rule forward to $a_{100}$ takes a hundred steps and gives no idea how fast the sequence grows. A closed form answers both at once, and the next lesson is how to find one.
Another way: steps
To work with a recurrence:
Another way: example
The tower of Hanoi with $n$ discs: to move $n$, move $n-1$ off, move the largest, move $n-1$ back. So $h_n = 2h_{n-1} + 1$ with $h_1 = 1$, giving $1, 3, 7, 15, 31$. The closed form $2^n - 1$ is visible from the list and is proved by induction, not by the list.
Running a recurrence forward often makes a formula obvious. $h_n = 2h_{n-1} + 1$ with $h_1 = 1$ gives $1, 3, 7, 15, 31$, and every one of those is one less than a power of two. So guess $h_n = 2^n - 1$.
That guess is not a proof, and lesson 9 said why: five confirming cases are five confirming cases. The proof is an induction, and the recurrence supplies the step. Base: $h_1 = 1 = 2^1 - 1$. Step: assuming $h_k = 2^k - 1$, the recurrence gives $h_{k+1} = 2(2^k - 1) + 1 = 2^{k+1} - 1$.
That pattern — run forward, guess, prove by induction — is the whole method when it works, and it is worth trying before anything more systematic. It works for geometric rules and for simple non-homogeneous ones; it fails for Fibonacci, where no amount of staring at $1, 1, 2, 3, 5, 8$ suggests the closed form. That failure is what the next lesson exists to fix.
Too few initial conditions. A second-order rule with one starting value defines nothing.
Applying the rule to the wrong term. Each step uses the previous term, not the first one.
Miscounting the steps. From $a_1$ to $a_4$ is three applications, not four. Writing the terms out with their indices prevents this and nothing else does.
Taking a pattern for a proof. The list is where a guess comes from; the induction is what establishes it.
Overlapping cases in the split. If an object can be counted in two of the kinds, the recurrence overcounts, and the error will not show up until the fourth or fifth term.
$a_n = 2a_{n-1} + 1$ is not an equation with an unknown in it; it is a rule that manufactures each term from the one before, and together with its initial condition it already determines every term. Solving it means finding a closed form — a different description of the same sequence — and it is a convenience rather than a necessity. The sequence exists and is completely determined whether or not anybody ever finds a formula for it.
How many ways can a $2 \times n$ strip be tiled with $1 \times 2$ dominoes? Call it $a_n$, and split by what covers the last column.
Name the count, then split.
A vertical domino covers the last column alone, leaving a $2 \times (n-1)$ strip: $a_{n-1}$ ways. Two horizontal dominoes cover the last two columns, leaving $a_{n-2}$.
Two kinds, overlapping in nothing.
So $a_n = a_{n-1} + a_{n-2}$, with $a_1 = 1$ and $a_2 = 2$: Fibonacci again. Two unrelated-looking counting problems have the same rule, which is a sign that the rule is about the splitting and not about the subject.
The recurrence came from the split.
$a_0 = 1$, $a_n = 3a_{n-1}$. Running it: $1, 3, 9, 27, 81$.
Write out enough terms to see something.
Guess $a_n = 3^n$. Base: $a_0 = 1 = 3^0$.
The guess comes from the list; the proof does not.
Step: assuming $a_k = 3^k$, the recurrence gives $a_{k+1} = 3 \cdot 3^k = 3^{k+1}$. By induction the closed form holds for every $n$.
The recurrence itself supplies the inductive step.
$a_2 = 2 + 4 = 6$, $a_3 = 6 + 6 = 12$, $a_4 = 12 + 8 = 20$.
Run it forward, one step at a time.
The list is $2, 6, 12, 20$, and the differences are $4, 6, 8$ — increasing steadily, which suggests something quadratic.
Look at the differences when the terms themselves say nothing.
$n(n+1)$ gives $2, 6, 12, 20$, so guess $a_n = n(n+1)$. Now prove it: the base is $a_1 = 2 = 1 \times 2$, and the step is $a_{k+1} = k(k+1) + 2(k+1) = (k+1)(k+2)$. The guess came from the list and the induction is what makes it a theorem.
A sequence starts at $a_0 = 2$ and obeys $a_n = 2a_{n-1} + 3$. Fill in the next three terms.
| Value | |
|---|---|
| $a_1$ | |
| $a_2$ | |
| $a_3$ |
$a_1 = 5$ and $a_n = a_{n-1} + 3$. What is $a_4$?
Answer:
$a_0 = 5$ and $a_n = 3a_{n-1}$. What is $a_3$?
Answer:
$F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$. Give the two terms before $F_{7}$ and then $F_{7}$ itself.
The two before are two and one, so $F_{7}$ is value.
Put in order the steps of finding the recurrence that a count obeys.
Number the steps in order (write the number in the box):
How many binary strings of length $6$ have no two adjacent $1$s?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A sequence starts at $a_0 = 1$ and obeys $a_n = 3a_{n-1} + 4$. Fill in the next three terms.
| Value | |
|---|---|
| $a_1$ | |
| $a_2$ | |
| $a_3$ |
You can run a recurrence forward, find one from a count, and prove a guessed closed form by induction. Say in your own words why a second-order rule needs two initial conditions, and why the first few terms are a source of guesses rather than a proof. Next: the method that finds a closed form when guessing fails.
10. Your turn: $a_1 = 2$ and $a_n = a_{n-1} + 2n$. Find $a_4$, and guess a closed form., step 3