Problem

9. (i) $f(n) = 7(3n + 1) - 1$

Prove by induction that, for $n \in \mathbb{Z}^+$, $f(n)$ is a multiple of $9$

(ii) A sequence of numbers is defined by

$u_1 = 2 \quad u_2 = 6$

$u_{n+2} = 3u_{n+1} - 2u_n \quad n \in \mathbb{Z}^+$

Prove by induction that, for $n \in \mathbb{Z}^+$

$u_n = 2(2^n - 1)$