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=x2+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) = x2+x + x+1 (distributive law again)
- x2+x + x+1 = x2+2x+1 (collecting like terms)
- (x+1)2=x2+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.
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, ....
Notice what the chain of statements we are trying to prove will be. The sentence S(k) is the statement xk=1+2k, where xk 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.
(1) We first write a subproof that S(1) is true: x1=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.
(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 x1=1+2(1). (Equivalence)
(Earlier, we showed x1=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 assuming S(k) is true for some unspecified k. Using the recursion to compute xk+1 we will demonstrate that S(k+1) is also true. Note: S(k+1) is the statement xk+1=1+2(k+1).
Assume xk=1+2k is true for some k=1, 2, 3, ....
xk+1=xk+2 (Given recursive definition of sequence)
(The statement we are trying to prove involves the symbol xk+1 so we need to create equations based on that symbol.)
xk+1=(1+2k)+2 (Substitution: xk=1+2k from assumed hypothesis)
(This is the key step: we use the recursive connection between xk+1 and xk to establish a formula for xk+1.)
(We now have a simple formula for xk+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 xk+1.)
So xk+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, xk=1+2k for k=1, 2, 3, ...