漸化式と倍数・余り

漸化式を敢えて解かない整数問題について見ていきます。

 

(例題1)
自然数\(n\)に対して、正の整数\(a_n,b_n\)を
\((3+\sqrt{2})^n=a_n+b_n\sqrt{2}\)
によって定める。このとき、

(1)\(a_1,b_1\)と\(a_2,b_2\)を求めよ。
(2)\(a_{n+1},b_{n+1}\) を \(a_n,b_n\) を用いて表せ。
(3)\(n\)が奇数のとき、\(a_n,b_n\)はともに奇数であって、\(n\)が偶数のとき、\(a_n\)は奇数で、\(b_n\)は偶数であることを数学的帰納法によって示せ。

 

(1)(2)の誘導はサラッと解いてきます。

(1)
\((3+\sqrt{2})=3+1\cdot\sqrt{2}\)
\((3+\sqrt{2})^2=11+6\sqrt{2}\)

よって
\(a_1=3\), \(b_1=1\)
\(a_2=11\), \(b_2=6\)

(2)
\(a_{n+1}+b_{n+1}\sqrt{2}\)

\(=(3+\sqrt{2})^{n+1}\)
\(=(3+\sqrt{2})(3+\sqrt{2})^n\)
\(=(3+\sqrt{2})(a_n+b_n\sqrt{2})\)

\(=(3a_n+2b_n)+(a_n+3b_n)\sqrt{2}\)

\(a_n,b_n\)は正の整数(有理数)だから
\(a_{n+1}=3a_n+2b_n\)
\(b_{n+1}=a_n+3b_n\)

(3)

連立漸化式から\(a_n,b_n\)の一般項は求まりますが、複雑な式になりかえって面倒になります。この手の漸化式が絡む整数問題は漸化式をそのままの形で扱うことも重要です。
問題文の記述の通り数学的帰納法で証明していくことなります。今回は\(a_n,b_n\)別々に証明していきますが、場合によってはまとめて証明することもあります。

まず\(a_n\)について、すべての自然数\(n\)で奇数になることを示す。

\(a_{n+1}=3a_n+2b_n\)・・・①

[1]\(n=1\)のとき
\(a_1=3\) だから奇数であり成り立つ。

[2]\(n=k\)のとき (\(k=1,2,\cdots\))
\(a_k\)が奇数であると仮定する。
このとき①より
\(a_{k+1}=3a_k+2b_k\)
だから、(奇数)×(奇数)+(偶数) より、\(a_{k+1}\) は奇数になる。

したがって[1][2]よりすべての自然数\(n\)で\(a_n\)は奇数

次に\(b_n\)について示す。

偶奇で結論が違うので、2つの仮定を使います。
この帰納法は、\(n=1,2\) で成立→\(n=3,4\) で成立→\(n=5,6\) で成立・・・という構成になっています。

\(b_{n+1}=a_n+3b_n\)・・・②

[1]\(n=1,2\) のとき
\(b_1=1\), \(b_2=6\) より
\(n=1\) で奇数、\(n=2\) で偶数になる。

[2]\(n=2k-1,2k\) のとき (\(k=1,2,\cdots\))
\(b_{2k-1}\)は奇数、\(b_{2k}\)は偶数であると仮定する。

このとき②に\(n=2k\)を代入して
\(b_{2k+1}=a_{2k}+3b_{2k}\)
\(a_n\)は奇数だから、(奇数)+(奇数)×(偶数) より\(b_{2k+1}\)は奇数

②に\(n=2k+1\) を代入して
\(b_{2k+2}=a_{2k+1}+3b_{2k+1}\)
よって (奇数)+(奇数)×(奇数) となるから \(b_{2k+2}\)は偶数

したがって[1][2]よりすべての自然数\(n\)について、\(b_n\)は\(n\)が奇数のとき奇数、\(n\)が偶数のとき偶数となる。

以上より題意は示された。

 

 

 

 

(例題2)
2次方程式 \(x^2-4x+1=0\) の2つの実数解のうち大きいものを\(α\)、小さいものを\(β\)とする。\(n=1,2,3,\cdots\) に対し、
\(s_n=α^n+β^n\)
とおく。

(1)\(s_1,s_2,s_3\)を求めよ。また、\(n≧3\)に対し、\(s_n\)を\(s_{n-1}\)と\(s_{n-2}\)で表せ。
(2)\(s_n\)は正の整数であることを示し、\(s_{2003}\)の\(1\)の位の数を求めよ。
(3)\(α^{2003}\)以下の最大の整数の\(1\)の位の数を求めよ。

 

 

(解答)
(1)

\(x^2-4x+1=0\) を解くと \(x=2±\sqrt{3}\) (\(α,β\)になる) です。そのまま直接計算するより、\(α^n+β^n\) が対称式であることに着目して、解と係数の関係を利用します。

解と係数の関係から
\(α+β=4\), \(αβ=1\)

よって
\(s_1=α+β=4\)
\(s_2=α^2+β^2=(α+β)^2-2αβ=14\)
\(s_3=(α+β)^3-3αβ(α+β)=52\)

漸化式のほうですが、\(α^n+β^n=(α^{n-1}+β^{n-1})(α+β)・・・\) という形を目指し、余分な項を調整していきます。

また
\(α^n+β^n\)
\(=(α^{n-1}+β^{n-1})(α+β)-(α^{n-1}β+αβ^{n-1})\)
\(=(α^{n-1}+β^{n-1})(α+β)-αβ(α^{n-2}+β^{n-2})\)
\(=4(α^{n-1}+β^{n-1})-(α^{n-2}+β^{n-2})\)

よって
\(s_{n}=4s_{n-1}-s_{n-2}\)

 

(2)

漸化式を単純に解いても、複雑な式(特性方程式の解が無理数になる)になるので却下です。
よって漸化式そのままの形で扱っていきますが、漸化式と初期条件\(s_1,s_2\)から、\(s_n\)は整数であることは簡単に分かります。また正の整数との記載があるのでこれは別に示します。ただし正であることは\(α,β\)はどちらも正であるから明らかです。

\(α=2+\sqrt{3}>0\), \(β=2-\sqrt{3}>0\) より
\(s_n=α^{n}+β^{n}\) は正の数

また、漸化式
\(s_{n}=4s_{n-1}-s_{n-2}\)
と、\(s_1=4\), \(s_2=14\) より、帰納的に\(s_n\)は整数となることが分かる。

よって\(s_n\)は正の整数

次に\(s_{2003}\)の1の位の数を求めます。まず見当をつけるために実験してみると、1の位だけとりあげて
\(s_1≡4\), \(s_2≡4\), \(s_3≡2\), \(s_4≡4\), \(s_5≡4\), \(s_6≡2\),・・・ となり、\(4,4,2,4,4,2\cdots\) の繰り返しになることが予測できます。これで解答にしてもよいですが、丁寧にやるなら帰納法でこのループ性を証明した後に、\(s_{2003}\) つまり\(2003\)番目がどうなるかを求めることになります。解答では 1の位なので\(\mathrm{mod}10\) で証明していきます。

次に、漸化式と\(s_1,s_2\)から項を具体的に求めると\(1\)の位は
\(4,4,2,4,4,2,\cdots\) となるから、\(4,4,2\) の繰り返しになると予想できる。これを数学的帰納法で証明する。

以下\(\mathrm{mod}10\)とした合同式を考える。

漸化式より
\(s_{n}≡4s_{n-1}-s_{n-2}\)・・・①

[1]\(n=1,2,3\) のとき
\(s_1≡4\), \(s_2≡14≡4\), \(s_3≡52≡2\) より成立する。

[2]\(n=3k-2,3k-1,3k\) のとき (\(k=1,2,\cdots\))
\(s_{3k-2}≡4\), \(s_{3k-1}≡4\), \(s_{3k}≡2\) であると仮定する。

このとき①と仮定から
\(s_{3k+1}≡4s_{3k}-s_{3k-1}≡4\cdot2-4≡4\)
よって \(s_{3k+1}≡4\)

またこの式と①と仮定から
\(s_{3k+2}≡4s_{3k+1}-s_{3k}≡4\cdot4-2≡14≡4\)
よって \(s_{3k+2}≡4\)

同様に
\(s_{3k+3}≡4s_{3k+2}-s_{3k+1}≡4\cdot4-4≡12≡2\)
よって \(s_{3k+3}≡2\)

[1][2]より\(s_n\)の\(1\)の位は\(4,4,2,4,4,2,\cdots\)の繰り返しになる。

したがって\(s_{2003}\)の\(1\)の位は
\(2003=3×667+2\) より \(4,4,2\) の2番目になるから
\(4\)

(3)

\(α^{n}\)の整数部分の1の位について求める問題です。\(α^n=(2+\sqrt{3})^n\) を直接考えるのは大変です。そもそも今までの誘導を考えると、\(s_n=α^n+β^n\) を考えるのは分かると思います。
ここで\(β\)が小さい数であることに着目します。\(β=2-\sqrt{3}≒0.27\) なので \(0<β^n<1\) になります。\(s_n\)は整数になるので、\(s_{2003}=α^{2003}+β^{2003}\) が具体的にどのような式になるかというと、\(24=23.9+0.1\) のような形(数値は適当です)になります。するとこの式だと\(α^{2003}\)の整数部分は\(23\)となるので、\(s_{2003}\) の整数部分より\(1\)小さいことになります。以上のことを不等式で表していきます。

\(β=2-\sqrt{3}\) だから、\(0<β<1\)
よって、\(0<β^{2003}<1\)

よって \(α^{2003}=s_{2003}-β^{2003}\) より
\(s_{2003}-1<α^{2003}<s_{2003}\)
が成り立ち、\(s_{2003}\)は正の整数だから、\(α^{2003}\)以下の最大の整数は \(s_{2003}-1\) である。したがって(2)より\(s_{2003}\)の\(1\)の位は\(4\)だから、\(α^{2003}\)以下の最大の整数の\(1\)の位は\(3\)である。

 

 

 

 

以上になります。お疲れさまでした。
ここまで見ていただきありがとうございました。
next→漸化式と互いに素(逆向き帰納法) back→積分と漸化式

タイトルとURLをコピーしました