Task: Consider the following recursion:
Provide a closed (non-recursive) formula for and prove it using mathematical induction.
finding a non-recursive formula
- recursively insert until you find a pattern
- try to write the pattern with a single expression, constant expressions / expressions containing and sums
- choose a substitution that makes
- simplify
proving formula using induction
- check base case (2nd case of the induction, in our case )
- induction case: choose an substitution for (for example the previously used subsitution with )
- simplify until you get the induction assumption again