当ページの内容は数学的帰納法を学習済みであることを前提としています。
n$を自然数とし,\ 数列$\{a_n\}$を$a_1=1,\ \ a_2=1,\ \ a_{n+2}=a_{n+1}+a_n$で定める.
(1)\ \ 一般項$a_n$を求めよ.
(2)\ \ $m$を自然数とするとき,\ $a_{4m}$は3の倍数であることを示せ.
(3)\ \ $a_{n+1}$と$a_n$が互いに素であることを示せ.
(4)\ \ $a_1+a_2+･･･+a_n=a_{n+2}-1$が成り立つことを示せ.
(5)\ \ $a_na_{n+2}-{a_{n+1^2=(-\,1)^{n+1}$が成り立つことを示せ.
(6)\ \ $lim{n\to∞}a_{n+1{a_n}$を求めよ. (数Iフィボナッチ数列の有名性質とその証明 \\
ある項が直前の2項の和である数列をフィボナッチ数列という.
各項の値を具体的に書き出すと $1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ ･･････$}
最も単純な隣接三項間型漸化式で定義されることもあり,\ 入試では超頻出である.
非常に多くの性質が知られており,\ ここでは頻出のものや応用性の高いものを取り上げる.
(1)\ \ $x^2-x-1=0$の2解を$α,\ β\ (α<β)$とすると,\ 解と係数の関係}より $α+β=1}$
隣接3項間型漸化式a_{n+2}+pa_{n+1}+qa_n=0}の一般項の求め方を復習する.
まず,\ a_{n+2}=x^2,\ a_{n+1}=x,\ a_n=1とした特性方程式を解く.
2解を\,α,\ β\,とすると,\ 2つの等比数列型\
a_{n+2}-α a_{n+1}=β(a_{n+1}-α a_n)
a_{n+2}-β a_{n+1}=α(a_{n+1}-β a_n)
これを解くと\
a_{n+1}-α a_n=(a_2-α a_1)β^{n-1}
a_{n+1}-β a_n=(a_2-β a_1)α^{n-1}
-.5zw}となるので,\ 2式からa_{n+1}\,を消去する.
ただし,\ フィボナッチ数列の場合には特有の扱いがある.
a_{n+2}-α a_{n+1}=β(a_{n+1}-α a_n)\,より,\ \{a_{n+1}-α a_n\}は初項a_2-α a_1,\ 公比\,β\,の等比数列である.
a_2-α a_1=1-α\,となるが,\ α+β=1より1-α=β\,である.
このように,\ 解と係数の関係}を用いると,\ 一般項がa_n=β^n-α^n}{β-α}\ (ビネの公式})と簡潔に表せる.
(2)\ \ $a_1=a_2=1$と漸化式の形から,\ 帰納的に$a_n$は自然数}である.
[1]\ \ $m=1}$のとき\ \ $a_4=3$より,\ 3の倍数である.
[2]\ \ $m=k}$のとき\ \ $a_{4k}$が3の倍数であると仮定すると,\ $a_{4k}=3l\ (l:自然数)}$とおける.}
$a_{4k+1}+2l$は自然数であるから,\ $a_{4(k+1)}$は3の倍数}である.
∴ [1],\ [2]\,より,\ すべての自然数mに対してa_{4m}\,は3の倍数である.}$}
$a_n\,を3で割ったときの余りを{r_n}\,とすると$
ある項の余りは直前の2項の余りで定まる.}{周期8で循環}する.
∴$ $r_4=r_8=0}$より,\ $a_{4m}\,は3の倍数}$である.}
整数論的性質は(1)で求めた一般項からはわからないので,\ 漸化式のまま探る}ことになる.
以降の議論は各項が整数でなければ成り立たない.
よって,\ 最初にすべての項が整数であることを確認している.
数学的帰納法を適用するまでもなくほぼ明らかなので,\ 「帰納的に」という表現で済ませた.
仮に数学的帰納法を適用する場合,\ 直前2つを仮定する必要がある.
[1]\ \ k=1,\ 2のとき a_1=a_2=1より,\ a_1,\ a_2\,は自然数である.
[2]\ \ n=k,\ k+1のとき a_{k},\ a_{k+1}\,が自然数であると仮定する.
\ \ n=k,\ k+1のとき} a_{k+2}=a_{k+1}+a_k\,より,\ a_{k+2}\,も自然数である.
さて,\ a_4,\ a_8,\ a_{12},\ a_{16},\ ･･･\ が3の倍数であることの証明}が題意である.
整数と数列の融合問題だが,\ 数列に比重を置いて扱うならば,\ 数学的帰納法の利用が自然である.
漸化式に関する命題を数学的帰納法で証明する場合,\ 仮定だけでなく漸化式自体も利用する.}
仮定a_{4k}=3lを利用できるまで,\ a_{n+2}=a_{n+1}+a_n\,を繰り返し適用していけばよい.
整数に比重を置いて考えると別解となる.
漸化式で定義された整数列の余りの数列は必ず一定周期で循環する}のであった.
整数カテゴリ「整数値漸化式」でも同種の問題を取り上げたが,\ 改めて理由を確認する.
a_n\,を3で割ったときの商をq_n,\ 余りをr_n\,とすると
よって,\ a_{n+2}\,を3で割ったときの余りr_{n+2}\,は,\ r_{n+1}+r_n\,を3で割ったときの余りに等しい.
合同式を用いて表すと,\ r_{n+2}≡ r_{n+1}+r_n±od3}となる.
ここで,\ 3で割ったときの余りは0,\ 1,\ 2の3種類である.
よって,\ (r_{n},\ r_{n+1})のパターンは最大でも3^2=9通りしかない.
ゆえに,\ (r_{10},\ r_{11})までには必ず(r_1,\ r_2)と同じ余りの組が現れ,\ それ以降は循環する.}
一般に「\,aとbを3で割ったときの余りが等しい\,⇔\,a-bが3の倍数}」が成り立つのであった.
よって,\ a_{n+8}-a_n\,が3の倍数であることを示すことにより,\ 周期8であることを示す方法もある.
このとき,\ a_{n+8}\,にa_{n+2}=a_{n+1}+a_n\,を繰り返し適用していくことになる.
しかし,\ a_{n+4}\,程度ならまだしも,\ a_{n+8}\,がa_{n+1}\,とa_n\,で表されるまで適用するのは面倒である
(3)\ \ $a_1=a_2=1$と漸化式の形から,\ 帰納的に$a_n$は自然数}である.
[1]\ \ $n=1}$のとき $a_2=1$と$a_1=1$は互いに素である.
[2]\ \ $n=k}$のとき $a_{k+1}$と$a_k$が互いに素であると仮定}する.
$a_{k+2}$と$a_{k+1}$が素数の公約数$p$をもつと仮定}する(背理法).
このとき,\ $a_{k+2}=pl,\ \ a_{k+1}=pm\ (l,\ m:正の整数)$とおける.
$a_{k+2}=a_{k+1}+a_k}$より $a_k=p(l-m)$
よって,\ $a_{k+1}$と$a_k$は共に$p$の倍数である.
これは,\ $a_{k+1}$と$a_k$が互いに素であるという数学的帰納法の仮定に矛盾}する.
よって,\ 背理法の仮定は誤りであり,\ $a_{k+2}$と$a_{k+1}$は互いに素}である.
∴$ [1],\ [2]\,より,\ すべての自然数$n}$に対して$a_{n+1}\,とa_n}$は互いに素である.
$n=1$のとき $a_2=1$と$a_1=1$は互いに素である.
$n≧2$のとき,\ ある$a_{n+1},\ a_n$が素数の公約数$p$をもつと仮定}する.
このとき,\ $a_{n+1}=pl,\ a_n=pm\ (l,\ m:正の整数)$とおける.
$a_{n+1}=a_n+a_{n-1$より $a_{n-1}=p(l-m)$
よって,\ $a_{n+1},\ a_n$が共に$p$の倍数であるとき,\ $a_{n},\ a_{n-1}$も共に$p$の倍数である.
帰納的に$a_2,\ a_1$も$p$の倍数となるが,\ これは$a_2=a_1=1$であることと矛盾}する.
∴$ すべての自然数$n}$に対して$a_{n+1}\,とa_n}$は互いに素である.
$n=1$のとき $a_2=1$と$a_1=1$は互いに素である.
$n≧2$のとき $a_{n+1}=a_n+a_{n-1$
よって $g(a_{n+1},\ a_{n})=g(a_{n},\ a_{n-1})=･･････=g(a_2,\ a_1)=g(1,\ 1)=1$}
∴$ すべての自然数$n}$に対して$a_{n+1}\,とa_n}$は互いに素である.
数学的帰納法}を利用して証明する.
a_{k+1},\ a_k\,が互いに素であると仮定し,\ a_{k+2},\ a_{k+1}\,も互いに素であることを示せばよい.
互いに素の証明は,\ 素数の公約数pをもつと仮定し,\ 矛盾を導く}のであった(背理法}).
このとき,\ 数学的帰納法の仮定と背理法の仮定を混同しないように注意する.
数学的帰納法の仮定(n=k)を利用して背理法の仮定が誤りであることを示す}ことになる.
別解1のように,\ 漸化式を逆に利用して繰り下げていくことで矛盾を示す方法}もある.
n=1のときa_{n-1}\,が定義されないので,\ 場合分けした.
別解2はユークリッドの互除法の原理}を利用するものである.
a=bq+rという形の式に対して,\ g(a,\ b)=g(b,\ r)が成り立つ}のであった.
a_{n+1}=a_n･1+a_{n-1}\,より,\ g(a_{n+1},\ a_n)=g(a_n,\ a_{n-1})が成り立つ.
なお,\ g(a,\ b)は2数a,\ bの最大公約数を表す.
[1]\ \ $n=1}$のとき $(左辺)=a_1=1,\ \ (右辺)=a_3-1=2-1=1$より成り立つ. {$a_1+a_2+･･･+a_k=a_{k+2}-1$が成り立つと仮定}する.
∴$ [1],\ [2]\,より,\ すべての自然数$n}$について与式は成り立つ.
フィボナッチ数列の和を求めたいときに役立つ関係式の証明である.
元の漸化式をa_n=の形にして各項に適用する}という非常にスマートな解法がある.
スマートな解法を知らなくても,\ 数学的帰納法を利用すると容易に証明できる.
a_{n+2}=a_{n+1}+a_n\,よりa_{k+3}=a_{k+2}+a_{k+1\,が成り立つことを利用する.
試験で出るフィボナッチ数列の関係式のほとんどは数学的帰納法で証明できる}と思ってよい.
(1)の結果と等比数列の和の公式を利用して示すことも可能である.
解と係数の関係より
式が複雑な場合,\ 何が仮定で何を証明すべきかを強く意識して処理する必要がある.
証明すべき式は,\ a_{k+1}a_{k+3}-{a_{k+2^2=(-\,1)^{k+2}\,である.
元の漸化式a_{n+2}=a_{n+1}+a_n\,も利用してこれを証明する.
a_k,\ a_{k+1},\ a_{k+2}\,で表された仮定を利用することを目指し,\ a_{k+3}\,を消去する.
仮定を適用した後にa_{k+2}\,をくくりだし,\ さらにa_{k+2}=a_{k+1}+a_k\,を利用すると証明できる.
以下のようによりスマートに処理することもできる.
数III}の極限を学習済みの学生にとっては基本的な無限等比数列の極限計算}である.
分母の公比の絶対値が最大の項\,β^n\,で分母分子を割る}と,\ 不定形が解消される.
本問から,\ フィボナッチ数列の連続する2項の比は\,1+√5}{2}\ (黄金比)に近づいていく}とわかる
一般項a_n\,から逆に漸化式a_{n+2}=a_{n+1}+a_n\,を導く問題も頻出である.
一般項a_n\,が\,α^n±β^n\,の形の場合,\ 方程式を利用して漸化式を作成する}方法がある.
まず,\ α,\ β\,を2解にもつ2次方程式を作成する.
その1つは(x-α)(x-β)=0,\ つまりx^2-(α+β)x+αβ=0である.
こうしてできた2次方程式に\,α,\ β\,を代入し,\ 両辺にそれぞれ\,α^n,\ β^n\,を掛ける.
この2式を組み合わせることにより,\ a_{n+2},\ a_{n+1},\ a_n\,の形を作成できる.
直接的に示そうとすると以下となる.
単純な式変形だけでは到底示せそうにないので,\ 数学的帰納法で証明する.
一度経験してしまえばそこまで難しいものではないが,\ 初見では難問である.
a_na_{n+2}-{a_{n+1^2=(-\,1)^{n+1}\,とa_{k+2}=a_{k+1}+a_k\,を利用し,\ a_{k+3}=a_{k+2}+a_{k+1}\,を示すことになる.
文字だけではわかりづらいので,\ k=1のときの具体例を示しておく.
a_na_{n+2}-{a_{n+1^2=(-\,1)^{n+1}\,より,\ a_1a_3-{a_2}^2=1,\ \ a_2a_4-{a_3}^2=-\,1\ が成り立つ.
辺々を足すと a_2a_4+a_1a_3-{a_3}^2-{a_2}^2=0 (右辺が0になるのがポイント)
a_2,\ a_3,\ a_4\,の関係式を導きたいので,\ 仮定a_3=a_2+a_1\,を用いてa_1\,を消去する.
実際には,\ a_{k+1}≠0を示す必要がある.
そこで,\ kだけでなくk以下のすべての自然数に対してa_{k+2}=a_{k+1}+a_k\,が成り立つと仮定した.
a_1=1,\ a_2=1,\ a_3=a_2+a_1,\ a_4=a_3+a_2,\ ･･････,\ a_{k+1}=a_k+a_{k-1}\,より,\ a_{k+1}>0である.
