Last week we looked at a recent question about recurrence relations, and I realized it needs a companion article to introduce these ideas. So here we will look at some answers from Ask Dr. Math about the simpler case, including general methods, why they work, and applications.
The ones we teach are the ones we can solve …
First, a general question from Dawn in 1999:
Recursive and Explicit Formulas
Is there an easy way to convert recursive formulas into explicit ones and vice versa? I've studied the examples in my pre-calculus book, but all of the examples are easy-to-solve problems, unlike the ones I will have to solve on the test. I've tried figuring out the first ten or so numbers in a particular sequence, but rarely can I see a pattern that I can put into a formula.
Solving a recursion means converting a recursive formula to an explicit (non-recursive) formula. We’ll also briefly look at the vice-versa here!
Doctor Rob answered:
In general, this is a fairly difficult problem. There are easy cases, but there are hard cases, and there are unsolved (and possibly unsolvable) cases, too. The situation is analogous to the situation when you are faced with a differential equation (analogue of a recursion) or an explicit equation for a function (analogue of the formula).
Probably the problems Dawn will do on a test are the same type she’s learning: the easy ones.
Let the sequence be S(1), S(2), ... .
Some of the cases where you can find the formula given the recursion are: 1. Recursions that are sums of terms like c(i)*S(n-i), where c(i) are constants, like the Fibonacci recursion: S(n) = 1*S(n-1) + 1*S(n-2). 2. As in (1), but you can also have a term which is a polynomial in n, like S(n) = 2*S(n-1) + n. 3. Things like S(n) = S(n-1)^c, where c is a constant. There are lots of others, too.
The first category are linear homogeneous recurrences with constant coefficients, the main topic this week. The second category are non-homogeneous recurrences, which we looked at last week (and maybe again next week). The third is a special case that we probably won’t see. As an example, if \(a_n = a_{n-1}^2\), and \(a_0=2\), then the first few terms are \(2, 4, 16, 256, \dots\), that is, \(2^1, 2^2, 2^4, 2^8, \dots\). You can perhaps see what the formula is.
The important point is that (like much of algebra, actually) we teach problems for which we have methods, and commonly hide the fact that that is a rather rare situation! It’s good to start with that knowledge.
The reverse problem
Now we look at that “vice versa” question, which gets less attention (but we will in fact be using later):
If you start with a formula and want to find a recursion, it is a good idea to write out S(n), S(n-1), S(n-2), and try to see some part of the first formula that is actually equal to one of the other formulas. For example, if: S(n) = n*2^n, S(n-1) = (n-1)*2^(n-1), etc. then you can see that the second formula can be converted into the first by multiplying by (2*n)/(n-1), so S(n) = [(2*n)/(n-1)]*S(n-1), S(1) = 2 is a recursion which this formula satisfies.
There is no general technique, really, but let’s take a moment to examine this example. We’re given the formula \(S_n=n2^n\), which generates the sequence (starting with \(n=0\)) \(0,2,8,24,64,\dots\). If we were just given this sequence, we might discover the formula by factoring. But how can we find a recursive formula? His suggestion is to write the formulas for two successive terms, $$S_n=n2^n\\ S_{n-1}=(n-1)2^{n-1}$$ and see that the ratio of the expressions is $$\frac{n2^n}{(n-1)2^{n-1}}=\frac{2n}{n-1}$$ so that $$S_n=\frac{2n}{n-1}S_{n-1}$$ This doesn’t apply to \(n=1\), so we have to make that the first term, specifying \(S_1=2\). Then $$S_2=\frac{2\cdot2}{2-1}\cdot2=8\\ S_3=\frac{2\cdot3}{3-1}\cdot8=24\\ S_4=\frac{2\cdot4}{4-1}\cdot24=64$$
We’ll see later how to create a recursion from a word problem.
Solving second-order recurrences
We’ll start actually solving, in this question from 2001:
Second-Order Linear Recurrences
I was wondering if I could get help with the following problems: 1. Find a recurrence relation for the number of bit strings of length n that do not contain a pair of consecutive zeroes. What are the initial conditions? 2. Solve the following recurrence relations together with the initial conditions given:
a_n = 4 a_{n-1} - 4 a_{n-2}; a_0 = 6, a_1 = 8 In other words, a sub n = 4 times a sub n minus 1 minus 4 times a sub n minus 2; a sub zero equals six, a sub one equals eight. 3. Consider the sequence 0, 1, 1/2, 3/4, 5/8, 11/16, ..., in which each term is the average of the previous two terms (eg., the next term will be 1/2(5/8 + 11/16) = 21/32. Find the formula for the general term using a recurrence equation. Make sure you state the initial condition. Then give a formula for the general term using a non-recursive equation by solving the above recurrence equation. I would appreciate any help you can give to help me get started with these problems.
The first question is to describe a situation in terms of a recurrence, which we don’t have to actually solve, The second is the sort of problem we’re focusing on here; and in the third we turn a description into a recurrence, then solve it.
How to solve a recurrence
Two of us answered. First, Doctor Rob gave the general procedure, without applying it to any of these problems, because Lanada only asked to get started!
Thanks for writing to Ask Dr. Math, Lanada. Here are the steps to solving second-order linear recurrences. 1. Find the recurrence relations and initial conditions. In the second problem, it is given. In the third, you have to find it: a(n) = [a(n-1)+a(n-2)]/2, a(0) = 0, a(1) = 1.
In most problems we’ll see, we are given the recurrence in algebraic form like this. Sometimes it may not be \(a_n\) on the left, but, say, \(a_{n+2}\). We saw one like that last time. I’ll use the recurrence for the first problem to illustrate, since we won’t be seeing it, but only deriving it, below. As we’ll see, it is the Fibonacci recursion (with different initial values): $$a_n=a_{n-1}+a_{n-2},a_1=2,a_2=3$$
2. Write it in the form a(n) + c(1)*a(n-1) + c(2)*a(n-2) = 0, where c(1) and c(2) are constants.
This is like putting a polynomial in standard form. In fact, that’s why we’re doing this: $$a_n-a_{n-1}-a_{n-2}=0$$
3. Write down the characteristic polynomial x^2 + c(1)*x + c(2). 4. Find the roots of this polynomial. They can be r(1) and r(2), distinct roots, or r(1), a double root.
For our example, the polynomial is $$x^2-x-1=0$$ By the quadratic formula, its roots are $$r_1=\frac{1+\sqrt{5}}{2},r_2=\frac{1-\sqrt{5}}{2}$$
5. Write down the general solution of the recurrence. In the case of distinct roots, that is a(n) = k(1)*r(1)^n + k(2)*r(2)^n. In the case of a double root, that is a(n) = [k(1)*n + k(2)]*r(1)^n. Here k(1) and k(2) are two arbitrary constants.
We use the two roots as bases of exponentials, with unknown coefficients: $$a_n=k_1r_1^n+k_2r_2^n$$ $$a_n=A\left(\frac{1+\sqrt{5}}{2}\right)^n+B\left(\frac{1-\sqrt{5}}{2}\right)^n$$ You can use whatever names you like for the coefficients.
Why is this the general solution? We’ll consider that later.
6. Use the initial conditions to set up equations in the unknown constants k(1) and k(2). 7. Solve those simultaneous linear equations and find the values of k(1) and k(2). 8. Write the explicit solution of the recurrence satisfying the initial conditions.
The initial conditions are \(a_1=2,a_2=3\), so we write these equations: $$a_1=A\left(\frac{1+\sqrt{5}}{2}\right)^1+B\left(\frac{1-\sqrt{5}}{2}\right)^1=2\\ a_2=A\left(\frac{1+\sqrt{5}}{2}\right)^2+B\left(\frac{1-\sqrt{5}}{2}\right)^2=3$$
These simplify to $$A\left(\frac{1+\sqrt{5}}{2}\right)+B\left(\frac{1-\sqrt{5}}{2}\right)=2\\ A\left(\frac{3+\sqrt{5}}{2}\right)+B\left(\frac{3-\sqrt{5}}{2}\right)=3$$
Solving, which takes a while, we find that \(A=\frac{5+3\sqrt{5}}{10}, B=\frac{5-3\sqrt{5}}{10}\), so our solution is $$a_n=\frac{5+3\sqrt{5}}{10}\left(\frac{1+\sqrt{5}}{2}\right)^n+\frac{5-3\sqrt{5}}{10}\left(\frac{1-\sqrt{5}}{2}\right)^n$$
To check, let’s find \(a_3\), which should be \(a_2+a_1=3+2=5\): $$a_3=\frac{5+3\sqrt{5}}{10}\left(\frac{1+\sqrt{5}}{2}\right)^3+\frac{5-3\sqrt{5}}{10}\left(\frac{1-\sqrt{5}}{2}\right)^3\\= \frac{5+3\sqrt{5}}{10}\left(2+\sqrt{5}\right)+\frac{5-3\sqrt{5}}{10}\left(2-\sqrt{5}\right)\\= \frac{25+11\sqrt{5}}{10}+\frac{25-11\sqrt{5}}{10}\\= \frac{50}{10}=5$$
Problem 1: counting bitstrings without double zeros
Next, Doctor Anthony answered each specific problem. First, the one where we just have to write a recurrence:
1. Find a recurrence relation for the number of bit strings of length n that do not contain a pair of consecutive zeroes. What are the initial conditions?
Let u(n) be the number of strings of length n that DO NOT contain consecutive 0's.
Let u(n0) = number of strings that start with 0
u(n1) = number of strings that start with 1
Then u(n) = u(n0) + u(n1)
Let’s first clarify the problem. For \(n=1\), the only bit strings of that length are 0 and 1; neither contains consecutive zeros, so \(u_1=2\). For \(n=2\), the bit strings of that length are 00, 01, 10, and 11; the last three contain no consecutive zeros, so \(u_2=3\).
To make a recursive description, we want to relate each term to preceding terms. Consider \(n=3\), where we have these bit strings, with those containing two zeros struck out: 000, 001, 010, 011, 100, 101, 110, 111, so that \(u_3=5\). His suggestion is to separate these into those starting with 0 (010, 011), whose count he calls \(u_{n0}\), and those starting with 1 (101, 110, 111), whose count he calls \(u_{n1}\). The former, to avoid a double 0, must start with 01, followed by any bit string with \(n=1\); so there are \(u_1\) of these. The latter may have anything following the 1, namely \(u_2\) bit strings.
That is what he explains next:
If the first number in the string is 1 then the string can be completed in u(n-1) ways. So u(n1) = u(n-1).
If the first number in the string is 0, then the second number must be 1. So u(n0) = u((n-1)1)
= u(n-2)
Therefore u(n) = u(n0) + u(n1) becomes
u(n) = u(n-2) + u(n-1)
Note that this is the recurrence relation for the number of strings that DO NOT have consecutive 0's.
This is the familiar recurrence relation for the Fibonacci series.
Whereas the Fibonacci sequence starts with \(F_0=F_1=1\), this starts with \(u_1=F_2\), continuing \(\{2, 3, 5, 8,\dots\}\). This recurrence is the one we solved above.
Problem 2: solving a recurrence with a double root
Next, we actually solve a recurrence, following the method described above:
2. Solve the following recurrence relations together with the initial conditions given:
a_n = 4 a_{n-1} - 4 a_{n-2}; a_0 = 6 a_1 = 8 a(n) = 4.a(n-1) - 4.a(n-2) a(n) - 4.a(n-1) + 4.a(n-2) = 0 The auxiliary equation is x^2 - 4x + 4 = 0 (x-2)^2 = 0
With the double root the solution is a(n) = (A + B.n)2^n a0 = 6, a1 = 8 6 = A 8 = (6 + B)2 so B+6 = 4 and B = -2 Therefore a(n) = (6 - 2n)2^n
He uses the term “auxiliary equation” instead of “characteristic polynomial”. This example, unlike the first, has a double root, so that instead of two identical terms, we force the terms to be different by multiplying by n. We’ll see more specifically why later.
Checking the answer, $$a_0=(6-2\cdot0)2^0=6\\ a_1=(6-2\cdot1)2^1=8\\ a_2=(6-2\cdot2)2^2=8$$
and the recurrence gives $$a_2=4a_1-4a_0=4\cdot8-4\cdot6=8$$
Problem 3: Making and solving a recurrence with distinct roots
Next, we translate words to a recurrence, and solve:
3. Consider the sequence 0, 1, 1/2, 3/4, 5/8, 11/16, ..., in which each term is the average of the previous two terms (eg., the next term will be 1/2(5/8 + 11/16) = 21/32. Find the formula for the general term using a recurrence equation. Make sure you state the initial condition. Then give a formula for the general term using a non-recursive equation by solving the above recurrence equation. u(n) = (1/2)[u(n-1) + u(n-2)] 2.u(n) - u(n-1) - u(n-2) = 0 The auxiliary equation is 2x^2 - x - 1 = 0 (2x+1)(x-1) = 0 x=1 or x = -1/2 So u(n) = A + B(-1/2)^n 0 = A + B so A = -B 1 = A - B/2 1 = -B - B/2 1 = -3B/2 therefore B = -2/3 then A = 2/3 u(n) = 2/3 - (2/3)(-1/2)^n check:
u(5) = (2/3)[1 - (-1/2)^5] = (2/3)[1 + 1/32] = (2/3)[33/32] = 11/16 which is correct.
Here the roots were \(1\) and \(-\frac{1}{2}\), so the general form is $$u_n=A(1)^n+B\left(-\frac{1}{2}\right)^n\\= \frac{2}{3}-\frac{2}{3}\left(-\frac{1}{2}\right)^n$$
Why the method works
The next question, from three days earlier in 2001, asks where this method comes from:
Non-Recursive Formula
I want to know the non-recursive formula of the nth number in the general Fibonacci sequence. The general Fibonacci sequence is: F(n+k) = a1*F(n+k-1)+a2*F(n+k-2)+...+ak*F(n) I know that we can get it by solving this equation: x^k-a1*x^(k-1)-...-ak = 0 Could you explain why we come to this conclusion? Thanks. Dang Nguyen Duc
What he calls the general Fibonacci sequence is more general than what we looked at in the post Generalizing and Summing the Fibonacci Sequence; it’s really any linear homogeneous recurrence. He has learned the method, but wants to know where the magic came from.
Doctor Rob answered again, and started with the first-order case:
If k = 1, you would have
F(n+1) = a1*F(n).
The solution to this is ("obviously")
F(n) = c1*a1^n,
for any constant c1. Also a1 is a root of the polynomial equation x - a1 = 0.
Can you see how this is “obvious”? Take an example. If we know that $$F_{n+1}=3F_n$$ then we are just repeatedly multiplying by 3, and each term is a power of 3 times whatever the first term was. If \(F_0=A\), then $$F_1=3F_0=3A\\F_2=3F_1=3(3A)=3^2A\\F_3=3F_2=3(3^2A)=3^3A\\…$$
But this result is just an example of the method we’re justifying, since our equation \(F_{n+1}=3F_n\) can be written as \(F_{n+1}-3F_n=0\), leading to the characteristic equation \(x-3=0\), whose root is the base we used.
How about second-order recurrences? This time we’ll start with an explicit formula and turn it into a recurrence, much as we did in the first question above:
Now suppose that
F(n) = c1*r^n + c2*s^n,
where r and s are not equal. What equation would this satisfy?
F(n+2) = c1*r^(n+2) + c2*s^(n+2)
= c1*r^(n+1)*r + c2*s^(n+1)*s
= c1*r^(n+1)*(r+s) + c1*(-r*s)*r^n +
c2*s^(n+1)*(r+s) + c2*(-r*s)*s^n
= (r+s)*F(n+1) + (-r*s)*F(n+2).
The key step here rewrites each term of the sum into a combination of lower powers like this: $$r^{n+1}r=r^{n+1}(r+s-s)=r^{n+1}(r+s)-sr^{n+1}=r^{n+1}(r+s)-rsr^n$$ and then puts them together to make a combination of previous terms.
Thus if we set r + s = a1, -r*s = a2, then F(n) will satisfy the recursion F(n+2) = a1*F(n+1) + a2*F(n).
But if we started with this recursion, how would we reconstruct the bases r and s?
Now r and s are the roots of the equation (x-r)*(x-s) = 0, x^2 - (r+s)*x - (-r*s) = 0, x^2 - a1*x - a2 = 0. Thus the solution of the recursion F(n+2) = a1*F(n+1) + a2*F(n) is given by F(n) = c1*r^n + c2*s^n, for any constants c1 and c2, where r and s are distinct roots of the polynomial equation x^2 - a1*x - a2 = 0.
You may be dissatisfied by the fact that we worked backward from the solution to the problem; but that’s how many facts work: We recognize the problem as something we’ve seen before.
The constants c1 and c2 are determined by the initial conditions on F(n). The same situation holds for a linear combination of k > 2 unequal exponential functions, except the degree of the equation is k. The coefficients of the equation are just the ones appearing in the recursion. (One has to make an adjustment to handle the case when the polynomial equation has repeated roots.)
As we’ve seen the adjustment is to replace the second term in the solution with n times the first term. Why? I suspect that someone first tried out various forms of explicit sequences and saw that this one works; he may have just been trying different variations to see which might work, and having found one, told others! Mathematicians can be like bees searching for flowers, going back and announcing their find to the hive.
An application
Finally, lets look at an application of these ideas, from 2000:
Finding an Explicit Formula for a Recursive Series
My question is as follows: There was a man who couldn't decide in which direction he wanted to walk, but there was a method in his indecision. He started off walking a mile west from his home. Then he changed his mind and walked back east one half the distance. He then changed his mind again and walked west again half of the distance he had just walked, and so on. (1, 1/2, 1/4, 1/8, 1/16, ...) The question is, how far away did he end up from his home? The distance the man is from home each time he changes his mind can be thought of as terms in an alternating sequence. The first few terms are: for n = 1: 1 mile for n = 2: 1/2 mile (1 - 1/2) for n = 3: 3/4 mile (1/2 + 1/4) for n = 4: 5/8 mile (3/4 - 1/8) for n = 5: 11/16 mile (5/8 + 1/16) for n = 6: 21/32 mile (5/8 - 1/32) for n = 7: 43/64 mile (21/32 + 1/64) for n = 8: 85/128 mile (43/64 - 1/128) for n = 9: 171/256 mile (85/128 + 1/256) and so on. The denominators of these distances are 2^(n-1). But the numerators have got me. I know that the terms in the numerator can be represented by the recursive sequence: f_n = f_(n-1) + 2*f_(n-2) This is close to the recursively defined Fibonacci sequence: f_n = f_(n-1) + f_(n-2) I saw another question on your wonderful Web site where the explicit formula was found from the auxiliary equation k^2 = k + 1 f_n = phi^n/sqrt(5) - (1-phi)^n/sqrt(5) where phi is the golden ratio. (I don't know how to do 2nd order differential equations.) So I need a formula to generate the nth term for the numerators:
1, 1, 3, 5, 11, 21, 43, 85, 171, ..., n. The limit as n goes to infinity of (?)/2^n should be the answer... right? Respectfully, Jacob
He has created a recurrence that looks a lot like Fibonacci.
Doctor Anthony replied:
To find the nth term for the recurrence relation
u(n+2) - u(n+1) - 2u(n) = 0
we consider the auxiliary equation
x^2 - x - 2 = 0
(x-2)(x+1) = 0
with roots -1 and 2.
These are considerably simpler than Fibonacci!
We then can say that
u(n) = A(-1)^n + B(2^n)
u(1) = 1 so 1 = -A + 2B
u(2) = 1 so 1 = A + 4B
------------- adding
2 = 6B
and so
B = 1/3
and
A = 1 - 4B = 1 - 4/3 = -1/3
Therefore
u(n) = (-1/3)(-1)^n + (1/3)(2^n)
This is the formula for the numerators in the problem.
Check n = 3: u(3) = +1/3 + 8/3 = 9/3 = 3 (okay)
Check n = 7: u(7) = +1/3 + 128/3 = 129/3 = 43 (okay)
Check n = 8: u(8) = -1/3 + 256/3 = 255/3 = 85 (okay)
So our formula is giving the correct sequence. We can be certain that the formula for u(n) is
u(n) = (-1/3)(-1)^n + (1/3)(2^n)
Returning to the original problem, the sequence of distances is $$a_n=\frac{\frac{1}{3}2^n-\frac{1}{3}(-1)^n}{2^{n-1}}\\=\frac{2^n-(-1)^n}{3\cdot2^{n-1}}$$ In the limit, as n approaches infinity, we have $$\lim_{n\to\infty}\frac{2^n-(-1)^n}{3\cdot2^{n-1}}=\lim_{n\to\infty}\frac{2-\left(\frac{-1}{2^{n-1}}\right)^n}{3}=\frac{2}{3}$$ which agrees with the terms Jacob had listed.
Pingback: Introduction to Non-homogeneous Recurrences – The Math Doctors
Pingback: A Challenging Homogeneous Second-Order Recurrence – The Math Doctors