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)$所保證。

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

(證明終了)