Back to the on-screen lesson ·
Substituting a power turns a recurrence into a quadratic; its roots give the growth, and the initial values give the constants — in that order.
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 turn a second-order linear recurrence with constant coefficients into its characteristic equation, solve that quadratic, write the general solution in the form its roots call for — including the factor of n a repeated root needs — and only then use the initial values to find the two constants. You will also be able to say which root decides the growth and why the initial values do not affect it, and to recognise a divide-and-conquer recurrence as a different shape that this method does not touch.
Lesson 27 ran recurrences forward and guessed closed forms from the first few terms. That method fails on Fibonacci — nothing in $1, 1, 2, 3, 5, 8$ suggests the answer — and this lesson is the systematic method that does not need a guess. You also need factorising a quadratic, which is the only algebra involved.
A recurrence is linear with constant coefficients when it reads $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ with the $c$ fixed numbers, and homogeneous when there is no extra term added on. Its characteristic equation is $r^2 = c_1 r + c_2$. A particular solution is any one sequence satisfying a non-homogeneous recurrence; the general solution is the family with the constants left in.
For $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, try $a_n = r^n$. Substituting gives $r^n = c_1 r^{n-1} + c_2 r^{n-2}$, and dividing by $r^{n-2}$ leaves
$$r^2 = c_1 r + c_2.$$
A question about sequences has become a quadratic. That trade is the whole method, and it works because the recurrence is linear: any combination of solutions is a solution, so finding two is finding all of them.
| The roots | The general solution |
|---|---|
| distinct, $r_1 \ne r_2$ | $A r_1^n + B r_2^n$ |
| repeated, $r$ | $(A + Bn) r^n$ |
Why the repeated case needs the $n$. With one root, $A r^n$ has one constant and cannot meet two initial conditions — the sequence would be over-determined and usually no solution would exist. The factor $n$ supplies a second independent solution, and substituting $n r^n$ into the recurrence confirms it works whenever the root is repeated.
The constants come last. The roots are read off the recurrence alone, and they describe every sequence obeying it. The initial values enter only at the end, as two linear equations in $A$ and $B$. Two sequences with the same rule and different starting values have different constants and exactly the same growth, and separating those two facts is most of the value of the method.
Fibonacci. $r^2 = r + 1$ gives $r = (1 \pm \sqrt 5)/2$, so $F_n = A\varphi^n + B\psi^n$, and the initial values give $A = 1/\sqrt 5$ and $B = -1/\sqrt 5$. An integer sequence with an irrational closed form — which no amount of looking at $1, 1, 2, 3, 5$ would ever have suggested.
Another way: steps
Another way: example
$a_n = 5a_{n-1} - 6a_{n-2}$, $a_0 = 1$, $a_1 = 4$. Characteristic: $r^2 - 5r + 6 = 0$, so $r = 2$ or $3$, and $a_n = A2^n + B3^n$. At $n = 0$: $A + B = 1$; at $n = 1$: $2A + 3B = 4$. So $B = 2$, $A = -1$, and $a_n = 3^{n+1} - 2^n$.
The larger root decides the growth, whatever the initial values — because $A r_1^n + B r_2^n$ is dominated by whichever power is bigger once $n$ is large. Fibonacci grows like $\varphi^n$ with $\varphi \approx 1.618$, and the other root, about $-0.618$, contributes less than half a unit for every $n$.
Divide-and-conquer recurrences are a different shape and are not solved this way. $T(n) = aT(n/b) + f(n)$ describes an algorithm splitting into $a$ pieces of size $n/b$ with $f(n)$ spent combining, and the question asked of it is growth rather than a formula. Compare two amounts of work: the leaves, which total about $n^{\log_b a}$, and the top level, $f(n)$.
| Recurrence | Growth | Why |
|---|---|---|
| $T(n) = 2T(n/2) + n$ | $\Theta(n \log n)$ | levels cost the same; there are $\log n$ of them |
| $T(n) = 2T(n/2) + 1$ | $\Theta(n)$ | the leaves dominate |
| $T(n) = T(n/2) + 1$ | $\Theta(\log n)$ | only the depth counts |
| $T(n) = 4T(n/2) + n$ | $\Theta(n^2)$ | the split outruns the combining |
The first row is merge sort, and the second is a tree traversal. The method is the master theorem; this course states it as a comparison and does not prove it.
Forgetting the factor of $n$ for a repeated root. One constant cannot meet two conditions, and the equations will come out inconsistent rather than wrong-looking.
Using the initial values too early. They mean nothing until there is a general solution to put them into.
Dividing by the wrong power. Divide by the lowest power of $r$ present; dividing by $r^n$ leaves negative exponents and a mess.
Expecting integer roots always. Fibonacci's are irrational, and an integer sequence may perfectly well have an irrational closed form.
Applying the characteristic equation to a divide-and-conquer recurrence. $T(n) = 2T(n/2) + n$ has a different shape and the substitution $r^n$ does nothing to it.
It is easy to treat $A$ and $B$ as part of the solution of the recurrence, and they are not: the recurrence alone determines the roots, and every sequence obeying it has the same two powers in its closed form. What the initial conditions do is pick one member of that family. Seeing the split clearly is what makes the growth claim obvious — two sequences with the same rule grow at the same rate however differently they start — and it is also why the constants cannot be found before the general solution exists.
$a_n = a_{n-1} + 6a_{n-2}$, $a_0 = 1$, $a_1 = 8$. Substituting $a_n = r^n$ and dividing by $r^{n-2}$: $r^2 - r - 6 = 0$.
The recurrence becomes a quadratic.
$(r - 3)(r + 2) = 0$, so the roots are $3$ and $-2$ and $a_n = A3^n + B(-2)^n$.
Two roots, two terms, two constants.
At $n = 0$: $A + B = 1$. At $n = 1$: $3A - 2B = 8$. So $A = 2$, $B = -1$, and $a_n = 2 \cdot 3^n - (-2)^n$. Check: $a_2 = 18 - 4 = 14$, and the recurrence gives $8 + 6 = 14$.
Check against a term you did not use.
$a_n = 6a_{n-1} - 9a_{n-2}$ gives $r^2 - 6r + 9 = (r-3)^2$, so $3$ twice.
One root, appearing twice.
$A3^n$ alone has one constant. With $a_0 = 2$ it forces $A = 2$, and then $a_1$ is decided at $6$ — so any other starting value would have no solution at all.
One constant cannot meet two conditions.
The general solution is $(A + Bn)3^n$. With $a_0 = 2$ and $a_1 = 9$: $A = 2$, and $(2 + B)3 = 9$ gives $B = 1$. The $n$ is not a patch — it is the second independent solution the linearity guarantees exists.
Two constants restored, and the fit works.
Characteristic equation: $r^2 - 7r + 12 = 0$, which factors as $(r-3)(r-4)$, so the roots are $3$ and $4$.
Substitute, divide, factorise.
General solution $a_n = A3^n + B4^n$. At $n = 0$: $A + B = 2$. At $n = 1$: $3A + 4B = 9$.
Only now do the initial values enter.
Solving, $B = 3$ and $A = -1$, so $a_n = 3 \cdot 4^n - 3^n$. Check against $a_2$: the formula gives $48 - 9 = 39$, and the recurrence gives $7 \times 9 - 12 \times 2 = 39$. And the growth is $4^n$, from the larger root, whatever the starting values had been.
The recurrence is $a_n = 6a_{n-1} - 5a_{n-2}$, whose characteristic equation is $r^2 - 6r + 5 = 0$. Fill in its two roots.
| Value | |
|---|---|
| Smaller root | |
| Larger root |
For $a_n = 6a_{n-1} - 5a_{n-2}$, what is the larger root of the characteristic equation?
Answer:
$a_n = 4a_{n-1} - 4a_{n-2}$ has the repeated root $2$, so $a_n = (A + Bn)2^{n}$. With $A = 2$ and $B = 6$, what is $a_2$?
Answer:
How fast does $T(n) = T(n/2) + 1$ grow?
Put in order the steps of finding a closed form for a second-order linear recurrence with constant coefficients.
Number the steps in order (write the number in the box):
$a_n = 4a_{n-1} - 4a_{n-2}$ has the repeated root $2$, so $a_n = (A + Bn)(2)^{n}$. Given $a_0 = 1$ and $a_1 = 6$, find $A$ and $B$.
$A = $ca and $B = $cb.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The recurrence is $a_n = 2a_{n-1} + 8a_{n-2}$, whose characteristic equation is $r^2 - 2r - 8 = 0$. Fill in its two roots.
| Value | |
|---|---|
| Smaller root | |
| Larger root |
You can find a characteristic equation, solve it, write the general solution and fit the constants to the initial values. Say in your own words why a repeated root needs the factor of n, and why the roots belong to the rule while the constants belong to the starting values. That completes the course: logic, the proof techniques, sets and relations and functions, counting, graphs, number theory and recurrences.
10. Your turn: $a_n = 7a_{n-1} - 12a_{n-2}$ with $a_0 = 2$ and $a_1 = 9$, step 3