数学的帰納法

質問

問題
任意の自然数nに対して5・2^n+(-4)^n-1をある素数pで割った時の余りが常に1になるとする時のpの値を求めよ。

解説は添付の資料の通りです。
n=1,2を代入してp=5であるところまでは出来ます。その後帰納法を使った証明で、
途中の解答に、
突然、なぜ漸化式が出てきたのかがわかりません。漸化式を使う必要性はなんですか？
計算が簡単だから？

通常の帰納法のように解答するという方法はダメなのでしょうか？今回の証明は特別に漸化式を使わないと解けない問題だということでしょうか。

回答No.3

yuta_math · ベストアンサー

今気づきましたが、先に回答した内容は、質問に対する回答になっていませんでした。お詫び申し上げます。

I.漸化式が出てきた理由について

これは、表記を簡略化するためでしょう。
いちいち、解答の文章中に5・2ⁿ+(-4)ⁿ⁻¹などと書くのは大変です。

a(n)=5・2ⁿ+(-4)ⁿ⁻¹などと置いてしまった方が楽です。
(関係ないのですが、解答中の5・2ⁿ+(-4)ⁿ⁻¹=a(n)と書き方があまり好きではありません。)

漸化式で置くこと自体で、既存の漸化式に関する定理等に帰着でき、議論が進展する問題もありますが、これはそういう類の問題ではないですね。。。

II.通常の帰納法のように解答すると...

以下のようになります。

解答例:
全ての自然数nについて「5・2ⁿ+(-4)ⁿ⁻¹をある素数5で割った時の余りが常に1になる」...(⭐︎)を示す。

(i)n=1のとき、5・2¹+(-4)⁰=11,11÷5=2あまり1より(⭐︎)は成り立つ。
n=2のとき、5・2²+(-4)¹=16,16÷5=3あまり1より(⭐︎)は成り立つ。

(ii)n=k,k+1のとき、(⭐︎)は満たされることを仮定すると、
整数m,lを用い、
5・2ᵏ+(-4)ᵏ⁻¹=5m+1
5・2ᵏ⁺¹+(-4)ᵏ=5l+1

5・2ᵏ⁺²+(-4)ᵏ⁺¹=5×(整数)+1の形で表されることが目標である。

{5・2ᵏ⁺²+(-4)ᵏ⁺¹}+2{5・2ᵏ⁺¹+(-4)ᵏ}-8{5・2ᵏ+(-4)ᵏ⁻¹}
=5・2ᵏ(2²+2・2-8)+(-4)ᵏ⁻¹{(-4)²+2(-2)-8}=0

5・2ᵏ⁺²+(-4)ᵏ⁺¹=-2{5・2ᵏ⁺¹+(-4)ᵏ}+8{5・2ᵏ+(-4)ᵏ⁻¹}
=-2(5m+1)+8(5l+1)
=5(-2m+8l+1)+1
となりn=k+2のときも(⭐︎)は成り立つ。

(i)(ii)より全ての自然数に対し、(⭐︎)は成り立つ。

※a(n)=5・2ⁿ+(-4)ⁿ⁻¹が三項間漸化式の解の形と気付くと、
「漸化式の解から、漸化式を作る」問題と見ることとできます。
a(n+2)+2a(n+1)-8a(n)=0を解くと、a(n)=5・2ⁿ+(-4)ⁿ⁻¹になります。

お礼

丁寧な解答ありがとうございます。
私は数学的帰納法で解いたのですが、お陰様でその解答合わせも出来ました。
助かりました。
もしかしたら、本当の問題には続きがあるのかもしれないですね。だから漸化式を使ったのかも…と思うと納得です。

回答No.2

yuta_math

こんにちは、OKwaveでの私の初回答になります。

解答ができるまでの思考過程を書いてみますね。

問題:任意の自然数nに対して5・2ⁿ+(-4)ⁿ⁻¹をある素数pで割った時の余りが常に1になるとする時のpの値を求めよ。

(問題は「任意の自然数nに対して5・2ⁿ+(-4)ⁿ⁻¹をpで割った余りを1とするような、素数pが存在するか、存在するならそれを全て求めよ。」とも言えます。このように私がいいかえた理由は、「ある」わかりにくい表現を「存在する」という表現にいいかえたかったためです。)

STEP1.まずは、問題の意味がわからない(私も含め)ので、具体的な自然数nを代入して5・2ⁿ+(-4)ⁿ⁻¹をpで割ったときの余りが1となるpを求め、素数pの「ふるまい」をみましょう。

いちいち、n=◯のとき、5・2ⁿ+(-4)ⁿ⁻¹=△などと書くのが面倒なので、
a(n)=5・2ⁿ+(-4)ⁿ⁻¹...(1)とおきます。

a(1)=11のとき、余りを1にするのは、p=5
a(2)=16のとき、余りを1にするのは、p=3,5
a(3)=56のとき、余りを1にするのは、p=5,11
a(4)=16のとき、余りを1にするのは、p=3
...

a(4)まで書きましたが、実はa(1)を考えた時点で、p=5のみですから、「任意の」の自然数に対し、余りを1にするようなpの候補はp=5のみです。

これだけでp=5が答えとわかってしまいますが、p=5が条件を満たすことを確認します。「pは存在しない」という可能性を潰すためです。(難しく言うと、p=5は今の時点では、必要条件しか満たさないから、十分条件を確認しないといけない。)

問題は「任意の自然数nに対して5・2ⁿ+(-4)ⁿ⁻¹をある素数5で割った時の余りが常に1になること」...(⭐︎)を示せ。にいいかえられます。

STEP2.(⭐︎)を示す。

任意の自然数nに関する命題は、数学的帰納法で示すのが、普通ですが、それはあなたの解答に書いてあるので、省略します。(関係ない補足ですが、任意の変数xに関する命題を全称命題といいます。)

ここでは、合同式を使って示しましょう。

ここでの合同式の定義は、
a-bが5で割り切れるなら、a≡bとします。

5・2ⁿ≡0...❶
(-4)≡1より、
これの両辺にn-1乗し、
(-4)ⁿ⁻¹≡1ⁿ⁻¹=1...❷

❶+❷より、
5・2ⁿ+(-4)ⁿ⁻¹≡0+1=1
となり、(⭐︎)が示されました。

回答は以上です。わかりにくい場所があれば、補足してください。

お礼

合同式で証明してもいいんですね。勉強になりました！ありがとうございます！

回答No.1

f272

> 漸化式を使う必要性はなんですか？計算が簡単だから？

解説を作った人の頭のなかに最初に思い浮かんだから。

> 通常の帰納法のように解答するという方法はダメなのでしょうか？今回の証明は特別に漸化式を使わないと解けない問題だということでしょうか。

どんなやり方でもいいですよ。別に漸化式に持ち込まなくてもいいです。
a[n]=5*2^n+(-4)^(n-1)
なのだから第1項は5で割り切れるし，第2項は5で割ると余りが1になるので，a[n]は5で割ると余りが1になると言えば最も簡単だと思います。

お礼

ありがとうございます！解決しました。