## Answers to selected in Section 5.2

1. (b) does not have constant coefficients and (d) is not homogeneous (because of the "+2"). 3. (a) a_n=2a_(n-1) and a_0=3

Characteristic equation: r-2=0 (degree 1). r=2 is only solution to characteristic equation. So solutions to recurrence have the form { A*2^n}. Initial condition is a_0=3, so solve A*2^0=3, for A=3.

(b) a_n=a_(n-1) and a_0=2

Characteristic equation: r-1=0, so r=1. Solve A*1^0 = 2, for A=2. Hence solution to recurrence: { 2 * 1^n } (obviously the same as a_n = 2 for all n).

(c) a_n=5a_(n-1)-6a_(n-2) a_0=1 a_1=0

r^2-5r + 6 (darn, they were easy till now). Solutions or roots: try to factor: r^2-5r+6=(r-3)(r-2). So the roots are r=3 and r=2. Choosing A and B to have A+B=a_0=1, and A*3^1 + B*2^1 =0. We could just memorize the formula in the theorem but usually it's pretty easy to solve these two equations in two unknowns (remember it depended on having two distinct roots).

Add -2 times first equation to the second equation to get rid of the B: A(-2+3) = -2(1) + 0, so A = -2. A+B=1, so B=3. Solution to recurrence: { (-2)*3^n + 3*2^n }.

(d) a_n=4a_(n-1)-4a_(n-2) a_0=6, a_1=8

r^2 - 4r + 4 =0 factors as (r-2)^2 = 0, i.e. we do not have distinct roots. Our solution will thus be of the form A 2^n + B*n*2^n for some A and B. Substitute n=0, so a_0 = 6 = A*2^0 + B*0*2^0, hence A=6. Then substitute n=1: a_1=8=A*2^1 + B*1*2^1 = 6*2 + B*2; or 8=12 + 2B, hence B=-2. { 6 * 2^n - 2*n*2^n } is the solution. (e) a_n=-4a_(n-1) -4a_(n-2) a_0=0 a_1=1

r^2+4r+4=0. Factoring: (r+2)^2=0, hence r=-2 is the repeated root. a_0 = 0 = A, and a_1 = 1 = A*(-2)^1 + B*1*(-2)^1, solve for B, (using that A=0), B=-1/2. So { (-1/2) * n * (-2)^n }. This can be simplified by writing (-2)^n = -2 * (-2)^(n-1) and cancelling the (-1/2).

(f) a_n=4a_(n-2) a_0=0 a_1=4

r^2-4=0. Thus r=2 and r=-2 are (distinct) roots. a_0=0=A+B, and a_1 = 4 = A*2 + B*(-2). Double the first and add it to the second (to get rid of the B): 4 = 2A + A*2 = 4A, hence A=1. Therefore B=-1 since A+B=0. Solution: { 2^n + (-1) * (-2)^n }

(g) a_n=a_(n-2)/4 a_0=1 a_1=0

r^2 - (1/4)=0, i.e. r^2=1/4, hence r=1/2 or r=-1/2. Similar stuff: a_0=A+B and a_1=A*(1/2) + B*(-1/2), Double the second and add to the first: 1=A+A, So A=1/2. Since A+B=1, we get that B=1/2. So { (1/2)*(1/2)^n + (1/2) * (-1/2)^n }. Can just simplify to get answer in book.

7. 2xn rectangle is tiled with 1x2 and 2x2 pieces.

First set up recurrence relation, initial conditions, then solve. We have a tower which is 2 units wide and n units tall.

We can draw picture but I think we are supposed to realize that we can only start at the botton and put either a 2x2 piece (and thus continue to tile a 2x(n-2) tower in any of the a_(n-2) ways). Or we could put a a 1x2 piece in some orientation, i.e. either as a 1x2 or as a 2x1 piece. If we put it as a 2x1 piece (long side horizontal) we would continue in any of the a_(n-1) ways. If we put it vertically, we'd have to put another right beside it and then continue in any of the a_(n-2) ways (remember we are not counting how many pieces we use just how many ways to do it).

Our recurrence then is a_n = a_(n-1) + 2 * a_(n-2).

Initial conditions: a_0=1, a_1=1, a_2=3 (note that a_2 can be computed with the recurrence relation or just thought about directly to reassure us that our recurrence relation is OK).

r^2-r-2=0 factors as (r-2)(r+1)=0, thus r=2 and r=-1 are the roots. Again we need A+B=a_0=1 and A*(2) + B*(-1)=1. Just add the two equations together (if it's easier to get rid of the A that's OK too): so this give us 3A=2, hence A=2/3 and B will have to be 1/3.

The solution then is { (2/3) 2^n + (1/3) (-1)^n }

8. lobsters in year n is average of previous two years (L_n). 100,000 and 300,000 in years 1 and 2.

Read it again: Ah, L_n = (L_(n-1)+L_(n-2))/2 = the average of the two previous years. r^2-1/2 r - 1/2 =0. Maybe I can factor it, I just don't know right now but let me remind you of the quadratic formula: (-b +/- SQRT(b^2 - 4ac) )/2a are the roots of ax^2+bx+c=0. So we have a=1, b=-1/2 and c=-1/2. Substitute into quadratic formula: [1/2 +/- SQRT( 1/4 + 2 ) ] / 2. OK I could have factored it pretty easily: root one is take the plus and root two is take the minus.
r_1 = ( 1 + 3 ) / 4 = 1 and r_2 = ( 1 - 3 ) / 4 = -1/2.

We really do go through exactly the same algebraic process every time we solve one of the quadratic recurrences: A = (a_1 - a_0 r_2)/(r_1-r_2) and B = (a_0 r_1 - a_1)/(r_1-r_2). So go ahead and plug in the values for a_0=100,000, a_1=300,000, r_1=1, r_2=-1/2.

A = (300,000 - 100,000*(-1/2))/(3/2) = 2/3 * 350,000 and B = (100,000 - 300,000) / (3/2) = 2/3 * (-200,000).

{ 2/3 * 350,000 + 2/3 * (-200,000) * (-1/2)^n } (Interesting looking). What happens as n goes to infinity, did you expect that?

13. a_n=7a_(n-2)+6a_(n-3) with a_0=9, a_1=10, a_2=32

r^3-7r-6=0. No r^2 term since there's no a_(n-1) term and we have a degree 3 (linear homogeneous) recurrence relation. Roots?

For polynomials of degree 2 we always have the quadratic formula. For higher degree we can just try some small values, if we find one, we can factor it out and start again. In the real world we'd use a computer algebra package. For degree 3 or higher we will make sure you can find them.

Try r=-1. We get (-1)^3-7(-1)-6=-1+7-6=0. So good, r=-1 is a root. That means that (r+1) is a factor of r^3-7r-6. Compute a,b,c so that (r+1)(ar^2+br+c)=r^3-7r-6. Clearly a=1 so that r*ar^2 gives us the only possible r^3 term. For the r^2 terms (which should be 0), we have 1*ar^2=r^2 and r*br, so b has to be -1. Also, c is clearly -6 by looking at the r^0 or constant terms. I.e. r^3-7r-6 = (r+1)(r^2 - r -6). r^2 -r-6 factors as (r-3)(r+2).

So the roots are r=3, r=-1, r=-2 (I like to list them in descending order, but there's no need).

Our solution will be { A*3^n + B*(-1)^n + C*(-2)^n } and we just have to find A, B, C so as to satisfy the initial conditions (maybe I should say just). Here are the relevant equations:

n=0: a_0=9 = A + B + C (since any r^0 is 1)
n=1 a_1=10 = 3A - B - 2C (each r^1 is r)
n=2 a_2=32 = 9A + B + 4 C (negatives squared are positive).

You may not have had much practice solving 3 equations in 3 unknowns. The principle is the same. E.g. Add first two equations together to get rid of B. Subtract first from third will also do this. This gives us the following two new equations:
9+10=19 = 4A-C

`     and    `
32-9=23=8A+3C
Now we are down to two equations in 2 unknowns: 3 times the first plus the second gets rid of the C:
3*19 +23 = 12A + 8A -3C + 3C ---> 80 = 20A, hence A=4.
Substitute this value for A into one of the previous 2 equations to give us C: 19=4A-C, hence C=-3. Finally A+B+C=9, hence 4+B-3=9, gives that B=8.

Final solution: { 4(3)^n +8(-1)^n - 3 (-1)^n }.

17. f_(n+1)=C(n,0)+C(n-1,1)+...+C(n-k,k) where k=floor(n/2) Hint: a_n is this sum and show it satsifies the right recurrence relation.

This is a neat idea. Why does it work in theory. Well if two sequences satisfy the same recurrence relation and have the same initial conditions then the sequences are the same (it is just an inductive proof hidden in the fact that we inductively proved the statement I just made).

What is the right recurrence relation: the one from the fibonacci numbers: f_n = f_(n-1) + f_(n-2). f_0=0, f_1 = 1 but we want every shifted up one term. Hence a_n = a_(n-1) + a_(n-2) and a_0 = 1, a_1 = 2 is satisfied by the sequence: a_0=f_1, a_1=f_2, a_2=f_3, ...

Now we show it is also satisfied by C(n,0) + ...
It's not complicated but it is a lot of terms to rearrange:
a_(n-2):

`      `
C(n-2,0) + C(n-3,1) + ... + C(n-2-j,j) where j = floor( n-2 /2)
a_(n-1): C(n-1,0) + C(n-2,1) + C(n-3,2)+ ... + C(n-1-i,i) where i = floor( n-1 /2)
The terms that are stacked upon one another (hopefully they line up) are just from Pascal's identity: C(n-m-1,m-1)+C(n-m-1,m)=C(n-m,m)
So add the two rows together and use this identity:
`       `
C(n-1,0) + C(n-1,1) + C(n-2,2) + ... + LAST TERM?

The idea is that this is just the expression we'd expect for a_n. The first term is OK because C(n,0) = C(n-1,0) = 1. Then we have to mess around to see how it ends and this depends on whether n is odd or even. If n is even then floor(n-2 /2) = floor(n-1 /2), so the first row has a term sticking out on the right. This term is just C(n-2 - (n-2)/2, n-2 /2) (we don't need the floor if we know it is even). This is just C( n-2 /2, n-2 /2) = 1 = C(n - (n/2), (n/2)) as it is supposed to be. On the other hand, if n is odd, then floor(n-1 /2) = (n-1)/2 = floor(n/2), so the term by term match ups go all the way to the end and the last term of each is C((n-2) - ( (n-1)/2 - 1), (n-1)/2 - 1 ) + C( (n-1) - (n-1)/2, (n-1)/2) =
C( (n-1) - (n-1)/2, (n-1)/2 - 1) + C( (n-1) - (n-1)/2, (n-1)/2) =
C( n - (n-1)/2, (n-1)/2) (by Pascal's Identity) = C( n - floor(n/2), floor(n/2) ) as required.

18. {p_n} is a solution to the inhomogeneous relation: a_n=c_1*a_(n-1) + ... + c_k*a_(n-k) + F(n) (F arbitrary function) then every solution is of the form { p_n + h_n} where {h_n} is any solution to the corresponding homogeneous relation (drop the F(n)).

Theory is always easier than application: Suppose that {q_n} is some other solution. For each n, set h_n = q_n - p_n, hence simply by the definition of h_n, we have that q_n = p_n + h_n. Now we just have to see if { h_n } is a solution to a_n = c_1*a_(n-1) + ... + c_k * a_(n-k).

Remember that { q_n } is a solution to the inhomogeneous relation:
(p_n + h_n) = c_1*(p_(n-1) + h_(n-1)) + c_2*(p_(n-2) + h_(n-2) ) + ... c_k(p_(n-k)+h_(n-k)) + F(n)

Simplify and rearrange ( F(n) occurs just once) to get:
p_n + h_n = (c_1*p_(n-1) + c_2*p_(n-2) + ... + c_(n-k)*p_(n-k) + F(n)) ) + (c_1*h_(n-1) + c_2 * h_(n-2) + ... + c_(n-k)*h_(n-k))

Now remember that p_n = (c_1*p_(n-1) + c_2*p_(n-2) + ... + c_(n-k)*p_(n-k) + F(n)) hence we can cancel those equal terms away from both sides leaving us with the fact that { h_n } satisfies the homogeneous recurrence relation.

19. a_n=3*a_(n-1) + 2^n (a) then a_n = -2^(n+1) is a solution.

Well just plug it in and check: a_n = - 2^(n+1), while 3*(- 2^(n-1+1)) + 2^n = -3 * 2^n + 2^n = 2^n * (-3+1) = 2^n * (-2) = - 2^(n+1) -- YUP.

(b) find all solutions

Use previous exercise: we just solve the homogeneous system: a_n=3*a_(n-1) (which is trivially just { A * 3^n } for any A. And then we get that { -2^(n+1) + A*3^n } is the general solution.

(c) now find one with a_0=1.

Set - 2^(0+1) + A*3^0 = a_0 = 1 and solve for A, i.e. A=3.