**what**mathematical induction is about. This post focuses more on the mechanics of writing a proof.

A proof is the mathematical form of argument or persuasion. A proof consists of a sequence of logical statements, each of which is shown to be a

**true**sentence based only on information previous to that sentence. Examples of sentences that might appear in a proof are

**equations**or

**inequalities**for which there is clear reason that it is true, and

*never*based on what we hope is true or will later show is true.

For example, suppose I needed to prove (x+1)

^{2}=x

^{2}+2x+1. In a proof, I can not write down this equation as the first statement because it is not something I know (yet). Instead, I can write down equations known to be true based on basic principles:

- (x+1)
^{2}= (x+1)(x+1) (meaning of power 2) - (x+1)(x+1) = x(x+1) + 1(x+1) (distributive law)
- x(x+1) + 1(x+1) = x
^{2}+x + x+1 (distributive law again) - x
^{2}+x + x+1 = x^{2}+2x+1 (collecting like terms)

**declaring**that the result of applying a rule

**demonstrates**that the sentence is actually true. (This is a subtle distinction that you need to fight your mind until it sinks in.) Technically, our proof is not yet complete. Each sentence on its own is a complete, true sentence. However, we need to end by stating that the sentence we were trying to prove is actually true:

- (x+1)
^{2}=x^{2}+2x+1 (equivalence of equal quantities, or substitution)

Recall that the Principle of Mathematical Induction (PMI) involves verifying the two conditions:

- Show that the first statement in the chain, which we call S(1), is true.
- Show that if any single statement in the chain, which we call S(n), is true, then this implies the next statement, which will be S(n+1), is also true.

**every**proof by induction involves two subproofs (showing S(1) is true; showing S(n) implies S(n+1)) followed by an application of the PMI. The subproofs are the method we verify that the two conditions of the PMI have been satisfied.

Here is what to look for in the subproofs.

- S(1) is almost always very easy to show. However, you still need to be clear that you follow the pattern of a proof described above.
- Showing S(n) implies S(n+1) will consist of
**assuming**that S(n) is true*for some n*(don't forget that this is a specific but unspecified value, so you must leave n or k, depending on the label being used, as a symbol and not an actual number). Then the proof will almost always rely on some type of**recursive**relation between a quantity involved in the statement S(n) and a similar quantity in the statement S(n+1). - After the subproofs are complete, you must
**invoke**the PMI and then declare that the statements are true for**every**n=1, 2, 3, ....

**Example**: Given a sequence defined by x1=3 and the recursive relation x

_{k+1}=x

_{k}+2 for k=1, 2, 3, ..., prove that x

_{k}=1+2k for k=1, 2, 3, ....

Notice what the chain of statements we are trying to prove will be. The sentence S(k) is the statement x

_{k}=1+2k, where x

_{k}is the value of the sequence defined recursively, and 1+2k is just a formula involving k. It is very important to remember that the "=" sign in this equation is

**not**defining the value of the sequence, but is simply stating that the two quantities (the sequence value and the formula value) happen to always be equal.

Everything in italics is not part of the proof.

**Proof:**

**(1)**

*We first write a subproof that S(1) is true:*x

_{1}=1+2(1).

*To do this, we need to create a sequence of equations that we*

**know**are true based on the symbols themselves, and not the equation above.x

_{1}=3 (Given)

(

*We looked at the given information and saw this was provided.*)

1+2(1) = 1+2 = 3 (Arithmetic)

(

*We needed an equation involving*1+2(1)

*so we wrote down an equation that was based on the rules of evaluating this formula.*)

So x

_{1}=1+2(1). (Equivalence)

(

*Earlier, we showed*x

_{1}=3

*and then we showed*1+2(1)=3

*, so this means the two quantities are equal. This ends the subproof since we just finished writing the statement corresponding to*S(1)

*being true.*)

**(2)**

*We next write a subproof that S(k) implies S(k+1) for k=1,2,3,...*

*To do this, we will start by*x

**assuming**S(k) is true for some unspecified k. Using the recursion to compute_{k+1}

*we will demonstrate that S(k+1) is also true. Note: S(k+1) is the statement x*.

_{k+1}=1+2(k+1)Assume x

_{k}=1+2k is true for some k=1, 2, 3, ....

x

_{k+1}=x

_{k}+2 (Given recursive definition of sequence)

(

*The statement we are trying to prove involves the symbol*x

_{k+1}

*so we need to create equations based on that symbol.*)

x

_{k+1}=(1+2k)+2 (Substitution: x

_{k}=1+2k from assumed hypothesis)

(

*This is the key step: we use the recursive connection between*x

_{k+1}

*and*x

_{k}

*to establish a formula for*x

_{k+1}.)

x

_{k+1}=3+2k (Algebra)

(

*We now have a simple formula for*x

_{k+1}

*and now we turn our attention to the other half of the statement S(k+1), namely the formula*1+2(k+1).)

1+2(k+1) = 1 + 2k + 2 (Distributive law)

(

*We are creating a true equation involving the formula by considering the results of applying mathematical laws.*)

1+2(k+1) = 3+2k (Algebra from above: 1+2=3)

(

*Our target should always be that the formula with k+1 in place of k will match whatever we found by the recursion to compute a value for*x

_{k+1}.)

So x

_{k+1}=1+2(k+1) (Equivalence or Substitution)

That is, S(k) implies S(k+1) for k=1, 2, 3,....

(

*This ends the second subproof because we just finished writing the statement we were trying to prove in this part. We are now ready to invoke the PMI.*)

Since S(1) is true and S(k) implies S(k+1) for k=1, 2, 3, ..., the Principle of Mathematical Induction guarantees S(k) is true for every k=1, 2, 3, .... That is, x

_{k}=1+2k for k=1, 2, 3, ...

♦

## No comments:

Post a Comment