Apostol Linear Algebra Exercise 0.13.2

題目

若一個實數$x$有性質$x^2=x+1$，用歸納法證明存在函數$f(n)$，使得對所有整數$n \geq 1$，都有$x^{n+1} = f(n+1)x +f(n)$。

解答

• 分析

$n=1$時，所要證明的的式子為
$$x^{1+1}=f(1+1)x + f(1),$$
也就是
$$x^2 = f(2) x + f(1).$$

比對題目所給的條件$x^2 = x +1$，合理猜測$f(2) = 1, f(1) = 1$。

現在看$n=2$的情況。此時要有
\begin{align*}
x^{2+1} &= f(2+1)x + f(2), \\
x^3 &= f(3) x + 1, \\
f(3) &= \frac{x^3 - 1}{x} \\
&= \frac{x \cdot x^2 - 1}{x} \\
&= \frac{x \cdot (x+1) -1}{x} \\
&= \frac{x^2 + x -1}{x} \\
&= \frac{(x+1)+ x -1}{x} \\
&= \frac{2x}{x} \\
&= 2.
\end{align*}
(注意顯然$x \neq 0$，所以$\frac{\square}{x}$是有意義的)而我們有
$$x^3 = 2x + 1.$$

再繼續看看$n=3$的情況。
\begin{align*}
x^{3+1} &= f(3+1)x + f(3) \\
x^4 &= f(4)x + 2 \\
f(4) &= \frac{x^4 - 2}{x} \\
&= \frac{x \cdot x^3 - 2}{x} \\
&= \frac{x \cdot (2x + 1) -2}{x} \\
&= \frac{2x^2 + x - 2}{x} \\
&= \frac{2(x+1) + x - 2}{x} \\
&= \frac{3x}{x} \\
&= 3.
\end{align*}而我們有
$$x^4 = 3x + 2.$$

彙整以上的計算結果如下
$$f(1) = 1, f(2) = 1, f(3) = 2, f(4) =3.$$
這些結果似乎構成Fibonacci數列，故猜測$f(5) = 5$。

計算$n=4$的情況來確認看看。
\begin{align*}
x^{4+1} &= f(4+1)x + f(4) \\
x^5 &= f(5)x + 3 \\
f(5) &= \frac{x^5 - 3}{x} \\
&= \frac{x \cdot x^4 - 3}{x} \\
&= \frac{x \cdot (3x + 2) -3}{x} \\
&= \frac{3x^2 + 2x - 3}{x} \\
&= \frac{3(x+1) + 2x - 3}{x} \\
&= \frac{5x}{x} \\
&= 5.
\end{align*}
而我們有
$$x^5 =5x + 3.$$

果真有$f(5) = 5$！

所以我們的猜測有可能正確！

甚至，由Fibonacci數列的通式可猜測
$$f(n) = \frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right].$$
(如此就把函數$f(n)$的顯式給表示出來)參考維基百科關於Fibonacci數列的條目。

• 正式解答

$n=1$時，由條件$x^2 = x + 1$可取$f(1) = 1, f(2) = 1$。

假定命題對於$n - 1$時成立，亦即存在函數$f$使得有$x^{(n-1)+1} = f\left[ (n-1) + 1 \right]x + f(n-1)$，這也意味著我們確定了$f(n-1)$與$f(n)$的值。

在$n$時，
\begin{align*}
x^{n+1} &= x \cdot x^n &[\text{指數的定義}] \\
&= x \cdot x^{(n - 1) + 1} & \\
&= x \cdot \left\{f[(n - 1) + 1]x + f(n-1) \right\} &[\text{歸納假設}] \\
&= x \cdot \left[ f(n)x + f(n-1) \right] & \\
&= f(n) x^2 + f(n-1) x &[\text{分配律}]\\
&= f(n) (x + 1) + f(n-1)x &[x\text{滿足的性質}]\\
&= \left[ f(n-1) + f(n) \right]x + f(n). &
\end{align*}
因為$f(n-1)$與$f(n)$的值都已確定，由此可定義
$$f(n + 1) = f(n-1) + f(n).$$
亦即$f(n+1)$之存在性由$f(n-1)$與$f(n)$所保證。

由數學歸納法證明了命題。

(證明終了)