2
$\begingroup$

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

$\endgroup$

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.