東京大学 新領域創成科学研究科 複雑理工学専攻 2018年8月実施 専門基礎科目 第2問

标签：

• Tokyo-University
• Fibonacci-Recurrence
• Companion-Matrix-for-Linear-Recurrences
• Matrix-Diagonalization
• Matrix-Power
• Tridiagonal-Determinant-Recurrence

Author

之遥

Description

整数 $n \ge 1$ に対して, 三項間漸化式

$$x_{n+2} = x_{n+1} + x_n,x_1 = 1,x_2 = 1$$

を考える。以下の問に答えよ。

(問1) $\begin{pmatrix}x_{n+1} \\ x_{n+2}\end{pmatrix} = A\begin{pmatrix} x_n \\ x_{n+1} \\ \end{pmatrix}$ を満たす $2 \times 2$ 実行列 $A$ を求めよ。

(問2) 行列 $A$ の固有値 $\lambda_{+},\lambda_{-}(\lambda_{+} > \lambda_{-})$ を求めよ。

(問3) 行列 $A$ の対角化を用いて,

$$A^n = \frac{1}{\sqrt{5}} \begin{pmatrix} \lambda_{+}^{n-1} - \lambda_{-}^{n-1} & \lambda_{+}^n - \lambda_{-}^n \\ \lambda_{+}^n - \lambda_{-}^n & \lambda_{+}^{n+1} - \lambda_{-}^{n+1} \\ \end{pmatrix} \qquad \qquad (1)$$

を示せ。

以下の問では, 式 (1) を用いてよい。

(問4) $x_n = \alpha\lambda_{+}^n + \beta\lambda_{-}^n$ を満たす実数 $\alpha,\beta$ を求めよ。

(問5) 実数 $a,b$ に対して三項間漸化式

$$y_{n+2} = y_{n+1} + y_{n},y_1 = a,y_2 = b$$

を考える。 $y_{n}(n\ge3)$ を $a,b,x_{n-1},x_{n-2}$ を用いて表せ。

(問6) $D_1 = 1,D_{n}(n \ge 2)$ を $n \times n$ 三重対角行列 $B_n$ の行列式とする。

$$B_2 = \begin{pmatrix} 1 & 1 \\ -1 & 1 \\\end{pmatrix} , B_n = \begin{pmatrix} 1 & 1 & 0 & \cdots & \cdots & 0 \\ -1 & 1 & 1 & \ddots & & \vdots \\ 0 & -1 & 1 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots & \ddots & 1 & 1 \\ 0 & \cdots & \cdots & 0 & -1 & 1 \end{pmatrix}(n \ge 3)$$

のとき, $D_n(n \ge 3)$ を $x_{n-1}$ および $x_{n-2}$ を用いて表せ。

题目描述

对整数 $n\ge1$，定义 Fibonacci 型递推

$$x_{n+2}=x_{n+1}+x_n,\qquad x_1=x_2=1.$$

回答：

1. 求满足
   $$\binom{x_{n+1}}{x_{n+2}} =A\binom{x_n}{x_{n+1}}$$
   的 $2\times2$ 实矩阵 $A$。
2. 求 $A$ 的两个特征值 $\lambda_+>\lambda_-$。
3. 利用 $A$ 的对角化证明
   $$A^n=\frac1{\sqrt5} \begin{pmatrix} \lambda_+^{n-1}-\lambda_-^{n-1}& \lambda_+^n-\lambda_-^n\\ \lambda_+^n-\lambda_-^n& \lambda_+^{n+1}-\lambda_-^{n+1} \end{pmatrix}. \tag{1}$$
4. 求实数 $\alpha,\beta$，使
   $$x_n=\alpha\lambda_+^n+\beta\lambda_-^n.$$
5. 对任意实数 $a,b$，设
   $$y_{n+2}=y_{n+1}+y_n,\qquad y_1=a,\ y_2=b.$$
   对 $n\ge3$，用 $a,b,x_{n-1},x_{n-2}$ 表示 $y_n$。
6. 令 $D_1=1$；对 $n\ge2$，$D_n$ 是上文所示 $n\times n$ 三对角矩阵 $B_n$ 的行列式，其主对角元为 1、上对角元为 1、下对角元为 $-1$。对 $n\ge3$，用 $x_{n-1},x_{n-2}$ 表示 $D_n$。

第 4 至第 6 问允许直接使用式 (1)。

Kai

(問1)

$$\begin{bmatrix} x_{n+1} \\ x_{n+2} \\ \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \begin{bmatrix} x_n \\ x_n \\ \end{bmatrix}$$

(問2)

$$\begin{aligned} &\det(A - \lambda I) = 0 \\ &\lambda^2 - \lambda - 1 = 0 \\ &\lambda_{-} = \frac{1 - \sqrt{5}}{2},\lambda_{+} = \frac{1 + \sqrt{5}}{2} \end{aligned}$$

(問3)

$$\begin{aligned} &x_{-} = \begin{bmatrix} \lambda_{-} - 1 \\ 1 \end{bmatrix}, x_{+} = \begin{bmatrix} \lambda_{+} - 1 \\ 1 \end{bmatrix} \\ &X = \begin{bmatrix}\lambda_{-}-1 & \lambda_{+} - 1 \\ 1 & 1 \\ \end{bmatrix}, \Lambda = \begin{bmatrix} \lambda_{-} & \\ & \lambda_{+} \\ \end{bmatrix} \\ &A^n = (X\Lambda X^{-1})^n = X\Lambda^nX^{-1} = \frac{1}{\sqrt{5}} \begin{bmatrix} \lambda_{+}^{n-1} - \lambda_{-}^{n-1} & \lambda_{+}^n - \lambda_{-}^n \\ \lambda_{+}^n - \lambda_{-}^n & \lambda_{+}^{n+1} - \lambda_{-}^{n+1} \\ \end{bmatrix} \end{aligned}$$

(問4)

$$\left\{ \begin{aligned} &x_1 = 1 = \alpha\lambda_{+} + \beta\lambda_{-} \\ &x_2 = 1 = \alpha\lambda_{+}^2 + \beta\lambda_{-}^2 \\ \end{aligned} \right., \left\{ \begin{aligned} &\alpha = \frac{1}{\sqrt{5}} \\ &\beta = -\frac{1}{\sqrt{5}} \\ \end{aligned} \right.$$

(問5)

From (問4) ,

$$x_n = \frac{\lambda_{+}^n - \lambda_{-}^n}{\sqrt{5}}, x_{n-1} = \frac{\lambda_{+}^{n-1} - \lambda_{-}^{n-1}}{\sqrt{5}}, x_{n-2} = \frac{\lambda_{+}^{n-2} - \lambda_{-}^{n-2}}{\sqrt{5}}$$

$$\begin{aligned} &\begin{bmatrix} y_{n+1} \\ y_{n+2} \\ \end{bmatrix} = A^n\begin{bmatrix} y_1 \\ y_2 \\ \end{bmatrix} = \frac{1}{\sqrt{5}} \begin{bmatrix} \lambda_{+}^{n-1} - \lambda_{-}^{n-1} & \lambda_{+}^n - \lambda_{-}^n \\ \lambda_{+}^n - \lambda_{-}^n & \lambda_{+}^{n+1} - \lambda_{-}^{n+1} \\ \end{bmatrix} \begin{bmatrix} a \\ b \\ \end{bmatrix} \\ &y_{n} = \frac{1}{\sqrt{5}}[a(\lambda_{+}^{n-2} - \lambda_{-}^{n-2}) + b(\lambda_{+}^{n-1} - \lambda_{-}^{n-1})] \\ &\quad = a \frac{\lambda_{+}^{n-2} - \lambda_{-}^{n-2}}{\sqrt{5}} + b\frac{\lambda_{+}^{n-1} - \lambda_{-}^{n-1}}{\sqrt{5}} = ax_{n-2} + bx_{n-1} \end{aligned}$$

(問6)

$$\begin{aligned} D_{n} &= \begin{vmatrix} 1 & 1 & 0 & \cdots & \cdots & 0 \\ -1 & 1 & 1 & \ddots & & \vdots \\ 0 & -1 & 1 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots & \ddots & 1 & 1 \\ 0 & \cdots & \cdots & 0 & -1 & 1 \end{vmatrix}_{n \times n} \\ &= 1 \cdot \begin{vmatrix} 1 & 1 & 0 & \cdots & \cdots & 0 \\ -1 & 1 & 1 & \ddots & & \vdots \\ 0 & -1 & 1 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots & \ddots & 1 & 1 \\ 0 & \cdots & \cdots & 0 & -1 & 1 \end{vmatrix}_{(n-1) \times (n-1)} + 1 \cdot \begin{vmatrix} 1 & 1 & 0 & \cdots & \cdots & 0 \\ -1 & 1 & 1 & \ddots & & \vdots \\ 0 & -1 & 1 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots & \ddots & 1 & 1 \\ 0 & \cdots & \cdots & 0 & -1 & 1 \end{vmatrix}_{(n-1) \times (n-1)} \\ &= \begin{vmatrix} 1 & 1 & 0 & \cdots & \cdots & 0 \\ -1 & 1 & 1 & \ddots & & \vdots \\ 0 & -1 & 1 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots & \ddots & 1 & 1 \\ 0 & \cdots & \cdots & 0 & -1 & 1 \end{vmatrix}_{(n-1) \times (n-1)} + \begin{vmatrix} 1 & 1 & 0 & \cdots & \cdots & 0 \\ -1 & 1 & 1 & \ddots & & \vdots \\ 0 & -1 & 1 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots & \ddots & 1 & 1 \\ 0 & \cdots & \cdots & 0 & -1 & 1 \end{vmatrix}_{(n-2) \times (n-2)} \\ &= D_{n-1} + D_{n-2} \end{aligned}$$

From (問5) , $a = D_1 = 1, b = D_2 = 2$

Then $D_{n} = y_n = ax_{n-2} + bx_{n-1} = x_{n-2} + 2x_{n-1}$