These are notes taken from the Lec 3 | MIT 6.042J Mathematics for Computer Science, Fall 2010 video lecture, which can be found at https://www.youtube.com/watch?v=NuGDkmwEObM#t=4658
What exactly does the Strong in Strong Induction mean? Let $P(n)$ be any predicate. if $P(0)$ is true then $\forall n (P(0) \wedge P(1) \wedge \ldots \wedge P(n)) \Rightarrow P(n+1)$ is true, then $\forall n : P(n)$ is true. Remember the normal induction axiom? Let $P(n)$ be a predicate. If $P(0)$ is True and $\forall n \in \mathbb{N} : (P(n) \Rightarrow P(n+1))$ is True, then $\forall n \in \mathbb{N}$ $P(n)$ is True. The difference is that you’re assuming that all the cases starting from the base case til $n$ are true, in order to prove that $P(n+1)$ is true. The Unstacking game is demonstrated: here’s a brief recap (no, actually, this is just another LaTex exercise for me)
The score one would get is (4*4)+(2*2)+(3*1)+(1*1)+(1*1)+(2*1)+(1*1) = 28. There must be a strategy to beat this, is there?
(7*1)+(6*1)+(5*1)+(4*1)+(3*1)+(2*1)+(1*1) = 28. Now one should immediately jump to the conclusion (if one is an MIT student) that all combinations lead to a score of 28. But one is not if one is reading this, so: Theorem: All strategies $S(n)$ for the Unstacking Game with $n$ starting blocks lead to the same score. Proof by strong induction: Inductive Hypothesis: $P(n)$ is the Theorem. Base Case: $S(1)$ is zero (One can’t play the game with 0 blocks). Inductive step: Assume $P(1), P(2), \ldots, P(n)$ in order to prove $P(n+1)$. With $(n+1)$ blocks, for $1 \leq k \leq n$:
Our score for $P(n+1)$ is $k(n+1-k)+P(k)+P(n+1-k)$ (think recursion, after each division of blocks each block is an instance of the Game). One has hit a dead end here, as one is trying to prove that $P(n+1)$ is dependent on $n$, not $k$. Honestly this example (IMHO) is rather haphazard, as the next step, which not so intuitively, is to make a good guess as to what $S(n)$ might be, and in classic MIT intuition style, our first guess yields $\frac{n(n-1)}{2}$. Testing a few values of $n$.. $S(2) = 1$, $S(3) = 3$, $S(4) = 6$, $S(8) = 28$. Let’s put $P(n)$ through its runs again…. Base case, where $P(n) = \frac{n(n-1)}{2}$: $P(1) = 0$. Going back to the previous expression which we derived for the score, now that we have an expression for $P(n)$: $k(n+1-k) + \frac{k(k-1)}{2} + \frac{(n+1-k)(n-k)}{2}$ Simplifying this expression (aka plugging it into WolframAlpha…) results in $\frac {n(n+1)}{2}$, which is $S(n+1)$. In the words of the professor, “The $k$ disappears.“ We have worked backwards (to my understanding), deriving an expression for the score, reaching a dead end, where we have to stop assuming ($k$), come up with an expression for $P(n)$, and filling in the blank to prove $P$(or $S$)$(n+1)$.