Suppose there are n pieces and the number of moves is f(n). Obviously, f (1) = 1, f (2) = 3, f (3) = 7, f(k+ 1)=2*f(k)- 1.

f(n)=2^n- 1

For example:

When we find out how many times the N plates of the Tower of Hanoi must move, we get the following recursive formula:

a[ 1]= 1；

a[n]= a[n- 1]* 2+ 1；

Reference general formula

a[ 1]= 1；

a[n]= a[n- 1]* 2+ 1；

You can get a [I] = 2i-1;

Proved by mathematical induction:

Guess a [I] = 2 I- 1

When i= 1, it is obviously true.

If i=k holds, that is, a [k] = 2k-1; Then:

From a [n] = a [n-1] * 2-1; get

a[k+ 1] = a[k] * 2 - 1

= 2^k * 2 - 1

= 2^(k- 1) - 1

Therefore, it is proved that.

Extended data:

N-order Vantage moves: Let the number of gold pieces be n, then the number of moves =2 n-1 power.

Problem background: There are three pillars A, B and C. At first, N disks of different sizes were stacked on pillar A from small to large. Now, all disks should be moved from A to C, and the small disk should always be above the big disk during the movement. Find out the least number of times to move the plate.

(1) Move disk A and disk B to the two-disk puzzle in the second column;

(2) The single disk problem of moving disk C to 3 columns;

(3) The double disk problem of moving disk A and disk B to three columns.

As can be seen from the above, every simplified problem is easier than the original problem, so the problem will become an easy-to-solve original problem.

Baidu encyclopedia-Fanta problem