On Monday, July 15, 2013 1:50:39 PM UTC-7, Dan Christensen wrote: > The explanations of double induction online can be quite confusing. No doubt I am re-inventing wheel here, but you may find the following analogy to ordinary induction to be useful. > > > > With ordinary induction, we want to prove that for all x in N, we have P(x) where P is a unary predicate. > > > > With double induction, we want to prove that for all x, y in N, we have P(x,y) where P is a binary predicate. >
Personally, and this is a matter of taste and depends on the situation, I would do induction on y first then x.
First take P(1, y) and proceed with induction.
Base Case: Prove P(1, 1).
Inductive Case: Assume P(1, y) and prove P(1, y+1).
Now, we know P(1, y) is true for all y, so we perform induction on x.
Base Case: P(1, y) for arbritrary y, already shown above.
Inductive Case: Assume P(x, y) and prove P(x+1, y) again for arbitrary y.
This keeps all of our "ducks in a row" so to speak. In your method, how can you prove P(x+1, y) from P(x, y) when all you are sure of is P(x, y) when y = 1?
Of couse, in my method, the order of induction on y and x could be interchanged.