漸化式を敢えて解かない整数問題について見ていきます。
(例題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)
\((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\)について、すべての自然数\(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\)について示す。
この帰納法は、\(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)
解と係数の関係から
\(α+β=4\), \(αβ=1\)
よって
\(s_1=α+β=4\)
\(s_2=α^2+β^2=(α+β)^2-2αβ=14\)
\(s_3=(α+β)^3-3αβ(α+β)=52\)
また
\(α^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_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)
ここで\(β\)が小さい数であることに着目します。\(β=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→積分と漸化式