Question

漢諾塔問題是根據一個傳說形成的一個問題：有三根桿子和套在一根桿子上的若干大小不等的穿孔圓盤，按下列規則，把圓盤從一根桿子上全部移到另一根桿子上．
①每次只能移動1個碟片；②大盤不能疊在小盤上面．
如圖所示，將A桿上所有碟片移到C桿上，B桿可以作為過渡桿使用，稱將碟片從一個桿子移動到另一個標子為移動一次，記將A桿子上的n個碟片移動到C桿上最少需要移動a_n次．
（Ⅰ）寫出a₁，a₂，a₃，a₄的值；
（Ⅱ）求數列{a_n}的通項公式；
（Ⅲ）設bn=

n

an+1

，求數列{b_n}的前n項和Sn．

Answer 1

分析：（Ⅰ）當n=1時，從A桿移到C桿上有一種方法A→C，即a₁=1；當n=2時，從A桿移到C桿上分3步，即A→B，A→C，B→C，有三種方法，即a₂=3，當n=3時，從A桿移到C桿上分七步，即A→C，A→B，C→B，A→C，B→A，B→C，A→C，有七種方法，即a₃=7；同理，得a₄=15；
（Ⅱ）由（Ⅰ）猜想數列{a_n}的通項公式為a_n=2ⁿ-1；現用數學歸納法證明，①驗證n=1時，a_n成立；②假設當n=k（k≥1）時，a_k=2^k-1成立，證明當n=k+1時，a_k+1=2^k+1-1也成立；即證得數列{a_n}的通項公式是a_n=2ⁿ-1．
（Ⅲ）由（Ⅱ）知，a_n=2ⁿ-1，bn=

n

an+1

=

n

2n

=n•(

1

2

)n，所以s_n=1•

1

2

+2•(

1

2

)2+3•(

1

2

)3+…+n•(

1

2

)n，易得

1

2

s_n=1•(

1

2

)2+2•(

1

2

)3+3•(

1

2

)4+…+n•(

1

2

)n+1；兩式相減，得

1

2

s_n，從而得s_n．

解答：解：（Ⅰ）由題意，知a₁=1，a₂=3，a₃=7，a₄=15．
（Ⅱ）由（Ⅰ）推測，數列{a_n}的通項公式為a_n=2ⁿ-1．
下面用數學歸納法證明如下：
①當n=1時，從A桿移到C桿上只有一種方法，即a₁=1，這時a_n=1=2¹-1成立；
②假設當n=k（k≥1）時，a_k=2^k-1成立．
則當n=k+1時，將A桿上的k+1個碟片看做由k個碟片和最底層1張碟片組成的，由假設可知，將A桿上的k個碟片移到B桿上有a_k=2^k-1種方法，再將最底層1張碟片移到C桿上有1種移法，最后將B桿上的k個碟片移到C桿上（此時底層有一張最大的碟片）又有a_k=2^k-1種移動方法，故從A桿上的k+1個碟片移到C桿上共有a_k+1=a_k+1+a_k=2a_k+1=2（2^k-1）+1=2^k+1-1種移動方法．
所以當n=k+1時，a_n=2ⁿ-1成立．
由①②可知數列{a_n}的通項公式是a_n=2ⁿ-1．
（Ⅲ）由（Ⅱ）可知，a_n=2ⁿ-1，所以，b_n=

n

2n-1+1

=

n

2n

=n•(

1

2

)n；
∴s_n=1•

1

2

+2•(

1

2

)2+3•(

1

2

)3+…+n•(

1

2

)n①；

1

2

s_n=1•(

1

2

)2+2•(

1

2

)3+3•(

1

2

)4+…+n•(

1

2

)n+1②；
①-②，得(1-

1

2

)s_n=

1

2

+(

1

2

)2+(

1

2

)3+…+(

1

2

)n-n•(

1

2

)n+1；
∴

1

2

Sn=

1 2 [1-( 1 2 )n]

1- 1 2

-n•(

1

2

)n+1，
∴Sn=2-(n+2)•(

1

2

)n．

點評：本題考查了數列知識和數學歸納法的綜合應用，用數學歸納法證明時，要按照（1）驗證，（2）假設，（3）證明的步驟解答，本題（Ⅲ）中數列求和方法，與教材中推導等比數列前n項和公式一樣，是錯位相減法．