Solutions to Assignment 8 8.2: 4.d: chi(r)=(r-1)^2. So a_n = A*2^n + B*n*2^n. Initial conditions show A=4, B=-7/2. 4.e: chi(r)=(r-1)(r+1). So a_n=A+B*(-1)^n. Initial conditions give A=2, B=3. 4.f: chi(r)=(r+3)^2. So a_n=A*(-3)^n + B*n*(-3)^n. Initial conditions give A=3, B=-2. 22: According to our theorem (Theorem 4 in the book) we have a_n = (d_0+d_1*n+d_2*n^2)*(-1)^n + (e_0+e_1*n)*(2)^n + (f_0+f_1*n)*(5)^n + g_0*7^n. 24: a) Follows just from plugging in: the left hand side is a_n=n*2^n, the right hand side is 2*a_(n-1)+2^n = 2*[(n-1)*2^(n-1)]+2^n = 2^n = n*2^n. They are equal, hence the recurrence is satisfied. b) From part a) we know one particular solution of the inhomogeneous recurrence. We now look for all solutions to the homogeneous one: the characteristic equation is r=2. So the general homogeneous solution is d_0*2^n. It follows that the general INhomogeneous solution is d_0*2^n + n*2^n. c) Plug n=0 into the result of b). You get d_0=2. 28: a) The characteristic equation is r=2. The general homogeneous solution is d_0*2^n. To find a special inhomogeneous solution, we use our theorem. Since F(n)=2*n^2 = =2*n^2*(1)^n, and 1 is not a root of chi(r), the theorem suggests an inhomogeneous solution of the form c_2*n^2+c_1*n+c_0. If you plug this into the inhomogeneous recurrence, you get n^2(c_2-2*c_2-2)+n*(c_1+4*c_2-2*c_1)_(c_0-2*c_2+2*c_1-2*c_0)=0. Each bracket must be zero because this is supposed to be true for all n. Hence c_2=-2, c_1=-8, c_0=-12. We get a general solution for the inhomogeneous equation equal to d_0*2^n - 2*n^2 - 8*n -12. b) Plug a_1=4 into the result of part a). You get d_0=13. 32: chi(r)= r-2. So a_n=A*2^n for homogeneous equation. F(n)=3*2^n, so s=2 and t=1. s is a root of chi of multiplicity 1. Hence the special solution to the inhomogeneous equation is of the form 2^n*B*n^1. Plug this into the recursion. You find B=3. So the general solution to the inhomogeneous equation is 2^n*3*n + A*2^n. Initial conditions, if they were given, would lead us to the value of A. 26: Applying Theorem 6 we need to know the roots of the characteristic equation. First off, the characteristic equation is r^3-6*r^2+12*r-8=0. As I told you in class, to find the roots you should try the divisors of the constant term -8. (Including the negative divisors!) One finds that the roots are r_1=r_2=r_3=2. So 2 has multiplicity 3. Now we use Theorem 6 and discover the following shapes of the specific solution to the inhomogeneous equation: a) b_2*n^2 + b_1*n + b_0 (s=1, m=0) b) b_0*2^n*n^3 (s=2, m=3) c) (b_1*n+b_0)*2^n*n^3 (s=2, m=3) d) b_0*(-2)^n (s=-2, m=0) e) (b_2*n^2+b_1*n+b_0)*2^n*n^3 (s=2, m=3) f) (b_3*n^3+b_2*n^2+b_1*n+b_0)*(-2)^n (s=-2, m=0) g) b_0 (s=1, m=0) 34: The characteristic equation is r^3-7*r^2+16*r-12=0. This polynomial has roots 2, 2 and 3. (You find them by trying the factors of the constant term -12.) So the solution of the homogeneous solution is of the form (b_0+b_1*n)*2^n + c_0*3^n. Now we need to find a solution for the inhomogeneous equation. Since n*4^n=4^n(1*n+0), s=4 and t=1. 4 is not a root of the characteristic equation, so the theorem 6 gives that a specific solution to the inhomogeneous equation should look like 4^n(d_1*n+d_0). To find out what d_0 and d_1 should be, plus this proposal into the recurrence. It's not much fun, but you discover that d_0=-80 and d_1=16. That means, that the general solution to the inhomogeneous equation is 4^n(16n-80) + (b_0+b_1*n)*2^n + c_0*3^n. This needs to be matched to the initial conditions. If a_0 =-2, then we obtain (-80) +b_0 + c_0 =-2. If a_1 = 0, we get 4*(-64) + (b_0+b_1)*2 + c_0*3 =0. If a_2 = 5 then 16*(-48) + (b_0+2*b_1)*4 + c_0*9 = 5. These are 3 equations for 3 variables, which you solve. You find that c_0 =61, b_0 = 17, b_1 = 39/2. Hence the solution to the inhomogeneous equation is 4^n(16n-80) + (17+39*n/2)*2^n + 61*3^n. 36: If a_n =(1+...+n^2) then a_n=(1+...+(n-1)^2)+n^2=a_(n-1) +n^2. So the recurrence is certainly satisfied. The initial condition a_1=1 is also clearly true. The F-term F(n) is n^2. The characteristic equation is r=1, so the only root is 1. That happens to be the s that shows up if we write F(n) = s^n(polynomial in n). So the second case of Theorem 6 is in force, suggesting a solution to the inhomogeneous equation of the form (b_0 + b_1*n + b_2*n^2)*n since s=1 and m=1. Plug this into the recurrence to find b_0,b_1,b_2. You find that b_2=1/3, b_1=1/2, b_0=1/6. So the general solution of the inhomogeneous recurrence is (n^2/3 + n/2 + 1/6)*n + d_0. Plug this into the initial condition a_1=1 to find that d_0=0. 46: a_0=2. a_n stands for the number of goats at the end of year n. a) a_(n+1) = 2*a_n +100, a_0=2. b) a_n = 2^(n+1) + (2^n-1)*100. c) a_1=2*2=4, a_2=2*4=8, a_3=2*8-3=13, a_4=2*13-4=22, a_5=2*22-5=39,... In terms of recurrences, a_n=2*a_(n-1) - n. d) The characteristic root is 2, the particular solution to the inhomogeneous equation is b_1*n+b_0. Plugging into the recurrence gives b_1=1, b_0=2, the particular solution is n+2. Hence a_n= n+2 + c_0*2^n. The initial condition says (note that the initial condition should be checked at n=2 since only at n=3 the rule "n sheep are removed" kicks in) 8=2+2+c_0*2^2. So c_0=1. Hence the solution is a_n = 2^n + n + 2. 8.4: 20: Comparing with what we did in class, if the order of the coins in "making change" does not matter, then the number of ways of making change for n pesos in 10, 20, 50 and 100 pesos is the coefficient of x^n in the Taylor series of 1/[(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)]. If on the other hand the order of the coins did matter (for example, if we picture tham as coming out of a change machine) then the number of ways that they could come out of the machine is given by the coefficient of x^n in the Taylor series of 1/(1-x^10+x^20+x^5-+x^100). 6: a) -1/(1-x) b) 1/(1-2x) c) 1/(1-x)^2 - 2/(1-x) d) (exp(x)-1)/x