20250627_D&A_recursion proof example

Task: Consider the following recursion:

T (n) = {\begin{cases} T (n - 1) + 3 n & n > 1 \\ 3 & n = 1 \end{cases}

Provide a closed (non-recursive) formula for $T (n)$ 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 $T (\dots)$ expression, constant expressions / expressions containing $n, k$ and sums
choose a substitution that makes $T (n, k, \dots) = T (1)$
simplify

\begin{aligned} T (n) & = T (n - 1) + 3 n \\ = (T (n - 2) + 3 (n - 1)) + 3 n \\ = ([T (n - 3) + 3 (n - 2)] + 3 (n - 1)) + 3 (n - 0) \\ = \dots \\ = T (n - k) + 3 n k + \sum_{j = 0}^{k - 1} 3 j \\ = T (n - k) + 3 n k + 3 \frac{(k - 1) k}{2} \\ = T (1) + 3 n (n - 1) + 3 \frac{(n - 2) (n - 1)}{2} & (k := n - 1) \\ = 3 + 3 n^{2} - 3 n - \frac{3}{2} (n^{2} - 3 n + 2) & (T (1) = 3) \\ = (3 - \frac{3}{2}) n^{2} + (- 3 + \frac{9}{2}) n + 3 - 3 \\ = \frac{3}{2} (n^{2} + n) \\ ⟹ T (n) : & = \frac{3}{2} (n^{2} + n) & (our Assumption) \end{aligned}

proving formula using induction

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

\begin{aligned} base case (n=1): & T (1) & = 3 = 3 = \frac{3}{2} (1 + 1) ✓ \\ induction case (n=k+1): & T (k + 1) & = T (k) + 3 (k + 1) \\ = \frac{3}{2} (k^{2} + k) + 3 k + 3 & (assumption) \\ = \frac{3}{2} k^{2} + \frac{9}{2} k + 9 \\ = \frac{3}{2} (k^{2} + 3 k + 2) \\ = \frac{3}{2} (k^{2} + 2 k + 1 + (k + 1)) \\ = \frac{3}{2} ((k + 1)^{2} + (k + 1)) \\ = \frac{3}{2} (n^{2} + n) ✓ & ◻ \end{aligned}