Question

汉诺塔问题是指有三根杆子和套在一根杆子上的若干大小不等的碟片，按下列规则，把碟片从一根杆子上全部移到另一根杆子上：（1）每次只能移动1个碟片；（2）较大的碟片不能放在较小的碟片上面．
如图所示，将B杆上所有碟片移到A杆上，C杆可以作为过渡杆使用，称将碟片从一根杆子移动到另一根杆子为移动一次，记将B杆子上的n个碟片移动到A杆上最少需要移动a_n次．
（1）写出a₁，a₂，a₃，a₄的值；
（2）求数列{a_n}的通项公式；
（3）设bn=

1

an+1

+

1

anan+1

，数列{bn}的前n项和为Sn，证明

2

3

≤Sn＜1．

Answer 1

分析：（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；
（2）由（1）猜想数列{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．
（3）由（2）可知，a_n=2ⁿ-1，，从而bn=

1

an+1

+

1

anan+1

=

an+1

anan+1

，进而可构建函数，从而可证．

解答：解：（1）a₁=1，a₂=3，a₃=7，a₄=15．…（4分）
（2）由（1）推测数列{a_n}的通项公式为a_n=2ⁿ-1．…（6分）
下面用数学归纳法证明如下：
①当n=1时，从B杆移到A杆上只有一种方法，即a₁=1，
这时a_n=1=2¹-1成立；…（7分）
②假设当n=k（k≥1）时，a_k=2^k-1成立．
则当n=k+1时，将B杆上的k+1个碟片看做由k个碟片和最底层1张碟片组成的，由假设可知，将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
种移动方法．
所以当n=k+1时a_n=2ⁿ-1成立．
由①②可知数列{a_n}的通项公式是a_n=2ⁿ-1．…（9分）
（说明：也可由递推式a₁=1，a_n=2a_n-1+1（n∈N^*，N＞1），构造等比数列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分）
因为函数f(x)=1-

1

21+x-1

在区间[1，+∞）上是增函数，∴(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分）

点评：本题以实际问题为载体，考查了数列知识和数学归纳法的综合应用，用数学归纳法证明时，要按照（1）验证，（2）假设，（3）证明的步骤解答