有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

線形漸化式

$2$ 項間線形漸化式

定理《定数係数の $2$ 項間線形漸化式》

 $p,$ $q$ ($p \neq 0,$ $1$)を定数とする. $a_1$ の値と \[ a_{n+1} = pa_n+q \quad \cdots [\spadesuit ]\] で定まる数列 $\{ a_n\}$ について, $1$ 次方程式 \[ x = px+q \quad \cdots [\spadesuit ]'\] の解を $\alpha$ とおく. このとき, $\{ a_n-\alpha\}$ は初項 $a_1-\alpha,$ 公比 $p$ の等比数列であり, $\{ a_n\}$ の一般項は \[ a_n = (a_1-\alpha )p^{n-1}-\alpha\] である.

証明

 $[\spadesuit ],$ $[\spadesuit ]'$ の辺々を引くと, \[ a_{n+1}-\alpha = p(a_n-\alpha )\] となる. これは, $\{ a_n-\alpha\}$ が初項 $a_1-\alpha,$ 公比 $p$ の等比数列であることを表している. よって, \[ a_n-\alpha = (a_1-\alpha )p^{n-1}\] から, 求める等式が得られる.

別証明

 $[\spadesuit ]$ において $n$ を $n+1$ に置き換えると, \[ a_{n+2} = pa_{n+1}+q\] となる. この式から $[\spadesuit ]$ を引くと, \[ a_{n+2}-a_{n+1} = p(a_{n+1}-a_n)\] が得られるので, $\{ a_{n+1}-a_n\}$ は初項 $a_2-a_1,$ 公比 $p$ の等比数列である. \[\frac{a_2-a_1}{p-1} = \frac{pa_1+q-a_1}{p-1} = a_1-\frac{q}{p-1} = a_1-\alpha\] であるから, $n \geqq 2$ のとき, \[\begin{aligned} a_n &= a_1+\sum_{k = 1}^{n-1}(a_2-a_1)p^{k-1} \\ &= a_1+\frac{a_2-a_1}{p-1}(p^{n-1}-1) \\ &= a_1+(a_1-\alpha )(p^{n-1}-1) \\ &= (a_1-\alpha )p^{n-1}-\alpha, \end{aligned}\] つまり $a_n-\alpha = (a_1-\alpha )p^{n-1}$ が成り立つ. これは $n = 1$ のときも成り立つから, $\{ a_n-\alpha\}$ は初項 $a_1-\alpha,$ 公比 $p$ の等比数列である.

参考

 $p,$ $q,$ $r$ $(p,\ r \neq 0)$ を定数とする. $a_1$ の値と \[ a_{n+1} = pra_n+qr^{n+1}\] で定まる数列 $\{ a_n\}$ について, 数列 $\left\{\dfrac{a_n}{r^n}\right\}$ は両辺を $r^{n+1}\ (\neq 0)$ で割って得られる漸化式 \[\frac{a_{n+1}}{r^{n+1}} = p\frac{a_n}{r^n}+q\] を満たすから, $1$ 次方程式 $x = px+q$ の解を $\alpha$ とおくとき, $\{ a_n\}$ の一般項は \[ a_n = r^n\{ (a_1-\alpha )p^{n-1}-\alpha\}\] である.

問題《ハノイの塔》

 地面に $3$ 本の棒が立てられており, そのうちの $1$ 本に穴の開いた半径の異なる円盤が半径の大きい順に通されている. $1$ 本の棒の最も上にある $1$ 枚を別の棒の最も上に移す操作を $1$ 手と数え, $1$ 本の棒の最も上にある $n$ 枚を別の棒の最も上に移すための手数の最小値を $a_n$ とおく. ただし, いずれの段階においても小さい円盤の上に大きい円盤は置かないとする.
(1)
すべての正の整数 $n$ に対して $a_{n+1} = 2a_n+1$ が成り立つことを説明せよ.
(2)
数列 $\{ a_n\}$ の一般項を求めよ.

解答例

(1)
最初に円盤を通された棒を A とし, 残りの棒を B, C とする. 棒 A の最も上にある $n+1$ 枚を棒 B の最も上に移すためには, まず上の $n$ 枚を棒 C に移し, 次に棒 A に残された $1$ 枚を棒 B に移し, 最後に棒 C に移された $n$ 枚を棒 B に移す必要がある.
ゆえに, \[ a_{n+1} = a_n+1+a_n = 2a_n+1 \quad \cdots [1]\] が成り立つ.
(2)
\[ \alpha = 2\alpha +1 \cdots [2]\] を解くと, $\alpha = -1$ となる. $[1]-[2]$ から \[ a_{n+1}-\alpha = 2(a_n-\alpha )\] となるので, $\alpha = -1$ を代入すると \[ a_{n+1}+1 = 2(a_n+1)\] となる. よって, $\{ a_n+1\}$ は初項 $a_1+1 = 1+1 = 2,$ 公比 $2$ の等比数列であるから, \[ a_n+1 = 2^n\] つまり \[ a_n = 2^n-1\] である.

背景

 本問は, フランスの数学者リュカによって考案された「ハノイの塔」(tower of Hanoi)と呼ばれるパズルの手数の最小値を求める問題である. $n+1$ 枚の場合に全体を $n$ 枚のかたまりと $1$ 枚に分けて考えると $n$ 枚の場合が現れ, $a_n,$ $a_{n+1}$ の関係式が得られた. この方法は, 漸化式を立てて場合の数を求める問題の定石の $1$ つと言える.

$3$ 項間線形漸化式

定理《定数係数の $3$ 項間線形漸化式》

 $p,$ $q$ $(q \neq 0)$ を定数とする. $a_1,$ $a_2$ の値と \[ a_{n+2}+pa_{n+1}+qa_n = 0 \quad \cdots [\heartsuit ]\] で定まる数列 $\{ a_n\}$ について, $2$ 次方程式 \[ x^2+px+q = 0 \quad \cdots [\heartsuit ]'\] の $2$ つの解を $\alpha,$ $\beta$ とおく. このとき, $\{ a_n\}$ の一般項は, \[ a_n = \begin{cases} \dfrac{a_2-\beta a_1}{\alpha -\beta}\alpha ^{n-1}-\dfrac{a_2-\alpha a_1}{\alpha -\beta}\beta ^{n-1} & (\alpha \neq \beta ), \\ a_1\alpha ^{n-1}+(a_2-\alpha a_1)(n-1)\alpha ^{n-2} & (\alpha = \beta ) \end{cases}\] である.

証明

 解と係数の関係により \[\alpha +\beta = -p, \quad \alpha\beta = q\] であるから, \[\begin{aligned} [\heartsuit ] &\iff a_{n+2}-(\alpha +\beta )a_{n+1}+\alpha\beta a_n = 0 \\ &\iff \left\{\begin{array}{l} a_{n+2}-\alpha a_{n+1} = \beta (a_{n+1}-\alpha a_n) \quad \cdots [1], \\ a_{n+2}-\beta a_{n+1} = \alpha (a_{n+1}-\beta a_n) \quad \cdots [2] \end{array}\right. \end{aligned}\] が成り立つ.
(i)
$\alpha \neq \beta$ のとき. $[1],$ $[2]$ は, それぞれ $\{ a_{n+1}-\alpha a_n\}$ が初項 $a_2-\alpha a_1,$ 公比 $\beta$ の等比数列であること, $\{ a_{n+1}-\beta a_n\}$ が初項 $a_2-\beta a_1,$ 公比 $\alpha$ の等比数列であることを意味するから, \[\begin{aligned} a_{n+1}-\alpha a_n &= (a_2-\alpha a_1)\beta ^{n-1} \quad \cdots [3], \\ a_{n+1}-\beta a_n &= (a_2-\beta a_1)\alpha ^{n-1} \quad \cdots [4] \end{aligned}\] が得られる. $([4]-[3])\div (\beta -\alpha )$ から, 求める等式が得られる.
(ii)
$\alpha = \beta$ のとき. $[1]$ は, $\{ a_{n+1}-\alpha a_n\}$ が初項 $a_2-\alpha a_1,$ 公比 $\alpha$ の等比数列であることを意味するから, \[ a_{n+1}-\alpha a_n = (a_2-\alpha a_1)\alpha ^{n-1}\] が成り立つ. $q \neq 0$ から $\alpha \neq 0$ であることに注意して, 両辺を $\alpha ^{n+1}$ で割ると, \[\frac{a_{n+1}}{\alpha ^{n+1}}-\frac{a_n}{\alpha ^n} = \frac{a_2-\alpha a_1}{\alpha ^2}\] となる. よって, $\left\{\dfrac{a_n}{\alpha ^n}\right\}$ は初項 $\dfrac{a_1}{\alpha},$ 公差 $\dfrac{a_2-\alpha a_1}{\alpha ^2}$ の等差数列であるから, \[\begin{aligned} \frac{a_n}{\alpha ^n} &= \frac{a_1}{\alpha}+(n-1)\frac{a_2-\alpha a_1}{\alpha ^2} \\ a_n &= a_1\alpha ^{n-1}+(a_2-\alpha a_1)(n-1)\alpha ^{n-2} \end{aligned}\] が成り立つ.

参考

 $p,$ $q,$ $r$ $(q \neq 0)$ を定数として, $a_1,$ $a_2$ の値と \[ a_{n+2}+pa_{n+1}+qa_n+r = 0\] で定まる数列 $\{ a_n\}$ は \[ (a_{n+3}-a_{n+2})+p(a_{n+2}-a_{n+1})+q(a_{n+1}-a_n) = 0\] を満たすから, $\{ a_n\}$ の一般項は上記の方法で求められる.

問題《フィボナッチ数列の一般項》

 $1$ 歩目は $1$ 段だけ上るとし, $2$ 歩目以降は $1$ 歩で $1$ 段上ることも $2$ 段上ることもできるとして, $n$ 段の階段を上る方法の総数を $F_n$ とおく.
(1)
$F_{n+2} = F_n+F_{n+1}$ が成り立つことを示せ.
(2)
数列 $\{ F_{n+1}-\alpha F_n\},$ $\{ F_{n+1}-\beta F_n\}$ がそれぞれ公比 $\beta,$ $\alpha$ の等比数列となるような定数 $\alpha,$ $\beta\ (\alpha < \beta )$ を $1$ 組求めよ.
(3)
数列 $\{ F_n\}$ の一般項を求めよ.

解答例

(1)
$n+2$ 段の階段を上るとき, 最後の $1$ 歩に着目すると, 次の $2$ つの場合が考えられる.
(i)
最後の $1$ 歩で $2$ 段上る場合. $n+2$ 段を上る方法は, $n$ 段の上り方 $F_n$ 通りだけある.
(ii)
最後の $1$ 歩で $1$ 段上る場合. $n+2$ 段を上る方法は, $n+1$ 段の上り方 $F_{n+1}$ 通りだけある.
(i), (ii) は排反であるから, \[ F_{n+2} = F_n+F_{n+1} \quad \cdots [1]\] が成り立つ.
(2)
数列 $\{ F_{n+1}-\alpha F_n\},$ $\{ F_{n+1}-\beta F_n\}$ がそれぞれ公比 $\beta,$ $\alpha$ の等比数列であるとき, \[\begin{aligned} F_{n+2}-\alpha F_{n+1} &= \beta (F_{n+1}-\alpha F_n), \\ F_{n+2}-\beta F_{n+1} &= \alpha (F_{n+1}-\beta F_n) \end{aligned}\] から \[ F_{n+2} = (\alpha +\beta )F_{n+1}-\alpha\beta F_n \quad \cdots [2]\] が成り立つ. $[1],$ $[2]$ から, \[\alpha +\beta = 1,\quad \alpha\beta = -1\] が成り立てばよい. このとき, $\alpha,$ $\beta$ は $2$ 次方程式 $x^2-x-1 = 0$ の解であるから, 条件を満たす $\alpha,$ $\beta$ の組として \[ (\alpha,\beta ) = \left(\frac{1-\sqrt 5}{2},\frac{1+\sqrt 5}{2}\right)\] がとれる.
(3)
明らかに $F_1 = 1$ であり, $1$ 歩目は $1$ 段だけ上るという条件から $F_2 = 1$ である. よって, 数列 $\{ F_{n+1}-\alpha F_n\},$ $\{ F_{n+1}-\beta F_n\}$ の初項は, それぞれ \[\begin{aligned} F_2-\alpha F_1 = 1-\alpha &= \frac{1+\sqrt 5}{2} = \beta, \\ F_2-\beta F_1 = 1-\beta &= \frac{1-\sqrt 5}{2} = \alpha \end{aligned}\] である. したがって, $\alpha,$ $\beta$ の取り方から, \[\begin{aligned} F_{n+1}-\alpha F_n &= \beta ^n, \\ F_{n+1}-\beta F_n &= \alpha ^n \end{aligned}\] が成り立つ. 辺々を引くと \[ (\beta -\alpha )F_n = \beta ^n-\alpha ^n\] となるので, $\beta -\alpha = \sqrt 5$ から \[ F_n = \frac{1}{\sqrt 5}\left\{\left(\frac{1+\sqrt 5}{2}\right) ^n-\left(\frac{1-\sqrt 5}{2}\right) ^n\right\}\] が成り立つ.

背景

  • 初期条件 $F_1 = F_2 = 1$ と隣接 $3$ 項間漸化式 $F_{n+2} = F_n+F_{n+1}$ で定まる数列 \[\{ F_n\}:1,1,2,3,5,8,13,21,34,55,89,144,\cdots\] を「フィボナッチ数列」と呼ぶ. この数列の項は「フィボナッチ数」と呼ばれ, 花びらの枚数, 植物の種が並んでできるらせんの本数など, 自然界でよく見られる整数である.「フィボナッチ数列」は, 次の問題でも登場する: 先頭は動かないように, $2$ 番目以降は動かないか隣に移るように, $1$ 列に並んだ $n$ 人を並び替える方法の総数は $F_n$ である.
  • $\left|\dfrac{\alpha}{\beta}\right| = \dfrac{\sqrt 5-1}{1+\sqrt 5} < 1$ から \[\begin{aligned} \frac{F_{n+1}}{F_n} &= \frac{\beta ^{n+1}-\alpha ^{n+1}}{\beta ^n-\alpha ^n} = \frac{\beta -\alpha\left(\dfrac{\alpha}{\beta}\right) ^n}{1-\left(\dfrac{\alpha}{\beta}\right) ^n} \\ &\to \beta = \frac{1+\sqrt 5}{2} \quad (n \to \infty ) \end{aligned}\] であることもよく知られている(数学 III).

問題《カッシーニの公式》

 数列 $\{ F_n\}$ について, 初期条件 $F_1 = F_2 = 1$ のもとで,
$[1]$
$F_{n+2} = F_n+F_{n+1}$ 
$[2]$
$F_{n+1}{}^2-F_nF_{n+2} = (-1)^n$ 
は同値であることを示せ.
(参考: 2001 横浜国立大)

解答例

 $[1]$ を仮定して, $[2]$ を数学的帰納法で示す.
(i)
$n = 1$ のとき, \[ F_2{}^2-F_1F_3 = 1^2-1\cdot (1+1) = -1\] から, $[2]$ が成り立つ.
(ii)
$n = k$ ($k$: 正の整数)のとき $[2]$ が成り立つとすると, \[\begin{aligned} &F_{k+2}{}^2-F_{k+1}F_{k+3} \\ &= F_{k+2}{}^2-F_{k+1}(F_{k+1}+F_{k+2}) \\ &= F_{k+2}{}^2-F_{k+1}{}^2-F_{k+1}F_{k+2} \\ &= F_{k+2}{}^2-F_{k+1}{}^2-(F_{k+2}-F_k)F_{k+2} \\ &= F_{k+2}{}^2-F_{k+1}{}^2-F_{k+2}{}^2+F_kF_{k+2} \\ &= -(F_{k+1}{}^2-F_kF_{k+2}) \\ &= -(-1)^k = (-1)^{k+1} \end{aligned}\] となるから, $n = k+1$ のとき $[2]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[2]$ が成り立つ.
 $[2]$ を仮定して, $[1]$ と $F_n,$ $F_{n+1} > 0$ を数学的帰納法で示す.
(i)
$[2]$ に $n = 1$ を代入すると $1^2-1\cdot F_3 = -1$ から $F_3 = 2 = 1+1 = F_1+F_2$ となるので, $n = 1$ のとき $[1]$ が成り立つ. また, $F_1 = F_2 = 1 > 0$ が成り立つ.
(ii)
$n = k$ ($k$: 正の整数)のとき, $[1]$ と $F_n,$ $F_{n+1} > 0$ が成り立つとする. \[\begin{aligned} F_{k+2}{}^2-F_{k+1}F_{k+3} &= (-1)^{k+1}, \\ F_{k+1}{}^2-F_kF_{k+2} &= (-1)^k \end{aligned}\] の辺々を加えると \[\begin{aligned} F_{k+2}{}^2+F_{k+1}{}^2-F_{k+1}F_{k+3}-F_kF_{k+2} &= 0 \\ F_{k+2}{}^2\!+\!F_{k+1}{}^2\!-\!F_{k+1}F_{k+3}\!-\!(F_{k+2}\!-\!F_{k+1})F_{k+2} &= 0 \\ F_{k+1}{}^2+F_{k+1}F_{k+2}-F_{k+1}F_{k+3} &= 0 \\ F_{k+1}(F_{k+1}+F_{k+2}-F_{k+3}) &= 0 \end{aligned}\] となるから, $F_{k+1} > 0$ に注意すると, $F_{k+1}+F_{k+2}-F_{k+3} = 0$ つまり $n = k+1$ のとき $[1]$ が成り立つ. また, $F_{k+2} = F_k+F_{k+1} > 0$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[1]$ と $F_n,$ $F_{n+1} > 0$ が成り立つ.

背景

 「フィボナッチ数列」の漸化式 $[2]$ は,「カッシーニの公式」(Cassini's identity)として知られている.