For some property P(n)

Its true for 0.

Since its true for 0, its true for 1.

etc..... until n.

Theorem: The sum of the first n positive natural numbers is n(n+1)/2.

Proof: By induction; Let P(n) be the sum of te=he first n positive natural numbers is n(n+1)/2. 
- For our base case, we need to show P(0) is true. So, P(0) = 0; which is true. 
- For the inductive step, assume that for some n E N that P(n) holds, meaning that 1 +2 + ... + n = n(n+1)/2.
  - We assume that P(n) is true, and simplify and replace. So, sum of n+1 = n(n+1)/2 + (n+1).  
  - n(n+1)/2 + (n+1) =  (n+1)(n+2)/2 = P(n+1).

To prove that some property hold of all natural numbers.

prove P(0) is true

prove that for all n E N, that if P(n) is true, then P(n+1) is true as well.

Conclude by induction that P(n) holds for all n.

Easier way to multiple term sums.
Identity element: 0. So sum of numbers is empty sum and defined to be 0.

Peel off the last term of the sum; many inductive proofs on sums will use this trick.

Theorem: Summation of 2ⁱ from 0 to n-1 = 2ⁿ -1. 

Proof: By induction. Let P(n) be summation of 2ⁱ from 0 to n-1 = 2ⁿ -1.
- base case: P(0) = 0, which is true.
- inductive step: P(n+1) - peel off the last term. You get 2ⁿ - 1 + 2ⁿ = 2ⁿ⁺¹ -1. Which is P(n+1)!