汉诺塔问题是指有三根杆子和套在一根杆子上的若干大小不等的碟片，按下列规则，把碟片...

（1）当n=1时，从A杆移到C杆上有一种方法A→C，即a1=1；当n=2时，从A杆移到C杆上分3步，即A→B，A→C，B→C，有三种方法，即a2=3，当n=3时，从A杆移到C杆上分七步，即A→C，A→B，C→B，A→C，B→A，B→C，A→C，有七种方法，即a3=7；同理，得a4=15； （2）由（1）猜想数列{an}的通项公式为an=2n-1；现用数学归纳法证明，①验证n=1时，an成立；②假设当n=k（k≥1）时，ak=2k-1成立，证明当n=k+1时，ak+1=2k+1-1也成立；即证得数列{an}的通项公式是an=2n-1． （3）由（2）可知，an=2n-1，，从而，进而可构建函数，从而可证． 【解析】 （1）a1=1，a2=3，a3=7，a4=15．…（4分） （2）由（1）推测数列{an}的通项公式为an=2n-1．…（6分） 下面用数学归纳法证明如下： ①当n=1时，从B杆移到A杆上只有一种方法，即a1=1， 这时an=1=21-1成立；…（7分） ②假设当n=k（k≥1）时，ak=2k-1成立． 则当n=k+1时，将B杆上的k+1个碟片看做由k个碟片和最底层1张碟片组成的，由假设可知，将B杆上的k个碟片移到C杆上有ak=2k-1种方法，再将最底层1张碟片移到A杆上有1种移法，最后将C杆上的k个碟片移到A杆上（此时底层有一张最大的碟片）又有ak=2k-1种移动方法，故从B杆上的k+1个碟片移到A杆上共有ak+1=ak+1+ak=2ak+1=2（2k-1）+1=2k+1-1 种移动方法． 所以当n=k+1时an=2n-1成立． 由①②可知数列{an}的通项公式是an=2n-1．…（9分） （说明：也可由递推式a1=1，an=2an-1+1（n∈N*，N＞1），构造等比数列an+1=2（an-1+1）求解） （3）由（2）可知，an=2n-1， 所以 =．…（10分）Sn=b1+b2+…+bn =++…+ =．…（11分） 因为函数在区间[1，+∞）上是增函数，∴．…（12分） 又，∴Sn＜1． 所以．…（13分）