一个数列 $u_1, u_2, u_3, \ldots$ 由下式定义

$n\in\mathbb{Z}^+$

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

递推式同时使用前两项，所以归纳证明必须先验证 $n=1$ 与 $n=2$ 两个基例。归纳步骤中假设公式对相邻的 $u_k$、$u_{k+1}$ 成立，再代入递推式推出 $u_{k+2}$ 的目标形式。

For $n=1$, the proposed formula gives

For $n=2$, it gives

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

Assume that the result is true for two consecutive positive integers $k$ and $k+1$. Thus,

and

Using the recurrence relation,

The powers of $2$ combine as

Also,

Since $(-1)^{k+2}=(-1)^k$, it follows that

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

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