I know that for proving some $P(m,n)$ we can apply induction as follows: prove some base case $P(m_0, n_0)$, an inductive step given $P(m-1,n)$ to show $P(m,n)$, and an inductive step given $P(m,n-1)$ to show $P(m,n)$. However in a proof I am working on I need a stronger hypothesis. In particular, in order to show $P(m,n)$ given $P(m-1,n)$ I also need to assume that $P(m-1,n-k)$ holds for $1\leq k\leq n$ too, a strong induction of sorts. Is this logically sound, and if not what is the issue with it? If it is sound, how much stronger can we get?
Strong Induction on Two Variables
inductionlogic
Related Solutions
You wrote:
i understand how to do ordinary induction proofs and i understand that strong induction proofs are the same as ordinary with the exception that you have to show that the theorem holds for all numbers up to and including some n (starting at the base case) then we try and show: theorem holds for $n+1$
No, not at all: in strong induction you assume as your induction hypothesis that the theorem holds for all numbers from the base case up through some $n$ and try to show that it holds for $n+1$; you don’t try to prove the induction hypothesis.
In your example the simple induction hypothesis that the result is true for $n$ is already enough to let you prove that it’s true for $n+1$, so there’s neither need nor reason to use a stronger induction hypothesis. The proof by ordinary induction can be seen as a proof by strong induction in which you simply didn’t use most of the induction hypothesis.
I suggest that you read this question and my answer to it and see whether that clears up some of your confusion; at worst it may help you to pinpoint exactly where you’re having trouble.
Added: Here’s an example of an argument that really does want strong induction. Consider the following solitaire ‘game’. You start with a stack of $n$ pennies. At each move you pick a stack that has at least two pennies in it and split it into two non-empty stacks; your score for that move is the product of the numbers of pennies in the two stacks. Thus, if you split a stack of $10$ pennies into a stack of $3$ and a stack of $7$, you get $3\cdot7=21$ points. The game is over when you have $n$ stacks of one penny each.
Claim: No matter how you play, your total score at the end of the game will be $\frac12n(n-1)$.
If $n=1$, you can’t make any move at all, so your final score is $0=\frac12\cdot1\cdot0$, so the theorem is certainly true for $n=1$. Now suppose that $n>1$ and the theorem is true for all positive integers $m<n$. (This is the strong induction hypothesis.) You make your first move; say that you divide the pile into a pile of $m$ pennies and another pile of $n-m$ pennies, scoring $m(n-m)$ points. You can now think of the rest of the game as splitting into a pair of subgames, one starting with $m$ pennies, the other with $n-m$.
Since $m<n$, by the induction hypothesis you’ll get $\frac12m(m-1)$ points from the first subgame. Similarly, $n-m<n$, so by the induction hypothesis you’ll get $\frac12(n-m)(n-m-1)$ points from the second subgame. (Note that the two subgames really do proceed independently: the piles that you create in one have no influence on what you can do in the other.)
Your total score is therefore going to be
$$m(n-m)+\frac12m(m-1)+\frac12(n-m)(n-m-1)\;,$$
which (after a bit of algebra) simplifies to $\frac12n(n-1)$, as desired, and the result follows by (strong) induction.
I believe the crux of Noble's question, as presented in his recent comment, is:
[B]ut I can't see how assuming it's true for more than one value is more powerful.
In logical terms, we say that a statement $A$ is stronger than a statement $B$ if $A \implies B$. It is clear that -- forgive me for writing $\wedge$ for and when discussing logical statements --
$A \wedge A' \implies A$,
and more generally
$A_1 \wedge A_2 \wedge \ldots \wedge A_n \implies A_n$.
In other words, assuming a set of things is stronger than assuming a subset of things.
This is the sense in which strong induction is "stronger" than conventional induction: for your predicate $P$ indexed by the positive integers, assuming $P(1) \wedge \ldots \wedge P(n)$ is stronger than just assuming $P(n)$. In more practical terms, the more hypotheses you assume, the more you have to work with and it can only get easier to construct a proof.
Now let me supplement with further comments:
Nevertheless the principle of mathematical induction implies (and, more obviously, is implied by) the principle of strong induction, via the simple trick of switching from the predicate $P(n)$ to the predicate $Q(n) = P(1) \wedge \ldots P(n)$.
Here is a further possible source of confusion in the terminology. Suppose I have a theorem of the form $A \wedge B \implies C$. Someone else comes along and proves the theorem $A \implies C$. Now their theorem is stronger than mine: i.e., it implies my theorem. Thus when you weaken the hypotheses of an implication you strengthen the implication. (While we're here, let's mention that if you strengthen the conclusion of an implication, you strengthen the implication.) This apparent reversal may be the locus of the OP's confusion.
Best Answer
One way to do this is to prove $P(1,n)$ for all values of $n\geq1$. Then make the induction hypothesis that for some $m>1$, $P(m,n)$ is true for all values of $n\geq1$, and prove that $P(m+1,n)$ is true for all values of $n\geq1$. This proves that that $P(m,n)$ is true for $m\geq1$ and all values of $m$. In proving that $P(m+1,n)$ is true for all $m,n\geq1$, you are, of course, free to use any sort of induction you choose.