Virgil
Posts:
8,833
Registered:
1/6/11


Re: Double Induction  A brief note that may help
Posted:
Jul 15, 2013 5:34 PM


In article <cac54bbd1fb445099197e1aa3860ab95@googlegroups.com>, Dan Christensen <Dan_Christensen@sympatico.ca> wrote:
> The explanations of double induction online can be quite confusing. No doubt > I am reinventing 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). > > Comments? >
Seems adequate! 

