Proof by Induction

Subject: Proof by Induction
From: Richard Mateosian <srm -at- C2 -dot- ORG>
Date: Fri, 10 Feb 1995 23:36:15 -0800

>The first step in proof by induction is to assume that the thing you want
>to prove is in fact true. Now that's what I call begging the question.

That may be begging the question, but it's not exactly proof by induction.

To prove by mathematical induction that A(n) is true for all n > n0, the
steps are:

1. Prove A(n0+1).
2. Prove that if n > n0, then A(n) implies A(n+1)

For example, if S(n) is defined as 1 + ... + n, then to prove that S(n) =
n(n+1)/2 for all n > 0, the steps are:

1. S(1) = 1 = 1(1+1)/2
2. For n > 0, S(n+1) = S(n)+n+1. Therefore, S(n) = n(n+1)/2 implies S(n+1) =
(n(n+1)/2)+n+1 = (n+1)(n/2 +1) = (n+1)(n+2)/2. QED

In step 2 we don't actually assume what we're trying to prove. We just show
that its truth for any integer implies its truth for the next integer. ...RM

Richard Mateosian Technical Writer in Berkeley CA srm -at- c2 -dot- org


Previous by Author: Who's the author?
Next by Author: Credits
Previous by Thread: Re: Conditional Text
Next by Thread: Re: Graphics Don't Help


What this post helpful? Share it with friends and colleagues:


Sponsored Ads