漸化式と互いに素(逆向き帰納法)

漸化式と互いに素に関する例題です。

(例題1)
数列\(\{a_n\}\)が漸化式
\(a_{n+2}=a_{n+1}+a_{n}\)　(\(n=1,2,3,\cdots\))
\(a_1=1\),　\(a_2=1\)
によって定義されている。このとき、どの隣り合う\(2\)項も互いに素であることを証明せよ。

互いに素をそのまま数式で表すのは難しいので、約数をもつ(ある数の倍数になる)と仮定して矛盾を示します(背理法)。ここで、通常の前向きの帰納法を用いると、\(a_k,a_{k+1}\)が\(p\ (≠1)\)の倍数とすると、\(a_{k+2}\)も\(p\)の倍数となるから、\(k\)以降の自然数でで\(a_{n}\)は\(p\)の倍数となります。しかし\(a_n\)の後ろのほうにこの結論と矛盾する条件がないのでうまくいきません。そこで漸化式を
\(a_{n}=a_{n+2}-a_{n+1}\)
と逆向きに見て、\(a_{k+2},a_{k+1}\) が\(p\)の倍数だと、\(a_k\) が\(p\)の倍数という逆向き帰納法を用いてみます。すると初期の\(a_1,a_2\)が互いに素なので、矛盾が示せます。
なお背理法の仮定は、どの隣り合う2項も互いに素であることの否定なので、「ある隣り合う2項が\(p\)の倍数である」です。(どこか1か所で約数をもてば、もともとの証明したい結論であるどの2項も互いに素とは違うものになる)

(解答)
(ア)\(a_1=a_2=1\) だから、この2項は互いに素である。

(イ)\(k≧1\)とする。ある隣り合う2項\(a_{k+2},a_{k+1}\)が互いに素でない、つまり\(1\)でない正の公約数\(p\)をもつと仮定する。\(a_{k+2},a_{k+1}\)はどちらも\(p\)の倍数で、漸化式

\(a_k=a_{k+2}-a_{k+1}\)

より、右辺は\(p\)の倍数だから、\(a_k\)も\(p\)の倍数となる。
これを繰り返すことで
\(a_k,a_{k-1},\cdots,a_3,a_2,a_1\)
はすべて\(p\)の倍数となる。しかし、\(a_1=a_2=1\) より矛盾する。
したがって、\(a_2\)以降の隣り合う2項は互いに素である。

(ア)(イ)より、どの隣り合う\(2\)項も互いに素である。

漸化式 \(a_k=a_{k+2}-a_{k+1}\) は、\(k≧1\) で成り立つので、(イ)だけだと\(a_3,a_2\)以降の隣り合う2項についての証明なるので、(ア)も追加しました。

(例題2)
\(n\)は正の整数とする。\(x^{n+1}\)を\(x^2-x-1\)で割った余りを\(a_nx+b_n\)とおく。

(1)数列\(\{a_n\},\{b_n\}\)　(\(n=1,2,3,\cdots\)) は、
\(a_{n+1}=a_{n}+b_{n}\)
\(b_{n+1}=a_n\)
を満たすことを示せ。
(2)\(n=1,2,3,\cdots\)に対して、\(a_n,b_n\)はともに正の整数で、互いに素であることを証明せよ。

因数定理を用いようとすると、 \(x=\displaystyle\frac{1+\sqrt{5}}{2}\) を代入することになるので、却下です。

(解答)
(1)

(2)の誘導になっています。
\(x^{n+1}=(x^2-x-1)Q(x)+a_nx+b_n\)
が成り立つので、両辺に\(x\)を掛けて漸化式を導きます。

\(x^{n+1}\)を\(x^2-x-1\)で割ったときの商を\(Q_n(x)\)とすると

\(x^{n+1}=(x^2-x-1)Q_n(x)+a_nx+b_n\)

両辺\(x\)倍して
\(x^{n+2}=(x^2-x-1)xQ_n(x)+a_nx^2+b_nx\)

(後ろ2項を\(x^2-x-1\)で割って)

\(=(x^2-x-1)xQ_n(x)+a_n(x^2-x-1)+a_nx+a_n+b_nx\)
\(=(xQ_n(x)+a_n)(x^2-x-1)+\color{blue}{(a_n+b_n)x+a_n}\)

\(x_{n+2}=(x^2-x-1)Q_{n+1}(x)+\color{blue}{a_{n+1}x+b_{n+1}}\)
と比較して

\(a_{n+1}=a_{n}+b_{n}\)
\(b_{n+1}=a_n\)

(2)

まずは\(a_n,b_n\)が正の整数となることの証明をします。漸化式を解こうとすると複雑になりそうなのでそのままの形で進めます。
漸化式と相性のいい帰納法で証明していくことになりますが、\(a_1,b_1\)が必要になるのでも求めておきます。

まず\(a_n,b_n\)が正の整数となることを示す。

\(n=1\) のとき
\(x^2=(x^2-x-1)+x+1\) より
\(a_1=1\),　\(b_1=1\)

(1)の漸化式
\(a_{n+1}=a_{n}+b_{n}\)・・・①
\(b_{n+1}=a_n\)・・・②

より、\(a_1,b_1\)が正の整数だから帰納的にすべての自然数\(n\)で\(a_n,b_n\)は正の整数となる。
(丁寧にやるなら帰納法を使う)

次に、\(a_n,b_n\)が互いに素であることを示す。

(例題1)と同様の背理法を用いたいと思います。

(ア)\(a_1=b_1=1\) だから、\(a_1,b_1\)は互いに素。

(イ)ある \(a_{k+1},b_{k+1}\) (\(k≧1\)) が公約数\(p\ (≧2)\)をもつと仮定すると
\(a_{k+1}=pA\),　\(b_{k+1}=pB\)　(\(A,B\)は自然数)
と表せる。漸化式①②より

\(pA=a_{k}+b_{k}\)・・・③
\(pB=a_{k}\)・・・④

④から\(a_k\)も\(p\)の倍数。これを③に代入して
\(pA=pB+b_k\)
\(b_k=p(A-B)\)
よって、\(b_k\)も\(p\)の倍数。

これを繰り返すことで
\(a_k,b_k,a_{k-1},b_{k-1},\cdots,a_1,b_1\)
はすべて\(p\)の倍数となるが、\(a_1=b_1=1\) と矛盾。

ゆえに、\(n≧2\) において \(a_n,b_n\) は互いに素である。

(ア)(イ)より\(a_n,b_n\)は、任意の自然数\(n\)で互いに素である。

少し補足しておくと、問題文の意味することは「各\(n\)について、\(a_n,b_n\)が互いに素」(同じ番号の項について互いに素) ということです。項の番号が違う場合には公約数をもつこともあり得ます。

以上になります。お疲れさまでした。
ここまで見ていただきありがとうございました。
next→漸化式と不等式　 back→漸化式と倍数・余り