Proof by Induction example

Here is an example of proof by induction.

Proposition: 1+2+3+...+x = \frac{x(x+1)}{2}

Proof: in order to prove this we will follow the instructions shown in the previous page. First let x = 1 for our base case. P(1) = 1 = \frac{1(1+1)}{2}. Therefore our base case is true.

Now for our inductive hypothesis. We now assume that 1+2+3+...+x = \frac{x(x+1)}{2} is true for x=n and now we prove for the case x= n+1.

1 + 2 + 3 + ... + n + n + 1 = ( 1 + 2 + 3 + ... + n ) + n + 1

                                               = (\frac{n(n+1)}{2})+n+1

We can collapse that part because of our inductive hypothesis.

                                               = \frac{n(n+1)}{2}+\frac{2(n+1)}{2}

                                               = \frac{n^2+3n+2)}{2}

                                               = \frac{(n+1)((n+1)+1)}{2}

This proves that 1+2+3+...+x = \frac{x(x+1)}{2}.

Induction proofs are used to prove closed forms and greedy algorithms which are both important components in the design and analysis of algorithms. Generally speaking proof of induction is used for statements of facts more often then for statements such as “if P then Q” or “P if and only if Q”.

Previous | Next

  1.  What is a proof?
  2. Direct Proof Part I
  3. Direct Proof Part II
  4. Proof by  Contradiction
  5. Proof by Induction
  6. Proof by Induction example
  7. Proof by Contrapositive
  8. Proof of Existence
  9. Proof of Uniqueness
  10. Disproof
  11. Conclusion

Filed under : Mathematics

Sharing the Wonder