The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

Posts: 1,161
Registered: 5/24/13
Re: Double Induction -- A brief note that may help
Posted: Jul 15, 2013 11:47 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
> Download my DC Proof 2.0 software at


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.