FC2ブログ

Welcome to my blog

[答1070] 漸化式で表された数列の和

ヤドカリ

ヤドカリ


'


[答1070] 漸化式で表された数列の和


 a1=0 ,nが自然数のとき a2n=an+1,a2n+1=an で 表される数列{ an }について、

 a1+a2+a3+a4+……+a1069+a1070=?


[解答1]

 Sn=a1+a2+a3+a4+……+an-1+an とします。

 a2n+a2n+1=an+1+an=2an+1 だから、

 S2n+1=a1+a2+a3+a4+a5+……+a2n+a2n+1=0+2a1+1+2a2+1+……+2an+1=2Sn+n 、

 S2n=S2n+1-a2n+1=2Sn+n-an

 S2n=2Sn+n-an ,S2n+1=2Sn+n です。

 S1070=2S535+535-a535=2(2S267+267)+535-a267=4S267+1069-a267=4(2S133+133)+1069-a133

  =8S133+1601-a133=8(2S66+66)+1601-a66=16S66+2129-a66=16(2S33+33-a33)+2129-(a33+1)

  =32S33+2656-17a33=32(2S16+16)+2656-17a16=64S16+3168-17a16

  =64(2S8+8-a8)+3168-17(a8+1)=128S8+3663-81a8=128(2S4+4-a4)+3663-81(a4+1)

  =256S4+4094-209a4=256(2S2+2-a2)+4094-209(a2+1)=512S2+4397-465a2

  =512(2S1+1-a1)+4397-465(a1+1)=1024S1+4444-977a1=1024・0+4444-977・0=4444 です。


[解答2]

 an は nを2進法で表したときの 0 の個数です。

 nが2進法でk桁の数であるとき、すなわち、2k-1≦n≦2k-1 のとき、

 該当する自然数は 2k-1 個あり、2進法で首位を除いて 0,1 が同数個あるので、

 平均して (k-1)/2 個の 0 があることになり、総数は 2k-2(k-1) です。

 1023=1111111111(2) なので、 S=a1+a2+a3+……+a1023 とすれば、

 S=2-1・0+20・1+21・2+22・3+23・4+24・5+25・6+26・7+27・8+28・9 、

 2S=20・0+21・1+22・2+23・3+24・4+25・5+26・6+27・7+28・8+29・9 、

 4S=21・0+22・1+23・2+24・3+25・4+26・5+27・6+28・7+29・8+29・18 、

 S+4S-2・2S=1+21(2+0-2・1)+22(3+1-2・2)+……+28(9+7-2・8)+29(8+18-2・9) 、

 S=1+0+……+0+29・8=1+4096=4097 です。

 1024=10000000000(2) から 1055=10000011111(2) までの 32個について、

  2進法で下5桁は 0,1 が同数個あるので、0 は 32・(10+5)/2=240 個、

 1056=10000100000(2) から 1071=10000101111(2) までの 16個について、

  2進法で下4桁は 0,1 が同数個あるので、0 は 16・(9+5)/2=112 個です。

 a1+a2+a3+a4+……+a1069+a1070=4097+240+112-5=4444 です。

.

スポンサーサイト



Comments 12

There are no comments yet.
ひとりしずか  
No title

セツブンソウ、春の妖精ですネ
前に住んでいた家の近所の庭にキバナセツブンソウが沢山咲いていました。
どちらも関東以西が分布となっていますが……
庭に咲かせてみたい花のひとつです。

ニリンソウ  
No title

セツブンソウは新潟の山では見ない花!
花屋さんで売ってますが育つのかな、奥秩父の山で
見たときは感動でした。
素敵な花があるものだと!

ナイス

アキチャン  
No title

こんにちわ。
なんと美しい♪(o^-^o)

黒翼  
No title

解法2は目からウロコですね。
自分の頭の硬さを痛感します。

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとナイス!をありがとうございます。
春の妖精のように感じる花が咲くようになってきました。
セツブンソウは滅多に見ない花ですが、綺麗に咲いていました。

ヤドカリ  
No title

ニリンソウさん、早速のコメントをありがとうございます。
セツブンソウは其方にはあまり縁のない花のようですね。
その分、雪割草など綺麗な花が多いですよね。

ヤドカリ  
No title

アキチャンさん、早速のコメントとナイス!をありがとうございます。
私もセツブンソウは美しいと思います。
あまり見る機会がありませんが、この時期に見たい花ですね。

ヤドカリ  
No title

黒翼さん、早速のコメントをありがとうございます。
[解答2]を思いついて作った問題です。
他の方もこのような解き方をされていました。

スモークマン  
No title

グーテンアーベント ^^
よくわからず ^^;
2進法でも考えてみたんだけどなぁ…?
解読できませんでしたわ ^^;;...無念…Orz...

ヤドカリ  
No title

スモークマンさん、コメントをありがとうございます。
2進法が分かり易いと思います。
そのようなイメージができるかどうかですね。

樹☆  
No title

この時期にしか見ることができないという
セツブンソウ・・
わたし、本物この目でまだ見たことがありません。
ほんとに妖精のようなお花です。

ヤドカリ  
No title

樹ちゃん、コメントをありがとうございます。
セツブンソウは滅多に見られませんが、
小さいながらその姿を毎年見たいです。