Re: Strong Induction clarification....

From: Dennis May (dennis_at_NOkernelSPAMthread.e7even.com)
Date: 10/30/04 

Date: Sat, 30 Oct 2004 17:44:24 +0100

George wrote:

> Before some time there was a post by Arturo Magidin saying:
> ----------------------------------------------------------------------
> Formally, you do not need to prove a base case. Strong mathematical
> induction involves proving that
>
> For all n in N,
>
> if for all k in N (k<n->P(k)), then P(n).
>
> If you can really prove this proposition, then it takes care of the
> n=0 (the base case) automatically; because the antecedent of the
> implication ("for all k in N, k<n -> P(k)") is true by vacuity, and so
> if you have really proven the implication, then P(n) must follow.
> ----------------------------------------------------------------------
>
> What i can't understand is the "because" he uses. Or to say it
> clearly how the base case is derived automatically, by proving the
> above proposition.
> Or to say it even more clearly:
> If we prove the aforementioned proposition, how can we prove that P(0)
> is true?
The thing you need to prove is:

For all n in N, ( (For all k in N, (k<n => P(k))) => P(n) )

In particular you need to prove the case where n = 0, i.e.

For all k in N (k<0 => P(k)) => P(0)

k<0 is always false, so k<0 => P(k) is always true, so as part of the
proof you show that

true => P(0)

i.e. that P(0) is true.

Relevant Pages

  • Re: Strong Induction clarification....
    ... > George wrote: ... >> clearly how the base case is derived automatically, by proving the ... strong and weak induction are equivalent. ... every non-empty subset of N has a least element. ...
    (sci.math)
  • Re: Rigorous proof of natural numbers properties (by Edmund Landau).
    ... >then the argument given does not define a sequence, ... >recursion theorem. ... >by induction, fis defined for all natural numbers n and the above ... I think it's relevant here to point out that we're not proving ...
    (sci.math)
  • Proof of probability distribution of inhomogeneous Poisson process
    ... I've seen a proof in old lecture notes on Poisson processes which uses an induction argument and ODE techniques on proving that the distribution function of an inhomogeneous Poisson process over equals: ... using induction you can do it for arbitrary k. ...
    (sci.math)
  • Re: Simple versus formal proof?
    ... observe, that implication does hold, so the proof by ... induction works. ... proving the result for the naturals. ...
    (sci.math)
  • Re: Induction with a hard start
    ... José Carlos Santos wrote: ... > Could someone please provide an example of a proof by induction in which ... > proving the statement for n = 1 is clearly harder than going from n to ... Prev by Date: ...
    (sci.math)