整数問題 20 E###

Question

本題

本題は、漸化式と整数問題の融合問題

実際に漸化式の一般項を求めても深入りするばかり

丹念に、規則性を調べれば良いが、かなり周期が長そう

(2)
漸化式での対応は厳しい状況

識者の方のアプローチも教えてください。

以下問題

____________________________________________

ありものがたり · Accepted Answer

←補足(06/04 12:24)

今回は、漸化式の特性根がたまたま整数なので
その解法でも解けてしまうのだが、
「線型漸化式の各項を〇〇で割った余り」に関する話題は
よくあるもので、特性根が有理数とも限らないので、
No.4 No.3 の解法は、一応知っとくことを勧める。

Tacosan · Answer

画像は見たけど....

・行の先頭あたりにいっぱい出てくる矢印ってどういう意味なの?
・最後のところの「これより 5a(2010)=20 として」の「として」ってどういうこと?
・どうでもいい話ではあるけど計算ミスがあるような気はする.

Tacosan · Answer

たぶん誰もやらない (1) の解法.

まず n≧2 のとき a(n) が偶数であることは明らか. だから 5 で割った余りがわかれば十分.

でもってぐりぐり計算すると, b(n) = (n+1)*3^n に対して
a(n) と b(n) は 5 で割った余りが等しい
ことがわかる. だから本問は b(2010) を 5 で割った余りがわかればよく, それは 4 になるから a(2010) を 10 で割った余りは 4.

mtrajcp · Answer

整数a(1)≧0
整数a(2)≧0
a(n+2)=a(n+1)+6a(n)
a(n+2)-xa(n+1)=t{a(n+1)-xa(n)}
とすると
a(n+2)=(x+t)a(n+1)-txa(n)
x+t=1
tx=-6
t=1-x
(1-x)x=-6
x-x^2=-6
x^2-x-6=0
(x+2)(x-3)=0
x=-2.or.x=3

x=-2のとき
t=3
a(n+2)+2a(n+1)=3{a(n+1)+2a(n)}

b(n)=a(n+1)+2a(n)
とすると
b(1)=a(2)+2a(1)…①
b(n+1)=3b(n)
b(n)=3^(n-1)b(1)
a(n+1)+2a(n)=3^(n-1)b(1)…②

x=3のとき
t=-2
a(n+2)-3a(n+1)=-2{a(n+1)-3a(n)}

c(n)=a(n+1)-3a(n)
とすると
c(1)=a(2)-3a(1)…③
c(n+1)=-2c(n)
c(n)=(-2)^(n-1)c(1)
a(n+1)-3a(n)=(-2)^(n-1)c(1)
↓これを①から引くと
5a(n)=3^(n-1)b(1)-(-2)^(n-1)c(1)
↓両辺を5で割ると
a(n)={3^(n-1)b(1)-(-2)^(n-1)c(1)}/5
↓これと①③から
a(n)=(3^(n-1){a(2)+2a(1)}-(-2)^(n-1){a(2)-3a(1)})/5

(1)
a(1)=1
a(2)=2
b(1)=a(2)+2a(1)=4
c(1)=a(2)-3a(1)=-1
a(n)={4*3^(n-1)+(-2)^(n-1)}/5

a(2010)
={4*3^(2009)+(-2)^(2009)}/5
={4*3^(4*502+1)+(-2)^(4*502+1)}/5
={12(81^502)-2(16^502)}/5
={12{1+Σ_{k=1～502}(502Ck)80^k}-2{1+Σ_{k=1～502}(502Ck)15^k}}/5
={12+12Σ_{k=1～502}(502Ck)80^k-2-2Σ_{k=1～502}(502Ck)15^k}/5
=2+{12Σ_{k=1～502}(502Ck)80^k-2Σ_{k=1～502}(502Ck)15^k}/5
=2+{12*80Σ_{k=1～502}(502Ck)80^(k-1)-2*15Σ_{k=1～502}(502Ck)15^(k-1)}/5
=2+12*16Σ_{k=1～502}(502Ck)80^(k-1)-6Σ_{k=1～502}(502Ck)15^(k-1)
=
2
+12*16{502+Σ_{k=2～502}(502Ck)80^(k-1)}
-6{502+Σ_{k=2～502}(502Ck)15^(k-1)}
=
2
+12*16*502+12*16*80Σ_{k=2～502}(502Ck)80^(k-2)}
-6*502+90Σ_{k=2～502}(502Ck)15^(k-2)}
=
4(mod10)

(2)
a(2)=3a(1)
b(1)=a(2)+2a(1)=5a(1)
c(1)=a(2)-3a(1)=0
a(n)=a(1)3^(n-1)
a(n+4)=a(1)3^(n+3)

a(n+4)-a(n)
=a(1)3^(n+3)-a(1)3^(n-1)
=80a(1)3^(n-1)
は
10の倍数

ありものがたり · Answer

(1)
mod 2 で漸化してみると、
a[1] ≡ 1　(mod 2),
a[2] ≡ 0　(mod 2),
a[3] ≡ a[2] + 0 a[1] ≡ 0　(mod 2),
a[4] ≡ a[3] + 0 a[2] ≡ 0　(mod 2)
となって、n ≧ 2 では a[n] ≡ 0　(mod 2) です。

一方 mod 5 では、
a[1] ≡ 1　(mod 5),
a[2] ≡ 2　(mod 5),
a[3] ≡ a[2] + 1 a[1] ≡ 3　(mod 5),
a[4] ≡ a[3] + 1 a[2] ≡ 0　(mod 5),
a[5] ≡ a[4] + 1 a[3] ≡ 3　(mod 5),
a[6] ≡ a[5] + 1 a[4] ≡ 3　(mod 5),
a[7] ≡ a[6] + 1 a[5] ≡ 1　(mod 5),
a[8] ≡ a[7] + 1 a[6] ≡ 4　(mod 5),
a[9] ≡ a[8] + 1 a[7] ≡ 0　(mod 5),
a[10] ≡ a[9] + 1 a[8] ≡ 4　(mod 5),
a[11] ≡ a[10] + 1 a[9] ≡ 4　(mod 5),
a[12] ≡ a[11] + 1 a[10] ≡ 3　(mod 5),
a[13] ≡ a[12] + 1 a[11] ≡ 2　(mod 5),
a[14] ≡ a[13] + 1 a[12] ≡ 0　(mod 5),
a[15] ≡ a[14] + 1 a[13] ≡ 2　(mod 5),
a[16] ≡ a[15] + 1 a[14] ≡ 2　(mod 5),
a[17] ≡ a[16] + 1 a[15] ≡ 4　(mod 5),
a[18] ≡ a[17] + 1 a[16] ≡ 1　(mod 5),
a[19] ≡ a[18] + 1 a[17] ≡ 0　(mod 5),
a[20] ≡ a[19] + 1 a[18] ≡ 1　(mod 5),
a[21] ≡ a[20] + 1 a[19] ≡ 1 ≡ a[1]　(mod 5),
a[22] ≡ a[21] + 1 a[20] ≡ 2 ≡ a[2]　(mod 5)
となって、a[n+20] ≡ a[n]　(mod 5) が成り立ちます。
周期 25 以下を期待して実験して
実際は周期 20 だったのだから、歩留まりは悪いほうですけど。

mod 2 と mod 5 の結果を併せると、
a[n+20] ≡ a[n]　(mod 10).

a[2010] = a[20×100+10] = a[10] より
a[2010] ≡ a[10] ≡ 0　(mod 2),
a[2010] ≡ a[10] ≡ 4　(mod 5) なので
a[2010] ≡ 4　(mod 10) です。

ありものがたり · Answer

(2)
初期値を変えて同じようにやってみましょう。
a[1] = A と置いて、
a[2] = 3 a[1] ≡ 3A　(mod 10),
a[3] ≡ a[2] + 6 a[1] ≡ 3A + 6×A ≡ 9A　(mod 10),
a[4] ≡ a[3] + 6 a[2] ≡ 9A + 6×3A ≡ 7A　(mod 10),
a[5] ≡ a[4] + 6 a[3] ≡ 7A + 6×9A ≡ A ≡ a[1]　(mod 10),
a[6] ≡ a[5] + 6 a[4] ≡ A + 6×7A ≡ 3A ≡ a[2] (mod 10).
となって、a[n] は周期 4 を持ち、
a[n+4] ≡ a[n]　(mod 10) です。
すなわち、a[n+4] - a[n] を 10 で割った余りは 0 になります。

ありものがたり · Answer

a[n+2] を 10 で割った余り = 
= { (a[n+2] を 10 で割った余り)
　　+ 6 (a[n+2] を 10 で割った余り) } を 10 で割った余り
が成り立つ。
mod を知っているなら、
a[n+2] ≡ a[n+1] + 6 a[n]　(mod 10)
と書いたほうが見やすいかな？
ともかく、これで各項の計算は少し楽になります。

a[n] を 10 で割った余りと
a[n+1] を 10 で割った余りの組み合わせで
a[n+2] を 10 で割った余りが決まるのだから、
周期 10^2 以下の周期性があることはすぐ判りますが、
100 までやってみるのはちょっとしんどい。かもしれません。

案ずるより産むが易いもので、実際に順次漸化してみると
a[21] ≡ 1　(mod 10),
a[22] ≡ 2　(mod 10)
であることが見つかって、周期 20 があることが判ります。
ただ、22 で終われることは、やってみないと解らないので、
最悪 102 までやらねばならない漸化をやってみるのには度胸が要りますね。

そこの手数を軽減する工夫をしてみましょう。
10 = 2×5 と素因数分解して、10 で割った余りは
2 で割った余りと 5 で割った余りから再構成できます。
例えば、x ≡ 1　(mod 2), x ≡ 2　(mod 5) ならば x ≡ 7　(mod 10) です。

a[n+2] ≡ a[n+1] + 6 a[n]　(mod 10) を
a[n+2] ≡ a[n+1] + 6 a[n]　(mod 2) かつ
a[n+2] ≡ a[n+1] + 6 a[n]　(mod 5) と分解してみると、
mod 2 の漸化式は周期 2^2 以下
mod 5 の漸化式は周期 5^2 以下であることが予め判っています。

ssawatake · Answer

絵に書いた様な隣接3項漸化式の基本的タイプなんでしょ？
それでanを求めては駄目なんですか？

an=(4/5)･3ⁿ⁻¹+(1/5)･(-2)ⁿ⁻¹

整数問題 20 E###

←補足(06/04 12:24)

画像は見たけど....

たぶん誰もやらない (1) の解法.

整数a(1)≧0

(1)

(2)

a[n+2] を 10 で割った余り =

絵に書いた様な隣接3項漸化式の基本的タイプなんでしょ？

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング