On Mon, 15 Jul 2013, david petry wrote: > 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. > > > 1. Base case: > > Ordinary induction: Prove P(1) > > Double induction: Prove P(1,1) > > > 2. Inductive step: > > Ordinary induction: For x in N, assume P(x) and prove P(x+1) > > Double induction: For x, y in N, assume P(x,y) and prove P(x+1,y) and P(x,y+1).
> I don't think that's right. > Base case: prove for all n, P(1,n) and P(n,1) > It correct. From P(1,1) comes P(1,2), P(1,3),.. so by simple induction for all n P(1,n). What he's omitted is that proving doubled induction requires simple induction.
> Inductive step: Assume P(x,n) for all n <= y, and assume P(n,m) for all m and for all n < x, prove P(x, y+1) > >