【数列】3項間漸化式の数学的帰納法（一昨日帰納法）｜普通の帰納法は使えない

みなさん、どうもこんにちは。今回は、3項間漸化式の数学的帰納法を紹介します。

3項間漸化式の数学的帰納法とは
1. 普通の帰納法では証明できない
2. 3項間漸化式の数学的帰納法の方法
3項間漸化式の数学的帰納法
1. 例題1：3項間漸化式の数学的帰納法
2. 演習1：3項間漸化式の数学的帰納法
入試頻出の3項間漸化式の数学的帰納法
1. α＋β型
2. 三角関数型
おわりに

3項間漸化式の数学的帰納法とは

3項間漸化式の数学的帰納法とは、3項間漸化式のときに使われる数学的帰納法になります（そのまま）。例えば、一つの式中に$a_n，a_{n+1}、a_{n+2}$が登場する漸化式を証明する際に、3項間漸化式の数学的帰納法を使います。3項間漸化式のときは、普通の数学的帰納法では絶対に証明することができないため、3項間漸化式用の数学的帰納法（普通の帰納法とは異なる特別な帰納法）を使う必要があります。

普通の帰納法では証明できない

まず、普通の帰納法では証明できないことを理解しましょう。3項間漸化式の数学的帰納法を使う問題、例えば、次のような問題です。（つまらない問題ですが、お付き合いください）

例題1

数列$\{a_n\}$を次のように定める。

$$ a_1=a_2=1，a_{n+2}=a_{n+1}+a_n $$

このとき、全ての$a_n$が自然数であることを示せ。

例題1の漸化式は3項間漸化式です。このような漸化式は普通の帰納法では絶対に証明できません。普通の帰納法とは

（I）$n=1$に成り立つ
（II）$n=k$のときに成り立つとしたら，$n=k+1$のときでも成立

というものです。これは普通の2項間の漸化式では使えるのですが、3項間漸化式では使うことができません。

例題1を見てもらいたいのですが、普通の帰納法では、$k+1$のときに自然数であると仮定しても、$k+2$のときに自然数であることは分からないのです。なぜならば、$a_k$が何なのか、分からないからです。

では、どのようにすれば証明できるのでしょうか？

3項間漸化式の数学的帰納法の方法

3項間漸化式の数学的帰納法では、$n=k$と$n=k+1$のとき成り立つと仮定して、$n=k+2$のときも成立することを示せば良いです。イメージ的には下図のようになります。前の二つを仮定して証明することから、一昨日帰納法と呼ばれることがあります。

3項間漸化式の数学的帰納法についてまとめると、次のようになります。

3項間漸化式の数学的帰納法

（I）$n=1，2$のとき成立する

（II）$n=k，k+1$のとき成立すると仮定すると，$n=k+2$のときも成立する

$n=k$と$n=k+1$の2つを仮定することがポイントです。

3項間漸化式の数学的帰納法

では、実際に例題を解いていくことにしましょう。

例題1：3項間漸化式の数学的帰納法

導入部で使ったつまらない問題ですが、もう一度考えてみることにします。

例題1

数列$\{a_n\}$を次のように定める。

$$ a_1=a_2=1，a_{n+2}=a_{n+1}+a_n $$

このとき、全ての$a_n$が自然数であることを示せ。

問題で与えられている漸化式は3項間漸化式ですから、下記に示す3項間漸化式の数学的帰納法（一昨日帰納法）の手順に従って証明していきましょう。

方針：3項間漸化式の数学的帰納法

（I）$n=1，2$のとき成立する
（II）$n=k，k+1$のとき成立すると仮定すると，$n=k+2$のときも成立する

解答1

数学的帰納法を用いて証明する。

（I）$n=1，2$のとき
問題文の条件より，$a_1=a_2=1$であるから，$n=1，2$のとき自然数である。

（II）$n=k，k+1$のとき
$n=k，k+1$のとき，すなわち$a_1，a_2$が自然数であると仮定する。$n=k+2$のとき，すなわち$a_{k+2}$は，問題文の漸化式$a_{k+2}=a_{k+1}+a_{k}$より自然数である。

以上より，全ての$a_n$が自然数であることが示された。

このように、二つ前を仮定して、証明していきます。

演習1：3項間漸化式の数学的帰納法

大学入試の過去問題を用いて演習していきましょう。

演習1

数列$\{a_n\}$を次のように定める。

$$ a_1=1，a_2=3，a_{n+2}a_n=2a_{n+1}^2 $$

このとき、全ての正の整数$n$について，$a_n$は正であることを示せ。

（東北大改）

演習1の答え

数学的帰納法を用いて証明する。

（I）$n=1，2$のとき
問題文の条件より，$a_1=1，a_2=3$であるから，$n=1，2$のとき正である。

（II）$n=k，k+1$のとき
$n=k，k+1$のとき，すなわち$a_1，a_2$が自然数であると仮定する。$n=k+2$は

$$ a_{k+2} = \displaystyle \frac{2a_{k+1}^2}{a_k} $$

であり，これより$a_{k+2}>0$だから，$n=k+2$のときも正である。

以上より，全ての正の整数$n$について，$a_n$は正であることが示された。

入試頻出の3項間漸化式の数学的帰納法

ここからは、入試頻出の3項間漸化式の数学的帰納法について紹介します。次の2タイプが非常によく出ます。

頻出：3項間漸化式の数学的帰納法

① $\alpha+\beta$型

② 三角関数型

上記の2パターンは式変形が必要なので、少し難しいです。

α＋β型

$\alpha+\beta$型は次の式変形を使って、3項間漸化式を作り、帰納法で証明していきます。

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

詳しくは次の記事で扱っています。

三角関数型

三角関数型は次の式変形を使って、3項間漸化式を作り、帰納法で証明していきます。

$$ \cos{(n+2)\theta} = 2\cos{\theta}\cos{(n+1)\theta}-\cos{n \theta} $$

詳しくは次の記事で扱っています。

おわりに

今回は、3項間漸化式の数学的帰納法について、紹介しました。理解してしまえば簡単なので、得点源になりやすいです。

最後までお読みいただき、ありがとうございました。