Question

漢諾塔問題是指有三根桿子和套在一根桿子上的若干大小不等的碟片，按下列規(guī)則，把碟片從一根桿子上全部移到另一根桿子上：（1）每次只能移動1個碟片；（2）較大的碟片不能放在較小的碟片上面．
如圖所示，將B桿上所有碟片移到A桿上，C桿可以作為過渡桿使用，稱將碟片從一根桿子移動到另一根桿子為移動一次，記將B桿子上的n個碟片移動到A桿上最少需要移動a_n次．
（1）寫出a₁，a₂，a₃，a₄的值；
（2）求數(shù)列{a_n}的通項公式；
（3）設(shè)bn=

1

an+1

+

1

anan+1

，數(shù)列{bn}的前n項和為Sn，證明

2

3

≤Sn＜1．

Answer 1

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

1

an+1

+

1

anan+1

=

an+1

anan+1

，進而可構(gòu)建函數(shù)，從而可證．

解答：解：（1）a₁=1，a₂=3，a₃=7，a₄=15．…（4分）
（2）由（1）推測數(shù)列{a_n}的通項公式為a_n=2ⁿ-1．…（6分）
下面用數(shù)學(xué)歸納法證明如下：
①當(dāng)n=1時，從B桿移到A桿上只有一種方法，即a₁=1，
這時a_n=1=2¹-1成立；…（7分）
②假設(shè)當(dāng)n=k（k≥1）時，a_k=2^k-1成立．
則當(dāng)n=k+1時，將B桿上的k+1個碟片看做由k個碟片和最底層1張碟片組成的，由假設(shè)可知，將B桿上的k個碟片移到C桿上有a_k=2^k-1種方法，再將最底層1張碟片移到A桿上有1種移法，最后將C桿上的k個碟片移到A桿上（此時底層有一張最大的碟片）又有a_k=2^k-1種移動方法，故從B桿上的k+1個碟片移到A桿上共有a_k+1=a_k+1+a_k=2a_k+1=2（2^k-1）+1=2^k+1-1
種移動方法．
所以當(dāng)n=k+1時a_n=2ⁿ-1成立．
由①②可知數(shù)列{a_n}的通項公式是a_n=2ⁿ-1．…（9分）
（說明：也可由遞推式a₁=1，a_n=2a_n-1+1（n∈N^*，N＞1），構(gòu)造等比數(shù)列a_n+1=2（a_n-1+1）求解）
（3）由（2）可知，a_n=2ⁿ-1，
所以bn=

1

an+1

+

1

anan+1

=

an+1

anan+1

=

2n

(2n-1)(2n+1-1)

=

(2n+1-1)-(2n-1)

(2n-1)(2n+1-1)

=

1

2n-1

-

1

2n+1-1

．…（10分）S_n=b₁+b₂+…+b_n
=(

1

21-1

-

1

22-1

)+(

1

22-1

-

1

23-1

)+…+(

1

2n-1

-

1

2n+1-1

)
=1-

1

2n+1-1

．…（11分）
因為函數(shù)f(x)=1-

1

21+x-1

在區(qū)間[1，+∞）上是增函數(shù)，∴(Sn)min=1-

1

21+1-1

=

2

3

．…（12分）
又

lim

n→+∞

Sn=

lim

n→+∞

(1-

1

21+n-1

)=1，∴S_n＜1．
所以

2

3

≤Sn＜1．…（13分）

點評：本題以實際問題為載體，考查了數(shù)列知識和數(shù)學(xué)歸納法的綜合應(yīng)用，用數(shù)學(xué)歸納法證明時，要按照（1）驗證，（2）假設(shè)，（3）證明的步驟解答