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

用数学归纳法证明，对于 $n \in \mathbb{Z}^+$，$f(n)$ 是 $9$ 的倍数。

(ii) 一个数列定义如下：

$u_1 = 2 \quad u_2 = 6$

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

用数学归纳法证明，对于 $n \in \mathbb{Z}^+$

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

先验证 $n=1$。归纳步骤中直接计算 $f(k+1)-f(k)$，并将差整理成显然含有因子 $9$ 的形式；再结合归纳假设推出 $f(k+1)$ 也是 $9$ 的倍数。

For $n=1$,

which is a multiple of $9$.

Assume that the result is true for $n=k$, where $k\in\mathbb{Z}^+$. Thus $f(k)$ is a multiple of $9$.

Now

Therefore, $f(k+1)-f(k)$ is a multiple of $9$. Since $f(k)$ is also a multiple of $9$ by the inductive hypothesis, $f(k+1)$ is a multiple of $9$.

Hence, if the result is true for $n=k$, it is true for $n=k+1$. Since it is true for $n=1$, $f(n)$ is a multiple of $9$ for every $n\in\mathbb{Z}^+$ by mathematical induction.

不先作差，而是直接把 $f(k+1)$ 拆成 $f(k)$ 与一个显然含因子 $9$ 的余项。这是官方评分资料给出的另一种等价整理。

The base case is

which is a multiple of $9$.

Assume that $f(k)$ is a multiple of $9$ for some $k\in\mathbb{Z}^+$. Then

Both terms on the final line are multiples of $9$, so $f(k+1)$ is a multiple of $9$.

Therefore, by mathematical induction,

这是二阶递推关系，因此归纳步骤需要同时假设公式对连续两项 $u_k$、$u_{k+1}$ 成立，才能推出 $u_{k+2}$。相应地，基础步骤也必须验证 $n=1$ 和 $n=2$ 两项。

For $n=1$,

For $n=2$,

Thus the result is true for $n=1$ and $n=2$.

Assume that the result is true for $n=k$ and $n=k+1$, where $k\in\mathbb{Z}^+$. Hence

and

Using the recurrence relation,

Therefore, if the result is true for $n=k$ and $n=k+1$, it is true for $n=k+2$. Since it is true for $n=1$ and $n=2$,

by mathematical induction.