競技数学解説

OMC対策（A,C分野：漸化式)

漸化式,OMC,競技数学

本記事の前提知識

　数学Bの教科書に載っている漸化式がある程度解ければ十分である．一応例題を用意しておく．

　以下の漸化式を解け．
(1)　 $a_{1} = 2, a_{n + 1} = 3 a_{n} + 2$
(2)　 $a_{1} = 4, a_{n + 1} = 4 a_{n}^{3}$

　解答は省略する．

OMCにおける漸化式の問題

　OMCにおける漸化式の問題は，大きく $2$ パターン存在する．

そもそも漸化式が与えられているパターン
漸化式も自分で作らないといけないパターン

　競技数学に慣れていない人は，後者の方が難しいように思われるかもしれないが，実際はそうでもない．前者のパターンは，簡単じゃないからこそ問題になっていることが多い．もちろん，後者のタイプが必ずしも簡単というわけでもないから，結局はどちらも心してかかる必要がある．
　いずれにせよ，OMCにおける漸化式の問題はA分野でもC分野でも出題される，頻出分野だと言えよう．　

漸化式の問題のタイプ

　これも，大きく $2$ パターンに分かれる．

一般項が求まる問題
一般項が容易には求まらず，計算で $a_{10}$ などの値を求めさせる問題

　具体例を使って説明した方がよいだろうから，次の例題を見てほしい．

一般項が求まる問題

(1)　 $a_{1} = 1, a_{n + 1} = \sqrt{n^{2} + 2 a_{n} + 1}$ のとき $a_{100}$ を求めよ．
(2)　 $a_{1} = 1, a_{n + 1} = ⌊ \frac{(a_{n} + 1)^{2}}{a_{n}} ⌋$ のとき $a_{100}$ を求めよ．
(3)　 $a_{1} = 1, a_{n + 1} = a_{n}^{2} + 4 a_{n} + 2$ のとき $a_{100}$ を求めよ．

　一般に，ルートや天井関数・床関数，二乗などが入っているときには，漸化式が解けない場合もある．しかしこれらの問題は $a_{100}$ を求めよと言われている．間違いなく一般項がわかるはずだと考えよう．

解答

(1)　実験すれば

a_{n} = n

であることがすぐわかるだろう．帰納法を使えば簡単に示せる．

a_{100} = 100

．
(2)　

a_{2} = 4

で，それ以降は

a_{n + 1} = a_{n} + 2

となる．よって

a_{100} = 200

．
(3)　

a_{n + 1} + 2 = (a_{n} + 2)^{2}

に気付けば簡単である．

a_{n} = 3^{2^{99}} - 2

である．

一般項を求めないだろう問題

(1)　 $a_{1} = a_{2} = a_{3} = 1, a_{n + 3} = a_{n + 2} + a_{n + 1} + a_{n}$ のとき， $a_{10}$ の値を求めよ．
(2)　 $a_{1} = 2, a_{2} = 4, a_{n + 2} = a_{n + 1} - 2 a_{n}$ のとき， $a_{8}$ の値を求めよ．
(3)　 $a_{1} = 1, b_{n} = 2 a_{n} + 1, a_{n + 1} = a_{n}^{2} + 2 b_{n}$ のとき， $a_{5}$ の値を求めよ．

　(1)は，一般項が求まらないわけではない（参考URLとして高校数学の美しい物語）．しかし一般項を求めるよりも，順々に $n = 1, 2, 3, \dots$ を代入していって $a_{4}$ から順に $3, 5, 9, 17, 31, 57, 105$ と求める方が早いだろう．
　(2)は，(1)以上に一般項を求めやすい問題である（大学受験数学の範疇である）．それでも $a_{8}$ くらいなら，手計算で求める方が圧倒的に早いだろう．解答は省略する．
　(3)は，一つ前の例２(3)と同じ問題である（ $b_{n}$ を消去すればわかるだろう）．つまり一般項を求めることができる．それでも $a_{5}$ を求めよと言われれば，代入しても早いだろう．OMCなら電卓が使えるので， $2$ 乗の計算も楽である．

　このように漸化式の問題が出てきた場合，まずは一般項を求めるか，手動で計算するかの選択肢がある．漸化式にもよるが，第 $10$ 項くらいを求めるなら，後者の方法でも通用するだろう． $20$ 項を超えてくると，一般項を求めるのが本筋だろうと思われる．
　なお，後者の方法は動的計画法と呼ばれ，Dynamic Programmingの頭文字を取ってDPと言うことも多い．OMCのユーザー解説等でしばしば用いられる用語なので，覚えておくとよい．

漸化式の問題を解く方法

　記事の最初に挙げた例題 $a_{1} = 2, a_{n + 1} = 3 a_{n} + 2$ を解くためには，ふつう $a_{n + 1} + 1 = 3 (a_{n} + 1)$ と変形するだろう．こうすることで，等比数列の形に帰着させることができる．
　漸化式を解く方法は，等差数列や等比数列などの，よく知った形に帰着させるのが基本である．言い換えれば，「 $a_{n + 1}$ を含む部分と $a_{n}$ を含む部分を，できるだけ似たような形にする」ということである．
　もう一度例２(3)を見てみよう．

例２(3)　再掲

　 $a_{1} = 1, a_{n + 1} = a_{n}^{2} + 4 a_{n} + 2$

　
　この漸化式は，左辺( $a_{n + 1}$ を含む部分)が $1$ 次式，右辺（ $a_{n}$ ）が $2$ 次式である．似たような形にしなければ話が進まないので，
　 $a_{n + 1} + k = (a_{n} + k)^{2}$
となるような数 $k$ が存在しないか，と発想する．この式を展開して係数を比べると $k = 2$ がわかり，展望が開けるのである．
　
　このような方針が思いつかない，あるいは通用しないという場合もある．そういうときには， $n = 1, 2, 3, \dots$ を代入してみるのもよい方法である．先ほどの例２(3)で言えば， $1, 7, 79, 6559$ となる．運がよければ，この数列を見て一般項が推測できるかもしれない．
　また， $a_{n}$ が常に $5$ 以下の非負整数であることがわかっているような場合には，周期性を持つ数列となる．そのような場合には根気よく $a_{n}$ を求めていくことで一般項がわかる，ということもある．
　まとめると，漸化式を解く問題においては，「 $a_{n + 1}$ を含む部分と $a_{n}$ を含む部分を，できるだけ似たような形にする」ことが原則である．しかし，どんどん漸化式に値を代入していく泥くさい方法も頭の片隅には残しておくのがよいだろう．

OMCの例題

　あまり簡単な問題が見つけられず，全て

300

点以上の問題である．
OMC119(D)
OMCB013(E)
OMC213(F)
OMCB014(F)
OMCB034(E)
OMCB022(E)

漸化式を自分で作る問題

　まずは基本的な例題を挙げよう．

　正四面体 $O A B C$ の頂点を移動する点 $P$ があり， $t = 0$ のとき，点 $P$ は点 $O$ の位置にある．
　点 $P$ は $1$ 秒ごとに，隣り合ういずれかの頂点を等しい確率で選び，移動する．
　時間 $t = n$ のときに，点 $P$ が点 $O$ の位置にある確率 $p_{n}$ を求めよ．

　受験数学ではよく「確率漸化式」と呼ばれるものである．この問題を解く際には， $p_{n + 1}$ と $p_{n}$ の関係式を作るだろう．より具体的には，漸化式 $p_{n + 1} = \frac{1}{3} (1 - p_{n})$ を解けばよいことになる．

　このように，漸化式が与えられているわけではないが，自力で $n$ の場合と $n + 1$ の場合を比較し，漸化式を作る問題はOMCでもよく出題される（特に，C分野の場合の数を求める問題で多く出題される）．
　例えば次のような問題である．

　A君は階段を上る際， $1$ 歩で $1$ 段， $2$ 段， $3$ 段のいずれかの上り方をする． $10$ 段の階段を上る方法は何通りか．

　漸化式を作って解くことができるので，考えてみてほしい．

解答

n

段の階段を上る方法を

a_{n}

としよう．
　

n

段目にたどり着くためには，その直前に

n - 1

段目にいるか，

n - 2

段目にいるか，

n - 3

段目にいるかのいずれかである．よって

a_{n} = a_{n - 1} + a_{n - 2} + a_{n - 3}

が成り立つ．
　

a_{1} = 1, a_{2} = 2, a_{3} = 4

を用いて，以下計算していけばよい．

1, 2, 4, 7, 13, 24, 44, 81, 149, 274

となり，

274

通りである．
　（例３(1)と漸化式は同じになるが，

a_{2}, a_{3}

の値は異なる．）

　次の問題は例５の変形バージョンである．

　A君は階段を上る際， $1$ 歩で $1$ 段， $2$ 段， $3$ 段のいずれかの上り方をできる．ただし $3$ 段上った場合，その次の $1$ 歩では $1$ 段か $2$ 段しか上れない．
　このとき， $10$ 段の階段を上る方法は何通りか．

　余事象を使う方法（例５から「続けて $3$ 段」を引き算する方法）もあるが，そうではなく，漸化式だけで解く方法を考えてみてほしい．

解答

3

段上った場合とそうでない場合とで，その後の上り方が変化する．そこで，
　　

n - 3

段目から

1

歩で

n

段目に上る場合の数を

a_{n}

　　それ以外の方法で

n

段目に上る場合の数を

b_{n}

としよう．すると漸化式は，

a_{n} = b_{n - 3}, b_{n} = a_{n - 1} + b_{n - 1} + a_{n - 2} + b_{n - 2}

である．
　

a_{1} = 1, b_{1} = 0, a_{2} = 2, b_{2} = 0, a_{3} = 3, b_{3} = 1

を用いて計算すればよい．
　答えは

a_{10} + b_{10} = 214 + 36 = 250

通りとなる．

　例５も例６も，慣れていない人には漸化式の問題だと気づけないだろう．しかし，「漸化式で解けるかもしれない」という発想さえ持っておけば，意外にも漸化式で解ける問題は多いのである．
　

OMCの例題

OMC043(B)
OMC021(C)
OMC203(E)
OMC075(C)
OMC183(D)
OMC092(D)

投稿日：3月21日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

て

800

他の人のコメント

コメントはありません。

読み込み中

て

OMC対策（A,C分野：漸化式)

本記事の前提知識
OMCにおける漸化式の問題
漸化式の問題のタイプ
漸化式の問題を解く方法
漸化式を自分で作る問題