Proof by induction

The typical method

1. Make a conjecture
2. Show it is true for
3. Assume it’s true for
4. Show it must also be true for
5. Conclude it’s true for all natural numbers (where )

Prove that the series

• Test when :
  • LHS:
  • RHS:
  • LHS = RHS
  • So it’s true for
• Assume that the statement is true for :
• Test for :
  • LHS:
  • Check if we can make the new sum of end terms equal our expected result ():
  • So LHS:
  • RHS:
  • LHS = RHS
  • So it’s true for
• In conclusion:
  • It’s true for
  • IF it’s true for , then it’s also true for $n=k+1
  • Since it is true for , by induction, it’s true for all integers (where )

How do we know that all integers are covered?

You might be a bit confused as to how we can get from knowing that is true, to knowing that all integers are true.

If is true for a specific value of , then the next integer must also be true. So:

• We know that
• let
• Because the value of is satisfied, the value of also is:
• Now let
  • We can do exactly the same as above to find that is also true
• …and so on, for all positive integers.

Proving using standard summation results

Prove

• Check when :
  • LHS:
  • RHS:
  • So is satisfied as it holds true!
• We now assume that also holds true.
• Find RHS when :
  • $=\frac13k^2-
• Check if holds true:
  • LHS:
    • …which is more than when , or more.
  • RHS: