数学的帰納法と漸化式についての勘違い？

松谷です。

数学的帰納法と漸化式は相性がいいです。

ですから、X_(n+2)=3X_(n+1)-X_n

みたいなのを示せという問題があったときに、

ああ、数学的帰納法だ！と思うかもしれません。

でも、それはちょっと待ったです。

数学的帰納法の形式の中に漸化式を使って示すことは大いにありますが、

漸化式を示せという問題において、数学的帰納法を使うことは結構レアケースです。

漸化式を帰納法で示すということは、

X_3=3X_2-X_1の成立を確認して、

X_(k+2)=3X_(k+1)-X_kの成立を仮定して、

X_(k+3)=3X_(k+2)-X_(k+1)を示すということです。

しかし、帰納法の形式からすると、仮定を使ってその次を考えるわけですが、ん？どうやって使うんだとなりますよね。そもそも上の式だけ見てるとX_(k+3)って何だって感じですし。

ということで、基本的には、漸化式を示す問題においては、帰納法を使うのではなく、直接示していくような方法を考えるのが普通です。

たとえば、こんな問題があったとします。

x^2-3x+1=0の２解をα,βとするときに、

α^n+β^nをX_nと置いたときに、X_(n+2)=3X_(n+1)-X_nを示せ。

という問題なら、

α^(n+2)+β^(n+2)=（α+β)｛α^(n+1)+β^(n+1)}-αβ(α^n+β^n)

ここで、解と係数の関係より、α+β=3,αβ=1より、上の式は、

X_(n+2)=3X_(n+1)-X_nとなる。よって示された。

みたいにするのが普通になるわけですね。

さて、じゃあどんな時に帰納法と漸化式を絡ませるんだよっていう話ですね。

それは、上の例なら、nが奇数のとき、X_nが3の倍数であることを示せ。とかそういうやつですね。

そのようなときは、漸化式は成り立っている前提として、それを帰納法の中に組み込んでいいくわけですね。

ちなみに、各項が整数値であるような漸化式は一般に余りに周期性を持ちます。その証明は鳩ノ巣原理を用いてできますが、まあそれはまた別の話ということで。。。

なんかパソコン文字が綺麗に出ないので、分かりにくい気もしますが、まあいいか。。。

数学ネタで込み入りすぎると誰も読まなくなってしまうので。。。