6.042/18.] Mathematics for Computer Science March 18 2005 Srini devadas and Eric Lehman Notes for recitation 12 1 Solving linear recurrences Guessing a particular solution. Recall that a general linear recurrence has the form f(n)=a1f(n-1)+a2f(n-2)+…+aaf(n-d)+g(n) As explained in lecture, one step in solving this recurrence is finding a particular solu tion; i.e., a function f(n) that satisfies the recurrence, but may not be consistent with the boundary conditions. Here's a recipe to help you guess a particular solution If g(n) is a constant, guess that f(n) is some constant c Plug this into the recurrence and see if any constant actually works. If not, try f(n)= bn+c, then f(n)=an2+ + ete More generally, if g(n) is a polynomial, try a polynomial of the same degree. If that fails, try a polynomial of degree one higher, then two higher, etc. For example, if g(n)=n, then try f(n)=bn +c and then f(n)=an+bn+c If g(n)is an exponential, such as 3 n, then first guess that f(n)=c3n. Failing that, try f(n)=bn3n+c3n and then an 3n+ bn3n+c3n,etc In practice, your first or second guess will almost always work. Dealing with repeated roots. In lecture we saw that the solutions to a linear recurrence are determined by the roots of the characteristic equation: For each root r of the equation, the function rn is a solution to the recurrence Taking a linear combination of these solutions, we can move on to find the coefficients The situation is a little more complicated when r is a repeated root of the characteristic equation: if its multiplicity is k, then(not only rn, but) each of the functions mrn nrl a solution to the recurrence o that our linear combination must use all of them6.042/18.062J Mathematics for Computer Science March 18, 2005 Srini Devadas and Eric Lehman Notes for Recitation 12 1 Solving linear recurrences Guessing a particular solution. Recall that a general linear recurrence has the form: f(n) = a1f(n − 1) + a2f(n − 2) + · · · + adf(n − d) + g(n) As explained in lecture, one step in solving this recurrence is finding a particular solu￾tion; i.e., a function f(n) that satisfies the recurrence, but may not be consistent with the boundary conditions. Here’s a recipe to help you guess a particular solution: • If g(n) is a constant, guess that f(n) is some constant c. Plug this into the recurrence and see if any constant actually works. If not, try f(n) = bn + c, then f(n) = an2 + bn + c, etc. • More generally, if g(n) is a polynomial, try a polynomial of the same degree. If that fails, try a polynomial of degree one higher, then two higher, etc. For example, if 2 g(n) = n, then try f(n) = bn + c and then f(n) = an + bn + c. • If g(n) is an exponential, such as 3n, then first guess that f(n) = c3n. Failing that, try f(n) = bn3n + c3n and then an23n + bn3n + c3n, etc. In practice, your first or second guess will almost always work. Dealing with repeated roots. In lecture we saw that the solutions to a linear recurrence are determined by the roots of the characteristic equation: For each root r of the equation, the function rn is a solution to the recurrence. Taking a linear combination of these solutions, we can move on to find the coefficients. The situation is a little more complicated when r is a repeated root of the characteristic equation: if its multiplicity is k, then (not only rn, but) n n 2 n each of the functions r , nr , n r , . . . , nk−1rn is a solution to the recurrence, so that our linear combination must use all of them