トップ› 大阪大学› 1970年› 理系第6問

大阪大学 1970年理系第6問解説

方針・初手

与えられた和を $S_n$ とおき、$S_n$ の漸化式を導いて数学的帰納法を用いるのが定石である。解と係数の関係から和と積を求め、$S_n$ と $S_{n-1}, S_{n-2}$ の関係式を作ることで、すべての $S_n$ が整数だけで構成されることを示す。

解法1

$$S_n = \sum_{r=0}^{n} \alpha^{n-r}\beta^r$$

とおく。

2次方程式 $x^2 + ax + b = 0$ の2つの解が $\alpha, \beta$ であるから、解と係数の関係より

$$\alpha + \beta = -a$$

$$\alpha\beta = b$$

が成り立つ。ここで $a, b$ は整数である。

$n \geqq 3$ のとき、$S_n$ の漸化式を導出する。

$$(\alpha + \beta) S_{n-1} - \alpha\beta S_{n-2}$$

$$= (\alpha+\beta) \sum_{r=0}^{n-1} \alpha^{n-1-r}\beta^r - \alpha\beta \sum_{r=0}^{n-2} \alpha^{n-2-r}\beta^r$$

$$= \sum_{r=0}^{n-1} \alpha^{n-r}\beta^r + \sum_{r=0}^{n-1} \alpha^{n-1-r}\beta^{r+1} - \sum_{r=0}^{n-2} \alpha^{n-1-r}\beta^{r+1}$$

第2項のシグマを展開して整理すると、

$$\sum_{r=0}^{n-1} \alpha^{n-1-r}\beta^{r+1} = \left( \sum_{r=0}^{n-2} \alpha^{n-1-r}\beta^{r+1} \right) + \alpha^0\beta^n$$

となるため、第3項と打ち消し合って $\beta^n$ だけが残る。したがって、

$$(\alpha + \beta) S_{n-1} - \alpha\beta S_{n-2} = \sum_{r=0}^{n-1} \alpha^{n-r}\beta^r + \beta^n = \sum_{r=0}^{n} \alpha^{n-r}\beta^r = S_n$$

が成り立つ。これに解と係数の関係を代入すると、以下の漸化式が得られる。

$$S_n = -a S_{n-1} - b S_{n-2}$$

この漸化式を用いて、すべての正の整数 $n$ について $S_n$ が整数であることを数学的帰納法で証明する。

(i) $n = 1, 2$ のとき

$$S_1 = \alpha + \beta = -a$$

$$S_2 = \alpha^2 + \alpha\beta + \beta^2 = (\alpha+\beta)^2 - \alpha\beta = (-a)^2 - b = a^2 - b$$

$a, b$ は整数であるから、$S_1, S_2$ はともに整数である。

(ii) $n = k, k+1$（$k$ は正の整数）のとき、$S_k, S_{k+1}$ が整数であると仮定する。

$n = k+2$ のとき、漸化式より

$$S_{k+2} = -a S_{k+1} - b S_k$$

$a, b$ は整数であり、仮定より $S_{k+1}, S_k$ も整数であるから、$S_{k+2}$ も整数である。

(i), (ii) より、すべての正の整数 $n$ について $S_n$ は整数値をとることが示された。

解法2

因数分解の公式を利用して漸化式を導く方法を考える。

$$S_n = \sum_{r=0}^{n} \alpha^{n-r}\beta^r$$

とおく。

(i) $\alpha \neq \beta$ のとき

因数分解の公式より、

$$\alpha^{n+1} - \beta^{n+1} = (\alpha - \beta)(\alpha^n + \alpha^{n-1}\beta + \cdots + \beta^n) = (\alpha - \beta)S_n$$

が成り立つ。$\alpha \neq \beta$ より $\alpha - \beta \neq 0$ であるから、

$$S_n = \frac{\alpha^{n+1} - \beta^{n+1}}{\alpha - \beta}$$

と表せる。ここで $V_n = \alpha^n - \beta^n$ とおくと、$\alpha, \beta$ は方程式 $x^2 + ax + b = 0$ の解であるから、

$$\alpha^2 = -a\alpha - b$$

$$\beta^2 = -a\beta - b$$

が成り立つ。これらの両辺にそれぞれ $\alpha^{n-1}, \beta^{n-1}$ （$n \geqq 2$）を掛けて辺々引くと、

$$\alpha^{n+1} - \beta^{n+1} = -a(\alpha^n - \beta^n) - b(\alpha^{n-1} - \beta^{n-1})$$

すなわち、

$$V_{n+1} = -a V_n - b V_{n-1}$$

が得られる。この両辺を $\alpha - \beta$ で割ると、

$$\frac{V_{n+1}}{\alpha - \beta} = -a \frac{V_n}{\alpha - \beta} - b \frac{V_{n-1}}{\alpha - \beta}$$

$S_n = \frac{V_{n+1}}{\alpha-\beta}$ であるから、

$$S_n = -a S_{n-1} - b S_{n-2}$$

となり、解法1と同じ漸化式が得られる。初期条件 $S_1, S_2$ も整数となるため、数学的帰納法によりすべての正の整数 $n$ について $S_n$ は整数となる。

(ii) $\alpha = \beta$ のとき

方程式 $x^2 + ax + b = 0$ は重解をもつため、判別式 $D = a^2 - 4b = 0$ が成り立つ。このとき重解は $\alpha = -\frac{a}{2}$ である。

$a^2 = 4b$ より $a^2$ は偶数であり、したがって $a$ も偶数である。$a = 2k$ （$k$ は整数）とおくと、$\alpha = -k$ となり、$\alpha$ は整数であることがわかる。

このとき、$S_n$ は次のように計算できる。

$$S_n = \sum_{r=0}^{n} \alpha^{n-r}\alpha^r = \sum_{r=0}^{n} \alpha^n = (n+1)\alpha^n$$

$\alpha$ は整数であり、$n+1$ も整数であるから、$S_n$ は整数となる。

(i), (ii) より、いずれの場合もすべての正の整数 $n$ について $S_n$ は整数値をとることが示された。

解説

対称式の漸化式を作成し、帰納法に持ち込む典型的な整数問題である。解法1のように直接シグマ記号を用いて $S_n$ を組み上げる方法は、重解の有無による場合分けを回避できるため非常に見通しが良い。一方、解法2のように等比数列の和や因数分解の形から $\alpha^{n+1}-\beta^{n+1}$ の漸化式に帰着させる手法も、2項間・3項間の関係式を作るうえで汎用性が高い。