Task: Consider the following recursion:

Provide a closed (non-recursive) formula for and prove it using mathematical induction.

finding a non-recursive formula

  1. recursively insert until you find a pattern
  2. try to write the pattern with a single expression, constant expressions / expressions containing and sums
  3. choose a substitution that makes
  4. simplify

proving formula using induction

  1. check base case (2nd case of the induction, in our case )
  2. induction case: choose an substitution for (for example the previously used subsitution with )
  3. simplify until you get the induction assumption again