四阶汉诺塔（Tower Of Hanoi (4 Pegs)）不等式证明及公式含义问询

First off, let's recall what $S_n$ means: it's the minimum number of moves needed to transfer $n$ disks from one peg to another using 4 pegs (this is the classic Frame-Stewart problem). Let's break down each proof step by step, and tie it back to the recursive formula you mentioned.

To prove this inequality, we just need to construct a valid, concrete strategy for moving $m$ disks that uses exactly $2·S_{m−k} + 2^{k} − 1$ moves. Since $S_m$ is the minimum number of moves required, it can't be larger than the number of moves used by any valid strategy.

Here's the strategy, step by step:

• Step 1: Move the top $m-k$ disks from the starting peg to one of the two auxiliary pegs, using all 4 pegs. By definition of $S_n$, this takes $S_{m−k}$ moves.
• Step 2: Now we have $k$ larger disks left on the starting peg. These can only be moved using 3 pegs (starting, target, and the remaining auxiliary peg—since the other auxiliary peg is holding the $m-k$ smaller disks). Moving $k$ disks with 3 pegs is the standard Tower of Hanoi problem, which we know requires $2^k - 1$ moves (a well-established result: $T_k = 2^k - 1$ for 3-peg Hanoi).
• Step 3: Finally, move the $m-k$ disks from the auxiliary peg to the target peg, again using all 4 pegs. This takes another $S_{m−k}$ moves.

Adding up the moves from all three steps:
$$S_{m−k} + (2^k - 1) + S_{m−k} = 2·S_{m−k} + 2^k - 1$$

Since this is a valid way to move $m$ disks, the minimum number of moves $S_m$ can't exceed this value. That's exactly what the inequality states.

We'll use mathematical induction here, since we're proving a statement for all non-negative integers $n$.

Base Cases #

Let's verify the smallest values of $n$ first to confirm the foundation:

• When $n=0$: $\frac{0(0+1)}{2} = 0$. $S_0 = 0$ (no disks to move), and the right-hand side is $2^0·(0-1) + 1 = 1·(-1) + 1 = 0$. So $0 \leq 0$ holds.
• When $n=1$: $\frac{1(1+1)}{2} = 1$. $S_1 = 1$ (just move the single disk), and the right-hand side is $2^1·(1-1) + 1 = 2·0 +1 =1$. $1 \leq1$ holds.
• When $n=2$: $\frac{2(2+1)}{2}=3$. For 3 disks on 4 pegs, the minimum moves $S_3=5$, and the right-hand side is $2^2·(2-1)+1=4·1+1=5$. $5 \leq5$ holds.

Inductive Step #

Assume the statement is true for $n=t$ (this is our inductive hypothesis):
$$S\left(\frac{t(t+1)}{2}\right) \leq 2^t·(t-1) +1$$

We need to prove it holds for $n=t+1$, i.e.:
$$S\left(\frac{(t+1)(t+2)}{2}\right) \leq 2^{t+1}·t +1$$

First, notice that:
$$\frac{(t+1)(t+2)}{2} = \frac{t(t+1)}{2} + (t+1)$$

Let $m = \frac{(t+1)(t+2)}{2}$ and $k = t+1$. Applying the inequality from Proof 1:
$$S_m \leq 2·S_{m−k} + 2^k -1$$

Substitute $m-k = \frac{t(t+1)}{2}$ and $k=t+1$:
$$S\left(\frac{(t+1)(t+2)}{2}\right) \leq 2·S\left(\frac{t(t+1)}{2}\right) + 2^{t+1} -1$$

Now use our inductive hypothesis to replace $S\left(\frac{t(t+1)}{2}\right)$:
$$\leq 2·\left(2^t·(t-1)+1\right) + 2^{t+1} -1$$

Simplify the right-hand side:
$$= 2^{t+1}(t-1) + 2 + 2^{t+1} -1$$
$$= 2^{t+1}(t-1 +1) + (2-1)$$
$$= 2^{t+1}·t +1$$

Which is exactly what we needed to prove. By induction, the statement holds for all $n \geq0$.

Quick Note on the $2S(k,r)+S(n-k,r-1)$ Formula #

You mentioned the general formula $2S(k,r)+S(n-k,r-1)$—this is the core of the Frame-Stewart algorithm for $r$-peg Tower of Hanoi. Here's how it connects to our proofs:

• $r=4$ (our problem with 4 pegs)
• When we split $n$ disks into $n-k$ and $k$:
  • $S(n-k, r)$ is moving the top $n-k$ disks with all $r$ pegs (so $S_{n-k}$ in our notation)
  • $S(k, r-1)$ is moving the bottom $k$ disks with $r-1=3$ pegs, which is the standard 3-peg Hanoi number $2^k -1$
• Substituting these values gives $2S_{n-k} + (2^k -1)$, which is exactly the right-hand side of our first inequality. This formula is the strategy we used to construct the move count for Proof 1.

内容的提问来源于stack exchange，提问作者Isabella.T