Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Double Induction -- A brief note that may help
Replies: 13   Last Post: Jul 18, 2013 12:42 AM

 Messages: [ Previous | Next ]
 Tucsondrew@me.com Posts: 1,161 Registered: 5/24/13
Re: Double Induction -- A brief note that may help
Posted: Jul 15, 2013 11:47 PM

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.

>
>
> Dan
>

ZG

Date Subject Author
7/15/13 Dan Christensen
7/15/13 Virgil
7/15/13 David Chmelik
7/15/13 Dan Christensen
7/16/13 William Elliot
7/16/13 Brian Q. Hutchings
7/15/13 David Petry
7/16/13 William Elliot
7/15/13 Tucsondrew@me.com
7/16/13 gnasher729
7/16/13 gnasher729
7/16/13 gnasher729
7/16/13 Tucsondrew@me.com
7/18/13 Dan Christensen