4. Recursion and Solutions of Recurrence Relations

• However, in most cases the recursive version will be slower and require more memory at execution time.

Recurrence Relations

• Based on these results, we might conjecture that any closed form expression for a sequence that combines exponential expressions and polynomial expressions will be solutions of finite order linear relations. Not only is this true, but the converse is true: a finite order linear relation defines a closed form expression that is similar to the ones that were just examined. The only additional information that is needed is a set of initial conditions (p.161).

Solving Recurrence Relations

• If The recurrence is of shape \(a_n = a_{n-1} + 1\) then the solution is \(a_n = a_0 + n\).
• If The recurrence is of shape \(a_n = a_{n-1} + n\) then the solution is \(a_n = a_0 + \frac{n(n+1)}{2}\).
• If The recurrence is of shape \(a_n = a_{n-1} + n^2\) then the solution is \(a_n = a_0 + \frac{n(n+1)(2n+1)}{6}\).
• If The recurrence is of shape \(a_n = x.a_{n-1} + y.a_{n-2}\) then there are multiple steps we must take:
  • Find the characteristic equation: \(a_n = x.a_{n-1} + y.a_{n-2}\) by putting all terms in the right side such as \(a_n - x.a_{n-1} - y.a_{n-2} = 0\).
  • Solve the characteristic equation: \(r^2 - x.r - y = 0\) and call them \(r_1\) and \(r_2\).
  • Find the general solution: \(a_n = c_1.r_1^n + c_2.r_2^n\).
  • Solve for \(c_1\) and \(c_2\) using the initial conditions.
  • Find the closed form solution: \(a_n = c_1.r_1^n + c_2.r_2^n\).
  • Compute the results using the closed form solution.