Notes on problems from Chapter 8. I really don’t believe in doing this, but I’ll do it this time.
8.7 problems
1. (a)The sequence begins 1, 5, 13, 29, 61, and you are supposed to see that it is the powers of 2, with 3 subtracted. It’s 2n+1-3 or 2n-3, depending on whether you start with 0 or 1.
(b) This is 0, 2, 6, 12, …You look at the differences. Second differences are consatant, so you get a quadratic solution. an=n+n2
(c) you do this by inspection.
(d) you are supposed to observe that an=2Fn
I’m not going to go through the induction arguments.
2. it’s 1, 2, 5, 10, 17, 26,… Second differences are constant, so you get a degree 2 polynomial as the solution, as in 1(b). an=2-2n+n2=1+(n-1)2
3. This has constant third differences, so the solution is a degree three polynomial, and there is a lot of algebra involved in getting the solution.
8.12 Problems
1 and 2 are straightforward inductions; I assume you have done them.
6. Here, the second differences are 3, so you again get a quadratic polynomial as the closed form solution.. an=123n2-n. If you solve for an-an-1, you get the recurrence.
7. She wants you to do this by intuition. The characteristic polynomial has a double root of 1. It turns out that the basic solutions are 1 and n; i.e., the multiple root and n times it. You get -1 + 2n.
13. of course!
14. Characteristic equation becomes x2-4x+3=0, which has roots 1 and 3. The coefficients are both ½.
17. Again a quadratic. Roots are 1 and 4.
18. The recurrence goes down to an-4
19. This one can be solved by any of our methods. She wants you to do it by intuition, I believe. Anyway, an=-2+3n
20. The characteristic polynomial factors as (r + 3)(r – 4). You work backwards to get the recurrence.