Question

如图所示，有三根针和套在一根针上的若干金属片．按下规则，把金属片从一根针上全部移到另一根针上．

1．每次只能移动1个金属片；

2．较大的金属片不能放在较小的金属片上面．

试推测：把n个金属片从1号针移到3号针，最少需要移动多少次？

Answer 1

答案：
解析：

导思：我们从移动1，2，3，4个金属片的情形入手，探究其中的规律性，进而归纳出移动n个金属片所需的次数． 　　探究：当n＝1时，只需把金属片从1号针移到3号针，用符号(13)表示，共移动了1次． 　　当n＝2时，为了避免将较大的金属片放在较小的金属片上面，我们利用2号针作为“中间针”，移动的顺序是： 　　(1)把第1个金属片从1号针移到2号针； 　　(2)把第2个金属片从1号针移到3号针； 　　(3)把第1个金属片从2号针移到3号针． 　　用符号表示为 　　(12)(13)(23)， 　　共移动了3次． 　　当n＝3时，把上面两个金属片作为一个整体，则归结为n＝2的情形，移动的顺序是： 　　(1)把上面两个金属片从1号针移到2号针； 　　(2)把第3个金属片从1号针移到3号针； 　　(3)把上面3个金属片从1号针移到3号针． 　　其中(1)和(3)都需要借助中间针，用符号表示为 　　(13)(12)(32)(13)(21)(23)(13)， 　　共移动了7次． 　　当n＝4时，把上面3个金属片作为一个整体，移动的顺序是： 　　(1)把上面3个金属片从1号针移到2号针； 　　(2)把第4个金属片从1号针移到3号针； 　　(3)把上面3个金属片从2号针移到3号针． 　　用符号表示为 　　(12)(13)(23)(12)(31)(32)(12)(13)　(23)(21)(31)(23)(12)(13)(23)． 　　共移动了15次． 　　至此，我们得到依次移动1，2，3，4个金属片所需次数构成的数列 　　1，3，7，15． 　　观察这个数列，可以发现其中蕴含着如下规律： 　　1＝21－1，3＝22－1，7＝23－1，15＝24－1． 　　由此我们猜想：若把n个金属片从1号针移到3号 　　针，最少需要移动an次，则数列{an}的通项公式为 　　an＝2n－1(n∈N*)． 　　通过探究上述n＝1，2，3，4时的移动方法，我们可以 　　归纳出对n个金属片都适用的移动方法．当移动n个金属片时，可分为下列3个步骤： 　　(1)将上面(n－1)个金属片从1号针移到2号针； 　　(2)将第n个金属片从1号针移到3号针； 　　(3)将上面(n－1)个金属片从2号针移到3号针． 　　这样就把移动n个金属片的任务．转化为移动两次(n－1)个金属片和移动一次第n个金属片的任务．而移动(n－1)个金属片需要移动两次(n－2)个金属片和移动一次第(n－1)个金属片，移动(n－2)个金属片需要移动两次(n－3)个金属片和移动一次第(n－2)个金属片……如此继续，直到转化为移动1个金属片的情形．根据这个过程，可得递推公式 　　 　　从这个递推公式出发，可以证明上述通项公式是正确的．