離散数学 数学的帰納法

大学の離散数学の問題で、

「3^n + 7^n は8で割ると2余る」ということを数学的帰納法で証明せよ

という問題があるのですが、うまく証明できず困っています。

n = kで成り立つとするときに、仮定の式をどのように立てるべきなのか、そもそもピンときません。

3^k + 7^k = 8*a + 2と置いてみて、3^(k+1) + 7^(k+1)を同じような形に変形しようと試みたり、

7^k = (6 + 1)^k のようにしてみて変形しようとしたりしたのですが、どれもうまくいかず・・・。

丸投げをするつもりはないので、解法のヒントをいただけるとありがたいです。
よろしくお願いいたします。

No.1 ベストアンサー 回答者： f272 回答日時： 2009/06/15 14:06

あなたの言うとおりに

3^k+7^k=8a+2
とおいてみました。このとき3^(k+1)+7^(k+1)が8の倍数+2になっていることを確認できればいいのですね。
3^(k+1)+7^(k+1)
当然のようにk乗の形にしてみる
=3*3^k+7*7^k
仮定を使ってみる
=3*3^k+7*(8a+2-3^k)
8の倍数+2と分かる部分を括りだしてみる。
=8*(7a+2)+2+4*(3^k-1)
ここまでくれば簡単です。

この回答へのお礼

早速の回答ありがとうございました。

自分の仮定でできたなんて・・・お恥ずかしい限りです。
おっしゃる式変形、自分でもやってみました。
No.2の回答者様のヒントもあって、無事にできそうです。
ありがとうございました。

お礼日時：2009/06/15 21:47

No.2 回答者： rnakamra 回答日時： 2009/06/15 14:12

>3^k + 7^k = 8*a + 2と置いてみて

これでいいと思います。
後は
3^(k+1)+7^(k+1) = 3*3^k+7*7^k = 3*3^k+3*7^k+4*7^k = 3(3^k+7^k)+4*7^k
とでも変形。
()中を置き換えてさらにゴリゴリと変形。4*偶数が8の倍数であることを利用する。

この回答へのお礼

No.1の方と式変形が違ったので、２通りともやってみました。
どちらも最終的には同じ形になりました。

＞4*偶数が8の倍数であることを利用する

これにはまったく気づきませんでした。
ありがとうございました。

お礼日時：2009/06/15 21:49

No.3 回答者： Tacosan 回答日時： 2009/06/15 18:36

たぶん反則技だと思うけど, 奇数の 2乗を 8 で割ると必ず 1 余ります. つまり

3^(k+2) ≡ 3^k, 7^(k+2) ≡ 7^k (mod 8)
です. だから n=1, 2 で示してから帰納法を回すということも考えられますね.

この回答へのお礼

お恥ずかしながら、modはまだやったことがありません・・・。
でも、剰余のことだろうな、という程度で聞いたことはあります。

機会があったら、自分で証明してみようと思います。
ありがとうございました。

お礼日時：2009/06/15 21:54