I am having an incredible amount of trouble understanding Strong Induction. I realize that Strong Induction means that we are assuming $P(1) \land P(2) \land P(3)\land...\land P(n-1) = P(n)$. But after this point, I'm lost. How does this chain of previous "truths" prove that $P(n) \implies P(n+1)$?

For example, a HW problem I have deals with splitting stacks of boxes. The problem goes like this

Lets say you have a stack of n boxes. You are allowed to split the
stack of boxes into stacks of size l and m, and in doing so, you earn
l * m in profit. You must repeatedly split the stacks until you have n stacks of
1 box.

Come up with a conjecture about the max profit you can earn and prove it by
strong induction.

Basically, the question is asking about breaking a stack of n boxes down repeatedly until you get to n 1 box high stacks, and then compute the sum of profit earned by each successive splitting of the stack. It was fairly easy to come up with a formula that computes the profit earned, which is $n(n-1)/2$. To prove this by strong induction, I first start with a base case.

Base Case: $P(1)$ is true because $1(1-1)/2) = 0$ and since you don't split any stacks, you don't earn any money.

Inductive Step: Assume $P(1)$ up to $P(n)$ is true and consider $P(n+1)$. That is, $P(1) \land P(2)\land P(3)\land...\land P(n-1) = P(n)$

It is from this point that I'm lost. It can't be as simple as stating every case leading up to $P(n)$ is true, since we didn't prove this chain leading up to $P(n)$, only claiming it in the inductive step. I also don't understand how this chain inherently proves $P(n+1)$. If someone can please help understand where to go with this homework problem, (and ultimately an understanding of Strong Induction), I would greatly appreciate it. Proof by induction isn't too bad, but I get completely lost at Strong induction. Thanks


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.