整数からなる数列\suuretu{a_n}を次に示す漸化式によって定める.$ \\[.5zh] \hspace{.5zw}$ a_1=1,\ \ a_2=3,\ \ a_{n+2}=3a_{n+1}-7a_n\ \ (n=1,\ 2,\ \cdots\cdots)$ \\[.5zh] \hspace{.5zw}$このとき,\ a_n\,が5の倍数となるための条件を求めよ.$ [\,東京大・改\,] 整数値漸化式} \phantom{ (1)}\ \ よって,\ \textcolor{red}{$a_{n+4}$と$a_n$を5で割ったときの余りは等しい.} \\[.2zh] \phantom{ (1)}\ \ ゆえに,\ $a_n$を5で割ったときの余りは\textcolor{red}{周期4で循環}する. \centerline{$\therefore$ $a_n$が5の倍数となるための条件は,\ $\bm{nが4の倍数}$となることである.} \\\\[1zh] \betu\ \ $a_n\,を5で割ったときの余りを{r_n}\,とすると$ \phantom{ (1)}\ \ 漸化式より,\ \textcolor{forestgreen}{ある項の余りは直前の2項の余りで定まる.{周期4で循環}する. \\\\ \centerline{$\therefore$ $a_n$が5の倍数となるための条件は,\ $\bm{nが4の倍数}$となることである.} \\\\ 漸化式は,\ 基本的には数\text B:数列の学習内容である. \\[.2zh] ただし,\ 一般項を求めるのではなく整数からなる数列の性質を探るのならば,\ ほぼ数\text Aの範疇である. \\[.2zh] 数\text Bを学習すると一般項a_n\,を求めたくなるが,\ \bm{整数論的性質は漸化式のまま探る}ことになる. \\[1zh] 整数値漸化式の余りの問題では,\ \bm{余りの数列\{r_n\}が一定周期で循環する}という知識が重要になる. \\[.2zh] まずは本問を例にその理由を確認する. \\[1zh] a_n\,を5で割ったときの商をq_n,\ 余りをr_n\,とすると よって,\ a_{n+2}\,を5で割ったときの余りr_{n+2}\,は,\ 3r_{n+1}-7r_n\,を5で割ったときの余りに等しい. \\[.2zh] 合同式を用いて表すと,\ \bm{r_{n+2}\equiv3r_{n+1}-7r_n\ \pmod5}となる. \\[.2zh] このように,\ 漸化式は合同式を用いて余りの漸化式に変換することができる. \\[1zh] 要するに,\ \bm{ある項を5で割ったときの余りは,\ 直前の2項を5で割ったときの余りで決まる.} \\[.2zh] 例えば,\ r_1\equiv1,\ r_2\equiv3より,\ r_3\equiv3r_2-7r_1\equiv2である. \\[1zh] ここで,\ 5で割ったときの余りは0,\ 1,\ 2,\ 3,\ 4の5種類である. \\[.2zh] この5数から2数(重複可)を選んで並べるときの場合の数は5^2=25通りである. \\[.2zh] よって,\ (r_2,\ r_3),\ \cdots,\ (r_{26},\ r_{27})の25組の中に必ず(r_1,\ r_2)と同じものが現れる(\bm{部屋割り論法}). \\[.2zh] 25通りのパターンしかないから,\ 26組目までには必ず重複が生じるという単純な論理である. \\[.2zh] そして,\ 一旦\bm{(r_1,\ r_2)と同じ余りの組が現れると,\ それ以降は循環する.} \\[1zh] 実際に問題を解く上では,\ まず\bm{周期を確認する}ことが重要である.\ ひたすら計算して調べる. (r_1,\ r_2)=(r_5,\ r_6)より,\ \bm{r_6\,まで計算すると周期4で循環することがわかる.} 後は周期が4であることをどのようにして示すかが問題になる. \\[.2zh] 周期が4ということは,\ a_{n+4}\,とa_n\,を5で割ったときの余りが等しくなるということである. \\[.2zh] 一般に「\,\bm{aとbを5で割ったときの余りが等しい\,\Longleftrightarrow\,a-bが5の倍数}」が成り立つのであった. \\[.2zh] \bm{a_{n+4}-a_n\,に漸化式を繰り返し適用していく}と,\ 5の倍数であることが示される. \\[1zh] 先程示したように,\ \bm{元の漸化式を合同式を用いて余りの漸化式に変換する}と簡潔に済む(別解). \\[.2zh] 計算が楽になるように,\ 7\equiv2\pmod5も適用した. n$を正の整数とする.\ \ $x^{n+1}$を$x^2-x-1$で割った余りを$a_nx+b_n$とおく. \\[1zh] \hspace{.5zw} (1)\ \ 数列$a_n,\ b_n\ (n=1,\ 2,\ 3,\ \cdots)$は\ $\begin{cases} a_{n+1}=a_n+b_n \\[.2zh] b_{n+1}=a_n \end{cases}$\hspace{-.5zw}を満たすことを示せ. \\\\[-.5zh] \hspace{.5zw} (2)\ \ $n=1,\ 2,\ 3,\ \cdots$に対して,\ $a_n,\ b_n$は共に正の整数で,\ 互いに素であることを \\[.2zh] \hspace{.5zw}\phantom{ (1)}\ \ 証明せよ. [\,東京大\,] (1)\ \ $x^{n+1}$を$x^2-x-1$で割ったときの商を$Q_n(x)$とおくと \centerline{$\therefore \maru2,\ \maru3を比較すると \bm{\begin{cases} a_{n+1}=a_n+b_n \\[.2zh] b_{n+1}=a_n よって,\ $a_1$と$b_1$は共に正の整数で互いに素である. \\[1zh] \phantom{ (1)}\ \ [2]\ \ $n=k$のとき \textcolor{cyan}{$a_k$と$b_k$が共に正の整数で互いに素であると仮定}する.より,\ $a_{k+1}$と$b_{k+1}$は共に正の整数である. \\\\[.5zh] \phantom{ (1)}\ \ \textcolor{magenta}{$a_{k+1}$と$b_{k+1}$が素数の公約数$p$をもつと仮定}する(背理法). \\[.2zh] \phantom{ (1)}\ \ このとき,\ $a_{k+1}=pl,\ \ b_{k+1}=pm\ (l,\ m:正の整数)$とおける. \phantom{ (1)}\ \ よって,\ $a_k$と$b_k$は共に$p$の倍数である. \\[1zh] \phantom{ (1)}\ \ これは,\ \textcolor{cyan}{$a_k$と$b_k$が互いに素であるという数学的帰納法の仮定に矛盾}する. \\[.2zh] \phantom{ (1)}\ \ よって,\ \textcolor{magenta}{背理法の仮定は誤りであり,\ $a_{k+1}$と$b_{k+1}$は互いに素}である. \\\\ \centerline{\scalebox{.95}[1]{$\therefore$ [1],\ [2]\,より,\ \textbf{すべての自然数$\bm{n}$に対して$\bm{a_n,\ b_n}$は共に正の整数で互いに素である.}}} \\\\\\ 互いに素の証明}\,] \\[1zh] \phantom{ (1)}\ \ $n=1$のとき $x^2=(x^2-x-1)+x+1$より $a_1=1,\ b_1=1$ \\[1zh] \phantom{ (1)}\ \ $n\geqq2$のとき,\ \textcolor{red}{ある$a_n,\ b_n$が素数の公約数$p$をもつと仮定}する. \\[.2zh] \phantom{ (1)}\ \ このとき,\ $a_n=pl,\ b_n=pm\ (l,\ m:正の整数)$とおける. \phantom{ (1)}\ \ よって,\ $a_{n-1},\ b_{n-1}$は$p$の倍数である. \\[1zh] \phantom{ (1)}\ \ \textcolor{red}{帰納的に$a_1,\ b_1$も$p$の倍数となるが,\ これは$a_1=b_1=1$であることと矛盾}する. \\\\ \centerline{$\therefore$ \textbf{すべての自然数$\bm{n}$に対して$\bm{a_n,\ b_n}$は互いに素である.}} \\\\\\ 本問は,\ 整式の割り算(数\text{I\hspace{-.1em}I})と漸化式(数\text B)と整数(数\text A)の融合問題である. \\[1zh] (1)\ \ 整式の割り算なので,\ まずは等式を作成するのが自然である. \\[.2zh] \phantom{(1)}\ \ このとき,\ \bm{nの値によって商や余りが変わる}ことに注意する. \\[.2zh] \phantom{(1)}\ \ そこで,\ ax+bではなくa_nx+b_n\,とするよう誘導されているわけである. \\[.2zh] \phantom{(1)}\ \ このように,\ \bm{n次式の余りを数列としてとらえると漸化式を作成することができる.} \\[1zh] \phantom{(1)}\ \ 実際には,\ \bm{x^{n+2}\,を2通りに表して係数比較}する. \\[.2zh] \phantom{(1)}\ \ \maru1をx倍すると,\ x^{n+2}\,をx^2-x-1で割ったときの等式を作成できる. \\[.2zh] \phantom{(1)}\ \ ここで,\ 2次式で割ったときの余りは1次以下の式でなければならない. \\[.2zh] \phantom{(1)}\ \ よって,\ \bm{a_nx^2+b_nxをさらにx^2-x-1で割る}必要がある. \\[.2zh] \phantom{(1)}\ \ 筆算でもよいが,\ ここではx^2-x-1を作ってつじつまを合わせた後,\ くくり出した. \\[1zh] (2)\ \ \bm{数学的帰納法}(数\text B)を用いて証明する. \\[.2zh] \phantom{(1)}\ \ a_n,\ b_n\,が共に正の整数であることだけならば,\ 漸化式からほぼ明らかである. \\[1zh] \phantom{(1)}\ \ 後は,\ a_k,\ b_k\,が互いに素であると仮定し,\ a_{k+1},\ b_{k+1}\,も互いに素であることを示せばよい. \\[.2zh] \phantom{(1)}\ \ \bm{互いに素の証明は,\ 素数の公約数pをもつと仮定し,\ 矛盾を導く}のであった(\bm{背理法}). \\[.2zh] \phantom{(1)}\ \ このとき,\ 数学的帰納法の仮定と背理法の仮定を混同しないように注意する. \\[.2zh] \phantom{(1)}\ \ \bm{数学的帰納法の仮定(n=k)を利用して背理法の仮定が誤りであることを示す}ことになる. \\[1zh] \phantom{(1)}\ \ 別解1のように,\ \bm{漸化式を逆に利用して繰り下げていくことで矛盾を示す方法}もある.
