まずは簡単に求めることができる場合を考えてみます。
最適なxがただ一つに決まる場合について考えます。つまり、n=x(x+1)/2のときです。
このときにb(n)=b'(x)とします。このとき、以下の漸化式が得られます。
a(x)=2^n-1ですから、これは簡単に解けそうです。
b'(x)=2b'(x-1)+2^x-1
b'(x)-x*2^x-1=2{b'(x-1)-(x-1)*2^(x-1)-1}
と変換できますから、b'(n)-x*2^x-1は初項1-1*2^1-1=-2公比2の等比数列になります。したがって、
b'(x)-x*2^x-1=-2*2^(x-1)=-2^x
b'(x)=x*2^x-2^x+1
b'(x)=(x-1)*2^x+1
となって手数が求まります。
検算してみます。
あっていますね。これで、まず第1段階の数式化ができました。ではこれを一般化していきたいと思います。はたして、うまくできるのでしょうか?
続きは次回に
最適なxがただ一つに決まる場合について考えます。つまり、n=x(x+1)/2のときです。
このときにb(n)=b'(x)とします。このとき、以下の漸化式が得られます。
- b'(1)=1
- b'(x)=2b'(x-1)+a(x)
a(x)=2^n-1ですから、これは簡単に解けそうです。
b'(x)=2b'(x-1)+2^x-1
b'(x)-x*2^x-1=2{b'(x-1)-(x-1)*2^(x-1)-1}
と変換できますから、b'(n)-x*2^x-1は初項1-1*2^1-1=-2公比2の等比数列になります。したがって、
b'(x)-x*2^x-1=-2*2^(x-1)=-2^x
b'(x)=x*2^x-2^x+1
b'(x)=(x-1)*2^x+1
となって手数が求まります。
検算してみます。
- x=2→n=3→b(3)=b'(2)=(2-1)*2^2+1=1*4+1=5
- x=3→n=6→b(6)=b'(3)=(3-1)*2^3+1=2*8+1=17
- x=4→n=10→b(10)=b'(4)=(4-1)*2^4+1=3*16+1=49
- x=5→n=15→b(15)=b'(5)=(5-1)*2^5+1=4*32+1=129
- x=6→n=21→b(21)=b'(6)=(6-1)*2^6+1=5*64+1=321
- x=7→n=28→b(28)=b'(7)=(7-1)*2^7+1=6*128+1=769
- x=8→n=36→b(36)=b'(8)=(8-1)*2^8+1=7*256+1=1793
- x=9→n=45→b(45)=b'(9)=(9-1)*2^9+1=8*512+1=4097
あっていますね。これで、まず第1段階の数式化ができました。ではこれを一般化していきたいと思います。はたして、うまくできるのでしょうか?
続きは次回に