9. (i) 一个数列定义如下：

$n \geq 1$

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

(ii) 用数学归纳法证明，对于 $n \in \mathbb{N}$

能被 $16$ 整除。

先验证 $n=1$。归纳步骤中假设公式对 $n=k$ 成立，再把该表达式代入递推关系；整理后的式子必须与原公式中把 $n$ 换成 $k+1$ 完全一致。

For $n=1$, the proposed formula gives

Therefore, the result is true for $n=1$.

Assume that the result is true for $n=k$, where $k\in\mathbb Z^+$. Thus

Using the recurrence relation,

This is precisely

which is the required formula for $n=k+1$.

Hence, if the result is true for $n=k$, it is true for $n=k+1$. Since it is true for $n=1$, by mathematical induction,

for all $n\in\mathbb Z^+$.

先验证 $f(1)$ 是 $16$ 的倍数。归纳步骤把 $f(k+1)$ 改写成 $5f(k)+16(k+2)$；归纳假设保证第一项可被 $16$ 整除，第二项显然也可以。

For $n=1$,

so $f(1)$ is divisible by $16$.

Assume that $f(k)$ is divisible by $16$ for some $k\in\mathbb Z^+$. Then

Now

By the induction hypothesis, $f(k)$ is divisible by $16$. Therefore both $5f(k)$ and $16(k+2)$ are divisible by $16$, so $f(k+1)$ is divisible by $16$.

Hence, if the result is true for $n=k$, it is true for $n=k+1$. Since it is true for $n=1$, by mathematical induction,

for all $n\in\mathbb Z^+$.

也可以使用差分。先求

再用一个简短的辅助归纳证明括号内总能被 $4$ 整除，于是相邻两项之差可被 $16$ 整除。

First,

so the result is true for $n=1$.

We first prove that $5^{k+2}-1$ is divisible by $4$ for every $k\in\mathbb Z^+$.

For $k=1$,

Assume that $5^{k+2}-1=4m$ for some integer $m$. Then

which is divisible by $4$. Therefore, by induction, $5^{k+2}-1$ is divisible by $4$ for every positive integer $k$.

Now assume that $f(k)$ is divisible by $16$. The difference between consecutive terms is

Since $5^{k+2}-1$ is divisible by $4$, this difference is divisible by $16$. Hence $f(k+1)$, being the sum of $f(k)$ and a multiple of $16$, is divisible by $16$.

The result is true for $n=1$, and truth for $n=k$ implies truth for $n=k+1$. Therefore, by mathematical induction,

for all $n\in\mathbb Z^+$.

把“能被 $16$ 整除”明确写成“等于 $16$ 乘某个整数”。由归纳假设把幂项表示出来，代入下一项后，提出因子 $16$，并说明括号内仍是整数。

For $n=1$,

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

Assume that the result is true for $n=k$, where $k\in\mathbb Z^+$. Then there is an integer $\lambda$ such that

Rearranging,

For the next value,

Since $\lambda$ and $k$ are integers, $5\lambda+k+2$ is an integer. Hence $f(k+1)$ is divisible by $16$.

The result is true for $n=1$, and truth for $n=k$ implies truth for $n=k+1$. Therefore, by mathematical induction,

for all $n\in\mathbb Z^+$.