受験数学わんこらスクール
京大理学部で数学をやったわんこらが中学生や高校生、受験生に数学の公式や問題を解説します。

連立漸化式と整数問題…東大2008年度文系第4問
年越しそばと数学は関係あるようでふるびた包丁をそぎ落とし。
どういう意味やねん。

と言うことで、東大文系2008年度の第4問をやりたい思います。


[問題]
081231_m1.jpg
pを自然数とする。次の関係式で定められる数列{a_n},{b_n}を考える。

a_1=p,b_1=p+1
a_(n+1)=a_n + pb_n (n=1,2,3,…)
b_(n+1)=pa_n + (p+1)b_n (n=1,2,3,…)

(1)n=1,2,3,…に対し、次の2つの数がともにp^3で割り切れることを示せ。

a_n - n(n-1)p^2/2 - np,
b_n - n(n-1)p^2 - np - 1

(2)pを3以上の奇数とする。このとき、a_nはp^2で割り切れるが、p^3では割り切れないことを示せ。


[解答と解説]
これは連立漸化式です。
連立漸化式とこれば文系の癖に行列をマニアックなまでに勉強してる人は行列で解いてまう強者もいるかもしれません。
そこまでしなくても、
a_(n+1)=a_n + pb_n
から
b_n=-1/p・a_(n+1) + 1/p・a_n
と言うようにb_nについて解いてb_(n+1)=pa_n + (p+1)b_nに代入して
a_(n+2)-(p+2)a_(n+1)+(-p^2+p+1)a_n=0
と隣接三項間漸化式になって特性方程式は
x^2-(p+2)x+(-p^2+p+1)=0
でこれを解いて
x=(p+2±√5)/2
だから
a_n=A{(p+2+√5)/2}^(n-1)+B{(p+2-√5)/2}^(n-1)
と置けてn=1とn=2と代入して…とやると
081231_m2.jpg
確かに解けるとは思いますが、計算がしんどくてわけわからんことになりかねないです。

東大や京大は文系でも数学3Cまで勉強して欲しいって言うのはあるらしいですが、そもそも東大では特に博学な知識を問うことはほとんどありません。


漸化式を解くのではなく漸化式のまま扱って証明したことはたぶん一回くらいあると思います。
こういう複雑な計算になりそうな漸化式ではその方法が上手くいきそうです。
思い浮かぶのは数学的帰納法です。
漸化式があるので非常に数学的帰納法に使いやすいです。

ただ注意して欲しいのは次の2つの数が『ともに』p^3で割り切れることを示せって所で、二つの数を同時にp^3で割れると成立を仮定しないと解けません。

この二つのn=k+1の時の式からこの二つの数のn=kの時の形を作り出していくわけですが、ややこしい式変形になれてる人はいいですがちょっと式がややこしいので

A_n=a_n - n(n-1)p^2/2 - np,
B_n=b_n - n(n-1)p^2 - np - 1
と置いて
a_n=A_n + n(n-1)p^2/2 + np
b_n=B_n + n(n-1)p^2 + np + 1
を代入していった方が機械的にA_nやB_nで表せて仮定が使えるので楽でミスが減ると思います。

081231_m3.jpg

A_n=a_n - n(n-1)p^2/2 - np,
B_n=b_n - n(n-1)p^2 - np - 1
と置いて数学的帰納法により
「A_n,B_nがともにp^3で割り切れる」…(*)
ことを示す。

(i)n=1の時
A_n=0,B_n=0で0はp^3で割り切れるから(と言うより0以外のどんな整数でも割り切れますが)(*)成立

(ii)n=kの時、(*)成立を仮定すると
A_(k+1)=a_(k+1) - (k+1)kp^2/2 - (k+1)p

a_(k+1)には漸化式a_(k+1)=a_k + pb_kでa_kとb_kにします。

A_(k+1)=a_k + pb_k - (k+1)kp^2/2 - (k+1)p


a_k=A_k + k(k-1)p^2/2 + kp
b_k=B_k + k(k-1)p^2 + kp + 1
を代入してA_kとB_kで表すと

A_(k+1)=A_k+B_k+k(k-1)p^3

これで帰納法の仮定からA_k+B_kがp^3で割り切れてk(k-1)p^3もp^3で割り切れるからA_(k+1)もp^3で割り切れます。

081231_m4.jpg

同じように
B_(k+1)=b_(k+1) - (k+1)kp^2 - (k+1)p - 1
=pa_k + (p+1)b_k - (k+1)kp^2 - (k+1)p -1
=pA_k+(p+1)B_k+3k(k-1)p^3/2

よってn=k+1の時も(*)成立。
(i)(ii)よりすべての自然数に対して(*)成立。


(2)は(1)を使おうと思うその精神があれば簡単だと思います。
普通(2)のために(1)があるはずなので大丈夫だとは思いますが。

081231_m5.jpg

(1)からmを整数として
a_p - p(p-1)p^2/2 - p^2 = mp^3(写真の置き方はnの時にmにしてるからまずかった…)
と置けて、
a_p = mp^3 + p(p-1)p^2/2 + p^2
pは3以上の奇数だからp=2q+1(qは自然数)と置けて
a_p = mp^3 + pqp^2 + p^2
=p^3(m+q)+p^2
でa_pはp^2で割り切れますが、p^3で割るとp^2余ることがわかります。


高校数学の入試問題などの解説

東京大学の入試の数学の過去問の解説

整数問題の解法の解説と問題演習




テーマ:算数・数学の学習 - ジャンル:学校・教育

▲ページトップへ
この記事に対するトラックバック
トラックバックURL
→http://kazuschool.blog94.fc2.com/tb.php/102-a50ff90e
この記事にトラックバックする(FC2ブログユーザー)
▲ページトップへ
プロフィール

わんこら

Author:わんこら
京都大学理学部で数学と物理を勉強し、数学を専攻しました。
東京で数学と物理の講師やってます

わんこら日記で日記とか勉強の仕方とか書いています

わんこら式数学の勉強法

メール
迷惑メールにされる危険性があるので出来るだけ
kazuyuki_ht○guitar.ocn.ne.jp
(○を@にしてください)に送ってください
勉強とかでどんな悩み持ってるかなど色々と教えてくれると嬉しいです。
わんこら式のやり方についてのメールはわんこら式診断プログラムを参考にしてください

詳しいプロフィール

人気blogランキングへ



にほんブログ村 受験ブログへ



学生広場

相互リンクも募集してます。

何かあれば
kazuschool_ht★yahoo.co.jp
かメールフォームからメールください。
(★を@にしてください)

カテゴリー

メールフォーム

名前:
メール:
件名:
本文:

FC2カウンター

リンク

このブログをリンクに追加する

お勧めの参考書、ノート

数学でお勧めのノートは
KOKUYOの無地
理由




センター試験は過去問が大切


チャートが終わったらお勧め
大学への数学1対1シリーズ
数学1


数学A


数学2


数学B


数学3


数学C

月別アーカイブ

ブログ内検索

RSSフィード

最近のトラックバック

ブロとも申請フォーム

この人とブロともになる

  1. 無料アクセス解析