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

$u_1 = 3$

$u_{n+1} = 2u_n - 2^{n+1} \quad n \geq 1$

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

$u_n = 5 \times 2^{n-1} - n \times 2^n$

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

$f(n) = 5^{n+2} - 4n - 9$

能被 $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^+$.

官方评分资料还给出差分路线。先求 $f(k+1)-f(k)=4(5^{k+2}-1)$，再用一个简短的辅助归纳证明括号内总能被 $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^+$.