数学の、数列の問題です。

質問

数列｛a（n）}を、a（1）＝a（2）=1、a(n+2)=２^(n-1)/a(n＋１） +a（n） (n = 1,2,3,・・・）　により定める。

（左辺＝数列のn+2項目、右辺＝数列のn+1項目 分の ２の（n-1)乗（分数終わり） + 数列のn項目）

(1)　自然数mに対して、a(2m-1)、a(2m) （数列の2m-1項目、数列の2m項目）を求めなさい。

(2)　自然数nに対して、a（n）を３で割った余りを　ｒ（n）とする。

　　　　　Σ[n = 1、N] r(n) >１０００　　を満たす最少の自然数Nを求めなさい。

　　（左辺＝Σの下にn = 1、上にN、右に r（n） ）　　解説もよろしくお願いします。

回答No.2

dragonkazooie

Autumnroomさん，こんばんは．

まずは，手計算で最初の何項かを計算してみることが大切です．

問題(1)

a[1]=1
a[2]=1
a[3]=2^0/1+1=1+1=2
a[4]=2^1/2+1=2
a[5]=2^2/2+2=4
a[6]=2^3/4+2=4
a[7]=2^4/4+4=8
a[8]=2^5/8+4=8
…
となりますから，
　a[2m-1]=a[2m]=2^(m-1)　…(1)
であることを推測するのは容易でしょう．一般項が推測できたならば，それが漸化式を満たすことが示されればその推測は当たっている，ということになります．nが偶数，すなわち整数mを用いてn=2mと書けるとき
　a[2m+2]=2^(2m-1)/a[2m+1]+a[2m]　…(2)
となります．(1)式によれば，
　a[2m+2]=a[2(m+1)]=2^{(m+1-1}=2^m　…(3)
　a[2m+1]=a[2(m+1)-1]=2^(m+1-1)=2^m　…(4)
　a[2m]=2^(m-1)
なので，これらを(2)式に代入してみましょう．
　(左辺)=2^m
　(右辺)=2^(2m-1)/2^m+2^(m-1)=2^(m-1)+2^(m-1)=2^m
となり確かに成り立っています．

次にnが奇数，すなわちn=2m-1と書ける場合について考えます．与えられた漸化式は
　a[2m+1]=2^(2m-2)/a[2m]+a[2m-1]　…(5)
となり，(1),(4)式を代入すると
　(左辺)=2^m
　(右辺)=2^(2m-2)/2^(m-1)+2^(m-1)=2^(m-1)+2^(m-1)=2^m
となり，やはり漸化式を満たします．

またこの推測した式は当然，初期条件a[1]=a[2]=1を満たしているので，結局，この推測した一般項
　a[2m-1]=a[2m]=2^(m-1)　…(6)
は正解であると分かりました．

問題(2)
a[n]={1,1,2,2,4,4,8,8,16,16,32,32,…}と続くものであることが分かりました．3で割った余りを計算してr[n]を求めると
　r[n]={1,1,2,2,1,1,2,2,1,1,2,2,…}
となります．このことから，r[4m-1]=r[4m]=2,r[4m-3]=r[4m-2]=1であると，これも容易に推測できます．

これを確かめてみましょう．(6)式より
　a[4m-1]=a[4m]=2^(2m-1)　…(7)
　a[4m-3]=a[4m-2]=2^(2m-2)　…(8)
です．一般に3で割って1余る数N=3s+1を2倍すると，2N=6s+2=3(2s)+2となり，2余る数になります．これをさらに2倍すると4N=12s+4=3(4s+1)+1となるので，1余る数になります．このことから3で割った余りは4倍しても変わらないことが分かります．(6),(7)式より
　a[4m+4]=a[4(m+1)]=2^(2m+1)=4a[4m]
　a[4m+3]=a[4(m+1)-1]=2^(2m+1)=4a[4m-1]
　a[4m+2]=a[4(m+1)-2]=2^(2m)=4a[4m-2]
　a[4m+1]=a[4(m+1)-3]=2^(2m)=4a[4m-3]
となり，a[n]は4項進むと4倍になっていることが分かります．よって，4項進んでも3で割った余りは変わらず，r[n]={1,1,2,2,1,1,2,2,…}と続くことが判明しました．r[n]は4項で一周期をなしており，一周期の和は1+1+2+2=6です．1000/6=166.66…ですので，167周期(668項目)で1000を超えていることが分かります．具体的な和は1002です．668項目は2なので，667項目までの和は1000となり，1000を超えてはいません．よって，求める最小のNは668となります．

分からない点があれば補足に書いてくださいね．

回答No.1

noname#232123

少々強引ですが、一般項を決定してみました。
{a[n]}の階差数列, {b[n]} は、b[n]=[{1+(-1)^n}/2]*2^(n/2 - 1) であるものとすると、少し面倒な計算の結果、
a[n]={(√2+1)*(√2)^n - (√2 - 1)*(-√2)^n}/4, (n≧1) .... (*)
を得ます。
これが与えられた漸化式を満たすことは、
a[n+1]*{a[n+2] - a[n]}=2^(n-1)
を示せばよいのですが、これはさほど面倒ではありません（記載しません）。
したがって、(*) は正しいことになります。
これを使って、
a[2m]=a[2m-1]=2^(m-1) となります。

(2)

mod(3) において、2^(奇数)≡2, 2^(偶数)≡1 です。
これから、階差数列を利用して、r[n] を求めると、
r[n]=1+Σ[k=1 to n-1](-1)^(k-1)={3+(-1)^n}/2. (これはn=1 のときも正しい)
次に、
S[n]=Σ[k=1 to n]r[k]={6n - 1+(-1)^n}/4.
ですから題意より、
{6n - 1+(-1)^n}/4>1000 ⇔ 6n - 1+(-1)^n>4000
ここで、S[n]は単調増加であり、
S[665]=3988, S[666]=3996, S[667]=4000, S[668]=4008, ...
ですから、求めるNは668となります。
------------------------------
※出題者が予想する解決方法とは言えませんが、a[n]が比較的簡単にもとまるのでこの方法で解いてみました。
なお、計算ミス、タイプミスがあるかもしれません。