Recurrence Equations

Last updated Nov 8, 2022 Edit Source

Solve using algebra

Important formulas to remember Arithmetic summation series: $$a+a+d+a+2d…+a+(n-1)d=\frac{n}{2}(2a+(n-1)d)$$ Geometric series summation: $$a+ar+ar^2+…ar^{n-1}=a(\frac{1-r^n}{1-r})$$

Guess and check strategy

1. Guess the solution form
2. Prove the base case (use a base case which is true)
3. Prove by mathematical induction:
   1. Assume true for n = k
   2. Prove true for k+1