Demo of proving a proposition by induction

inductive-proof.md

The sum of all natural numbers from 0 to n is

sum(n) = n*(n+1)/2

Proof

• Base case: Is it true for sum(0)?

  sum(0) = 0(0+1)/2 = 0
  

  Yes!

• Inductive case: Assume sum(i) = i(i+1)/2 is the sum of integers from 0 to i. Then the sum of all integers from 0 to i+1 is just the sum from 0 to i (which is just sum(i)) plus i+1

  sum(i) + (i+1) = i(i+1)/2 + (2i + 2)/2   <-- by mult. & div. by 2
                 = (i(i+1) + 2i + 2)/2     <-- by Distributive Law
                 = (i^2 + 3i + 2)/2
                 = (i+1)(i+2)/2            <-- factoring (i^2 + 3i + 2)
                 = (i+1)((i+1)+1)/2
                 = sum(i+1)
  

So we've shown the base case, and we've shown that the statement sum(i) is the sum of integers from 0 to i implies the statement sum(i+1) is the sum of integers from 0 to i+1.

So, by the principle of induction, we have that for all natural numbers n, sum(n) is the sum of integers from 0 to n, where

    sum(n) = n(n+1)/2