Last week we looked at Ask Dr. Math questions about homogeneous linear recurrences; this time we’ll see some on simple (first-order) non-homogeneous recurrences, which will bring us back to the topic two weeks ago, when we looked at the examples of this type that a student had the most trouble with. This will be an introduction to that, touching only on the simplest non-homogeneous terms, and also demonstrating a different approach to these, iteration.
A constant forcing term
We’ll start with a question, from 2004, looking for a method for a relatively simple case:
Nonhomogeneous Linear Recurrence Relations Given a recursive formula: a(n+1) = a(n) + (a(n) - b)*t, where b is a known constant and a(1) is also known, I am trying to find the explicit formula like y = ????? * t^n. I have tried to look for the "fixed point" which is what a(n) would be if a(n+1) = a(n), a(n) = a(n) + (a(n) - b)*t However this doesn't seem to give anything useful: 0 = (a(n) - b)*t Any help would be appreciated.
We haven’t been given specific values for \(b\), \(t\), and \(a_1\), which would make this problem more concrete, so I’ll follow along with, say, \(b=2\), \(t=3\), and \(a_1=5\) making the recurrence $$a_{n+1}=a_n+3(a_n-2)$$
Here are the first few terms of this sequence:
$$a_1=5\\ a_2=a_1+3(a_1-2)=5+3(5-2)=14\\ a_3=a_2+3(a_2-2)=14+3(14-2)=50\\ a_4=a_3+3(a_3-2)=50+3(50-2)=194$$
The “fixed point” (that is, the starting value that would cause the sequence to be constant) will satisfy $$a=a+3(a-2)\\a=4a-6\\a=2$$ This is simply b, and we’ll see that it is in fact useful. It’s interesting that the problem is given in a form that highlights this fixed point; if we write it as \(a_{n+1}-a_n=t(a_n-b)\), we can see that the length of each step is t times the distance from b. If that distance is initially zero, it will stay there.
Doctor Vogler answered, teaching the standard approach to such a problem:
Hi Raul, Thanks for writing to Dr. Math. What you have is a nonhomogeneous linear recurrence relation. You solve those in two parts. First you write it as a(n+1) - (t+1)*a(n) = -b*t to separate the homogeneous part (on the left) from the leftover "forcing" term (on the right). Now you find the general solution of the homogeneous part on the left by solving the equation x^(n+1) - (t+1)*x^n = 0 and you get x = t+1, which means you have the general solution to the homogeneous part a(n) = C*(t+1)^n, where C is some (as yet unknown) constant. (You'll notice that you can substitute this into your equation and get a solution when b = 0, when it is homogeneous.)
This first part is what we learned last week. For our numbers, the rewritten recurrence looks like $$a_{n+1}-4a_n=-6$$ so that the homogeneous equation is $$a_{n+1}-4a_n=0$$ whose characteristic (or auxiliary) equation is $$x-4=0$$ whose root is 4. (He wrote the equation in a different form than this, which is what we used last week.) So our general solution is $$a_n=C\cdot4^n$$ This is, indeed, a solution of the homogeneous equation $$a_{n+1}-4a_n=0$$ because it is true that $$C\cdot4^{n+1}-4C\cdot4^n=4C\cdot4^n-4C\cdot4^n=0$$
Looking back at the question, we see that Raul expected a term in the solution to have the form \(Ct^n\) rather than \(C(t+1)^n\).
Next you find a single particular solution by choosing a likely form
a(n) = constant = k
(since the forcing term is a constant) and seeing what the constant has to be.
a(n+1) - (t+1)*a(n) = -b*t
k - (t+1)*k = -b*t
-t*k = -b*t
k = b
which is actually the fixed point that you were looking for before. You had gotten
0 = (a(n) - b)*t
and then stopped. But if you divide by t and solve for a(n), you find that the fixed point is at a(n) = b (unless t = 0, in which case every point is fixed).
We’ll see soon why this form of the particular solution is “likely”.
Our specific recurrence, $$a_{n+1}-4a_n=-6$$ has constant forcing (non-homogeneous) term \(-6\), and taking the particular solution as \(a_n=k\) we get $$k-4k=-6\\-3k=-6\\k=2$$
This work is, of course, the same as the work above to find the fixed point. What do we do with it?
Then the general solution is the sum of the general homogeneous solution and the particular solution a(n) = C*(t+1)^n + b and we choose C according to what a(1) is. Since a(1) = C*(t+1) + b, we must have C = (a(1) - b)/(t+1), and therefore a(n) = (a(1) - b)*(t+1)^(n-1) + b.
In our example, we add the homogeneous solution \(h_n=C\cdot4^n\) and the particular solution \(p_n=2\) to get the general solution $$a_n=2+C\cdot4^n$$ To find \(C\), we use our initial value \(a_1=5\): $$a_1=2+C\cdot4^1=5\\2+4C=5\\C=\frac{3}{4}$$
So our final answer is $$a_n=2+\frac{3}{4}\cdot4^n=2+3\cdot4^{n-1}$$
Checking, $$a_1=2+3\cdot4^{1-1}=5\\a_2=2+3\cdot4^{2-1}=14\\a_3=2+3\cdot4^{3-1}=50\\a_4=2+3\cdot4^{4-1}=194$$
which agrees with the terms we got recursively.
But why?
Raul wrote back, asking about the reason for choosing the particular solution as a constant:
Thank you very much. I could follow everything except for the forcing term. Why is a(n+1) = a(n) = constant = k?
From your formulas:
a(n+1) - (t+1)*a(n) = -b*t
k - (t+1)*k = -b*t
Would you believe … we guess? But it’s a little more than that.
Doctor Vogler replied:
Hi Raul, When you want to find a "particular" solution to a nonhomogeneous linear recurrence relation, you generally guess the form of the solution, pack it full of unknowns, and then solve for what the unknowns need to be. The idea of a "particular" solution is that you only need any one solution, since every other solution will be your solution plus a solution to the homogeneous recurrence (this is not hard to prove; can you prove it?). So you figure what is my solution most probably going to look like, and you try it.
“Pack it full of unknowns” is a nice description; what we are doing is called the “method of undetermined coefficients”.
Let’s prove this claim that the sum of general and particular will always be a solution:
Suppose we have the general solution \(h_n\) of the homogeneous equation $$c_nh_n+c_{n-1}h_{n-1}+\dots+c_{n-k}h_{n-k}=0$$ and a particular solution \(p_n\) of the non-homogeneous equation $$c_np_n+c_{n-1}p_{n-1}+\dots+c_{n-k}p_{n-k}=f(n)$$ Then if we define \(a_n=h_n+p_n\), we find that $$c_na_n+c_{n-1}a_{n-1}+\dots+c_{n-k}a_{n-k}\\=c_n(h_n+p_n)+c_{n-1}(h_{n-1}+p_{n-1})+\dots+c_{n-k}(h_{n-k}+p_{n-k})\\=(c_nh_n+c_{n-1}h_{n-1}+\dots+c_{n-k}h_{n-k})+(c_np_n+c_{n-1}p_{n-1}+\dots+c_{n-k}p_{n-k})\\=0+f(n)=f(n)$$
(Properly speaking, what we need to prove is that every solution has this form, but I will not go that far.)
Really, this choice of form comes from experience (or lists of solution forms like we saw two weeks ago, which come from others’ experience); but it does end up feeling intuitive:
For example, if I wanted a particular solution to a(n+2) + 2a(n+1) + 3a(n) = n^2 + 2n + 3, then I would probably guess that some polynomial of degree no more than 2 will work, so I try a(n) = a*n^2 + b*n + c and then I substitute that into my formula and solve for the coefficients a, b, and c. There are several techniques to picking the form of your particular solution, such as: If some expression appears in the "forcing term," then put it in the particular solution, multiplied by a constant. If some polynomial (like n^3) appears in the forcing term (even if multiplied by something nonpolynomial), then don't just include that term but also all terms of lower degree (a*n^3 + b*n^2 + c*n + d). If one of these rules says to include a certain term, but that term already appears in the general solution to the homogeneous problem, then multiply the term by n. Sometimes none of these will give you a particular solution, but they work well for most simple examples.
To get a polynomial from a recurrence, you put in a polynomial (because all it does is add and multiply, which results in a new polynomial). Similarly, to get an exponential, you put in an exponential, and so on. If you aren’t sure, just try it and see if it works. Two weeks ago we saw a table listing such “guesses”.
A quadratic forcing term … and iteration
The next question, from 1999, demonstrates the polynomial case:
Finding a Non-Recursive Formula I cannot for the life of me see the pattern in this problem based on iteration. I understand that once you find a pattern in the solutions to the recurrence relation, you guess a formula to solve. Am I not seeing something? Because I can't find a pattern. Please help. recurrence relation: s_n = - [s_(n-1)] - n^2 initial condition: s_0 = 3 s_1 = -4 s_2 = 0 s_3 = -9 s_4 = -7 s_5 = -18
The iteration method is different from what we have been doing; as he says, it involves guessing (more seriously than the guessing involved in choosing a trial solution!), so we tend to see it as an initial method. But let me demonstrate it here.
We have $$s_n=-s_{n-1}-n^2$$ If we start at \(s_0=3\) and apply the recursion repeatedly (iteratively), we get $$s_1=-s_0-1^2=-3-1=-4\\s_2=-s_1-2^2=4-4=0\\s_3=-s_2-3^2=0-9=-9$$ That just shows us the values of the first few terms, from which we can’t see a pattern. But if we do this without evaluation, leaving all the operations visible, it looks like this:$$s_1=-s_0-1^2=-3-1^2\\s_2=-s_1-2^2=-(-3-1^2)-2^2=3+1^2-2^2\\s_3=-s_2-3^2=-(3+1^2-2^2)-3^2=-3-1^2+2^2-3^2$$ We can see a pattern, an alternating sum of squares; this suggests the answer might be different for even and odd n (which we may be able to combine into one later). For even \(n=2k\), $$s_{2k}=3+(1^2-2^2)+(3^2-4^2)+\dots+((2k-1)^2-(2k)^2)\\=3-[(2^2-1^2)+(4^2-3^2)+\dots+((2k)^2-(2k-1)^2)]\\=3-[(2-1)(2+1)+(4-3)(4+3)+\dots+((2k-(2k-1))(2k+(2k-1))]\\=3-[3+7+\dots+(4k-1)]=3-\frac{3+4k-1}{2}k\\=3-k(2k+1)=3-\frac{n(n+1)}{2}$$ using the formula for the sum of an arithmetic series.
Similarly, for odd \(n=2k+1\). $$s_{2k+1}=-3+(2^2-1^2)+(4^2-3^2)+\dots+((2k)^2-(2k-1)^2)-(2k+1)^2\\=-3+(2-1)(2+1)+(4-3)(4+3)+\dots+((2k-(2k-1))(2k+(2k-1))-(2k+1)^2\\=-3+(3+7+\dots+(4k-1))-(2k+1)^2\\=-3+\frac{3+4k-1}{2}k-(2k+1)^2\\=-3+k(2k+1)-(2k+1)^2=-3+\frac{n(n-1)}{2}-n^2\\=-3+\frac{n^2-n-2n^2}{2}=-3-\frac{n(n+1)}{2}$$
This can be turned into a single formula that we’ll see later. But it was a lot of work, and not all problems can be solved this way at all. So we’d like another method.
Doctor Anthony answered, using the method we’ve been learning:
The recurrence relation is u(n) + u(n-1) = -n^2 Let u(r) = v(r) + w(r) where v(r) is solution of v(r) + v(r-1) = 0 So we solve x + 1 = 0 x= -1 and v(r) = A.(-1)^r and we use a trial solution w(r) = a.r^2 + b.r
So the root of the characteristic equation, \(x+1=0\), \(x=-1\), leads to the homogeneous solution \(u_n=A(-1)^n\); the non-homogeneous term is \(-n^2\), a polynomial of degree 2, so we use a polynomial of degree 2 as our trial solution, which could require \(w(n)=an^2+bn+c\). Why did he not include the constant term? Let’s do so as we follow along, and see what happens!
Substituting into the equation
a.r^2 + b.r + a(r-1)^2 + b(r-1) = -r^2
a.r^2 + b.r + a(r^2 - 2r + 1) + b(r-1) = -r^2
2a.r^2 + r(2b-2a) + a-b = -r^2
2a.r^2 + 2r(b-a) + a-b = -r^2
comparing coefficients of r on both sides we require a = -1/2, b = a = -1/2
and so w(r) = -(1/2)[r^2 + r]
If we do the same work including the constant term, here is what we see: $$s_n+s_{n-1}=-n^2\\\left(an^2+bn+c)+(a(n-1)^2+b(n-1)+c\right)=-n^2\\an^2+bn+c+a\left(n^2-2n+1\right)+b(n-1)+c=-n^2\\an^2+bn+c+an^2-2an+a+bn-b+c=-n^2\\2an^2-2an+a+2bn-b+2c=-n^2\\2an^2+2(b-a)n+(a-b+2c)=(-1)n^2+0n+0$$ To make this true for all n, we need $$2a=-1\\2(b-a)=0\\a-b+2c=0$$ So \(a=-\frac{1}{2}\), \(b=a=-\frac{1}{2}\), and \(c=\frac{b-a}{2}=0\).
Here we had three equations in three unknowns, which worked. He had three equations in only two unknowns, which could have been inconsistent; if they had been, he would have added the third term as we did. I’m not sure whether he just knew his choice would work, or was lucky!
Now that we have a particular solution, we can add it to the homogeneous solution and find the other constant:
Therefore the general solution is u(n) = A(-1)^n - (1/2)[n^2 + n] and the initial condition is u(0) = 3 so A = 3
Here is the work for applying the initial value: $$u_n=A(-1)^n-\frac{1}{2}(n^2+n)\\u_0=A(-1)^0-\frac{1}{2}(0^2+0)\\3=A$$ So our final answer is $$u_n=3(-1)^n-\frac{1}{2}(n^2+n)$$
We get
u(n) = 3(-1)^n - (1/2)[n^2 + n]
Check with n = 5
u(5) = -3 - (1/2)[25 + 5]
= -3 - (1/2)(30)
= -3 - 15
= -18 which checks.
This solution is equivalent to what we got by iteration, but this is more straightforward.
Using iteration for an application
I’d like to close with an application problem for which we used what amounts to the iteration method, because it seemed suitable for the “patient”. The question is from 2003:
Deriving any Exponential Formula from a Pattern I write a lot of software, and often I identify growth/decay patterns that could easily be represented as exponential formulas. But I always struggle with deriving them and end up turning to other people for help. I would like to know the standard process for deriving an exponential formula. For example, I wrote a simple function which fades an image. The transparency of the image is a percent, where 100 is opaque. The simple formula I wrote runs in a loop, where: t = Target transparency (or alpha) c = Current transparency s = Speed (or rate) of fade F = final value The formula is: F = c + ((t - c)/s) I think that in the second iteration it would look like: F = (c + ((t - c)/s)) + ((t - (c + ((t - c)/s)))/s) Please help!
Lon is starting to use the iteration method for what amounts to a linear recurrence. I picked up on his start, first cleaning the problem up to make it easier to work with:
Hi, Lon. As I understand it, your "F" means the next transparency, not really the "final" value; you could write the iteration as c[n+1] = c[n] + (t - c[n])/s This can be simplified to c[n+1] = (1 - 1/s)c[n] + t/s If we set A = 1 - 1/s and B = t/s this becomes c[n+1] = Ac[n] + B
This looks more like the others we’ve worked with here. I now iterated it, as before simplifying at each step to make a pattern visible:
Repeating this, starting from a given the first value c[0] = f, we have c[0] = f c[1] = Af + B c[2] = A(Af + B) + B = A^2 f + (A+1)B c[3] = A(A^2 f + (A + 1)B)+B = A^3 f + (A^2 + A + 1)B c[4] = A(A^3 f + (A^2 + A + 1)B)+B = A^4 f + (A^3 + A^2 + A + 1)B Clearly (I won't bother to prove it) c[n] = A^n f + (1 + A + A^2 + ... + A^(n-1))B
Last time we found ourselves with an arithmetic series to add; this time it’s a geometric series!
The geometric series can be summed using a familiar formula, giving us
c[n] = A^n f + B(A^n - 1)/(A - 1)
= A^n(f + B/(A - 1)) - B/(A - 1)
As expected, we have an exponential function with a constant term. Now we can put back the original variables:
Replacing A and B with their values, B/(A-1) = -t, and c[n] = (1 - 1/s)^n (f - t) + t This clearly does what you want: it approaches t asymptotically (never actually getting there) in an exponential manner, starting at f. Your "speed" s, of course, is not really a speed of approach, but the reciprocal of the ratio by which the deviation from the target is decreased at each step. Setting s = 1/r, c[n] = t + (1-r)^n (f - t) That should be the formula you want. And normally we would start with this, and form an iterative approach from it, rather than derive it from the iterative formula the way I have.
I changed to the new variable \(r=\frac{1}{s}\) merely so that we had an actual rate in the formula. You may recognize this as looking much like Newton’s Law of Cooling.
Lon replied:
Dr. Peterson, Thank you so much for that awesome derivation! I see very clearly how you derived it, and I think it will solve my current dilemma. However, the general process is still not clear to me. For example, how did you know to sub out the (1 - 1/s)and the (t/s) ?
I explained:
Hi, Lon. I defined temporary variables A and B merely to make the equation look simpler and allow me to (a) see more clearly what had to be done, and (b) avoid typing too many complicated expressions. The work could have been done without that substitution, but when you have done this sort of algebra enough you learn how to save work.
This comes from lots of experience!
But now I took the chance to show a slightly nicer way I wished I’d done it the first time:
Also, my derivation could have been done more simply if I had chosen to use more insight into the problem (including your own insight that it is exponential) from the beginning, rather than just mechanically working out what successive iterations would do. Here's an alternative:
Your iterative formula was:
F = c + (t - c)/s
I write this iteratively as
c[n+1] = c[n] + (t - c[n])/s
Your purpose here is to reduce the distance from t to c by the same ratio at each step, which is what makes this exponential. We can rewrite the equation to emphasize this:
t - c[n+1] = t - c[n] - (t - c[n])/s
= (t - c[n])(1 - 1/s)
So the difference t - c is multiplied by 1 - 1/s at each iteration.
This time, explicitly expecting an equation of this form (much as we chose a form in the standard method, from experience), I wrote this as repeated multiplication by what I above called \(1-r\).
Therefore if we temporarily define a new variable d[n] = t - c[n] our iteration is d[n+1] = d[n] (1 - 1/s) and we can easily see that d[n] = d[0] (1 - 1/s)^n because we are multiplying by the same factor repeatedly. Putting this back in terms of c, c[n] = t - d[n] = t - (t - c[0])(1 - 1/s)^n That is the desired formula, equivalent to what I gave you last time.
Finding multiple ways to solve a problem can be good for the mind. To see an example where a Math Doctor not already familiar with these problems worked out his own way, see
Recursion, and Closure