Question

如图所示，在1号管上套着大小不同（从大到小）的n个铁环，按下列规则：①每次移动一个铁环；②较大的铁环不能放在较小铁环的上面．将铁环全部套到3号管上，最少需要移动的次数设为a_n，猜想a_n 的表达式，并加以证明．

Answer

当n=1时，从1号管移到3号管上有一种方法1→3，即a1=1；当n=2时，从1号管移到3号管上分3步，即1→2，1→3，2→3，有三种方法，即a2=3，当n=3时，从1号管移到3号管上分七步，即1→3，1→2，3→2，1→3，2→1，2→3，1→3，有七种方法，即a3=7；同理，得a4=15；猜想数列{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．
【解析】
由题意，知a1=1，a2=3，a3=7，a4=15．
推测，数列{an}的通项公式为an=2n-1．
下面用数学归纳法证明如下：
①当n=1时，从1号管移到3号管上只有一种方法，即a1=1，这时an=1=21-1成立；
②假设当n=k（k≥1）时，ak=2k-1成立．
则当n=k+1时，将1号管上的k+1个铁环看做由k个铁环和最底层1个铁环组成的，由假设可知，将1号管上的k个铁环移到2号管上有ak=2k-1种方法，再将最底层1个铁环移到3号管上有1种移法，最后将2号管上的k个铁环移到3号管上（此时底层有一张最大的铁环）又有ak=2k-1种移动方法，故从1号管上的k+1个铁环移到3号管上共有ak+1=ak+1+ak=2ak+1=2（2k-1）+1=2k+1-1种移动方法．
所以当n=k+1时，an=2n-1成立．
由①②可知数列{an}的通项公式是an=2n-1．