We use proof by induction when our claim concerns a sequence of cases, which can be numbered. An example is the equality

S(N) = Σ 2ⁱ = 2^(N+1) - 1
         _{i=0 to N}

The cases here depend on N:

1. N = 0: S(0) = 2⁰

2. N = 1: S(1) = 2⁰ + 2¹

3. N = 2: S(2) = 2⁰ + 2¹ + 2²

…..

N = k: S(k) = 2⁰ + 2¹ + 2² + ….. + 2^k

….

1. Inductive base: Show that the claim is true for the smallest case, usually k = 0 or k = 1.
2. Proof under inductive hypothesis:
   1. Assume that the claim is true for some k
   2. Prove that the claim is true for k+1

Prove by induction that

S(N) = Σ 2ⁱ = 2^(N+1) - 1, for any integer N ≥ 0
          _{i=0 to N}

1. Inductive base: Show that the formula is true for N = 0.

When substituting N=0 in the formula, we get

S(0) = Σ 2ⁱ = 2⁽⁰⁺¹⁾ - 1 = 2 - 1 = 1
          _{i=0 to 0}

Is this true?

Solution: By definition of S, S(0) = 2⁰ = 1

By the formula we have: 2⁽⁰⁺¹⁾ - 1 = 2¹ - 1 = 1

Right sides are equal, hence the formula is true for N = 0

S(0) = Σ 2ⁱ = 2⁽⁰⁺¹⁾ - 1 = 1
          _{i=0 to 0}

2. Proof under inductive hypothesis: Assume that the formula is true for some k and prove that under this assumption the formula is true for k+1

We assume that S(k) is equal to 2^(k+1) - 1, i.e.

S(k) = Σ 2ⁱ = 2^(k+1) - 1
          _{i=0 to k}

Now we shall show that


S(k+1) = Σ 2ⁱ = 2^(k+2) - 1
          _{i=0 to k+1}

We use the defining property of this particular sequence of sums: S(k+1) = S(k) + 2^(k+1) and we substitute S(k) with its equal expression from our assumption.

Thus we have:

S(k+1) = S(k) + 2^(k+1) =

= 2^(k+1) - 1 + 2^(k+1) =

= 2. 2^(k+1) - 1 =

= 2^1+(k+1) - 1 =

= 2^(k+2) - 1

This completes our proof: We conclude that

S(N) = Σ 2ⁱ = 2^(N+1) - 1, for any integer N ≥ 0
         _{i=0 to N}

Used when we want to prove that a statement is false.
Types of statements: a claim that refers to all members of a class.

Assume that the statement is false, i.e. its negation is true.
Show that the assumption implies that some known property is false - this would be the contradiction.

EXAMPLE:

Prove that there is infinite number of primes.

Proof:

1. Assume that the statement is false, i.e. the number of primes is finite.
2. Consequences of that assumption:

There is a prime number that is the largest one - P_k
Let P₁, P₂,.. P_k are all the prime numbers, ordered.
Consider the number N = P₁*P₂*….P_k   +  1
( N is the product of all prime numbers plus one)
N is greater than Pk, and following our assumption N is not prime.
All non-prime numbers are equally divided by some prime number
(This is a known property)

Hence N should be equally divided by at least one of P₁ through P_k.

3. Contradiction:

We can see that none of the prime numbers P₁ through P_k divides N equally - there is a remainder of 1. This is the contradiction.

Based on the equivalence of P → Q and ~Q → ~P
In order to prove P → Q, we prove ~Q → ~P

Example: Prove that if the square of an integer is odd, then the integer is odd.

Proof: We will prove that if an integer is even, then its square even. We can do this using direct proof.