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 ]
William Elliot

Posts: 2,637
Registered: 1/8/12
Re: Double Induction -- A brief note that may help
Posted: Jul 16, 2013 4:48 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Mon, 15 Jul 2013, David N Melik wrote:

> > 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).

> Sounds like an interesting idea... is there an example proof somewhere?

Proof is simple. Let S be a set of interger pairs with (1,1) in S
and for all n,m in N, If (n,m) in S, then (n+1,m) and (n,m+1) in S.

Assume (a,b) not in S and let let c be the smallest c in N for which (c,b) not
in S. Next let d be the smallest d in N for which (c,d) not in S.

Case c = 1. Then (1,d) not in S and 1 < d. Thus (1,d-1) in S and
by hypthesis, (1,d) = (1, (d-1)+1) in S, a contradiction.

Case 1 < c. Then (c-1,d) in S. Thus by hypothesis, (c,d) = ((c-1)+1,d) in S
a contradiction.

Exercise. State and prove the base and induction steps
of n-fold induction. Can there be an aleph_0-fold induction?

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.