Introduction

• Proof by induction is a method used to prove a statement is true for all natural numbers, or sometimes for all natural numbers that are greater than some specific value.
• The natural numbers are all positive integers: 1, 2, 3, 4, 5, 6, ..., ∞. Sometimes zero will also be included.
• The components of a proof by induction are the base case and the induction step. The induction step includes the induction hypothesis and induction claim.

Base Case

• Let the statement to be proven be represented by (*).
  • As an example, in the course of this explanation we will prove the following statement:
  • n

    ∑

    i

    =

    1

    (

    2

    i

    )
    =
    2

    (

    n

    +

    1

    )

    −

    2
    (*)
    for
    all
    n
    >
    0.
• The first step in the proof is the base case. It involves proving that (*) is true for the lowest possible value of n, which we will call n₀.
• Usually the question will ask for the statement (*) to be proven for all natural numbers, so for n₀ = 0 or n₀ = 1.
  • Since this example asks for all n > 0, choose n₀ = 1.
• If the question specifies another number, like asking you to prove for n ≥ 5 or n > 3, then you just make the base case n₀ = 5 or n₀ = 4 instead.
• Once the value of the base case n₀ has been identified, the statement (*) must be proven true for n = n₀.
• So we replace n with the number chosen for n₀ in (*). Each side is then simplified until the truth of the statement is trivial.
  • Left
    side:
    n₀

    ∑

    i

    =

    1

    (

    2

    i

    )
    =
    1

    ∑

    i

    =

    1

    (

    2

    i

    )
    =
    2

    1
    =
    2
    .
  • Right
    side:
    2

    (

    n₀

    +

    1

    )

    −

    2
    =
    2

    (

    1

    +

    1

    )

    −

    2
    =
    2

    2

    −

    2
    =
    4

    −

    2
    =
    2
    .
  • Since both sides are equal when n = n₀, (*) is true for the base case.

Inductive Step

• We now assume that the statement (*) is known to be true for all values of n up to some fixed number k, but is not known to be true for any values of n greater than k.
• So we replace n with k in (*) and assume this new statement (**) to be true. This is called the induction hypothesis.
  • Assume
    k

    ∑

    i

    =

    1

    (

    2

    i

    )
    =
    2

    (

    k

    +

    1

    )

    −

    2
    (**)
    is
    true
    for
    all
    n = n₀, ..., k;
    especially
    n = k.
• To complete the induction step, it must then be proven that (*) is true for n = k + 1, using the induction hypothesis (**).
• We replace n with k + 1 in (*) and call this statement the induction claim (***). Proving that (***) is true using the induction hypothesis (**) is the goal of the induction step.
  • Then
    prove
    for
    n = k + 1
    that
    k

    +

    1

    ∑

    i

    =

    1

    (

    2

    i

    )
    =
    2

    (

    k

    +

    1

    +

    1

    )

    −

    2
    (***)
    is
    true
    if
    the
    induction
    hypothesis
    is
    true.
• We start by rearranging the left side of (***) to contain the left side of the induction hypothesis (**). This allows us to use (**) for substitution.
  • k

    +

    1

    ∑

    i

    =

    1

    (

    2

    i

    )
    =
    k

    ∑

    i

    =

    1

    (

    2

    i

    )

    +

    2

    (

    k

    +

    1

    )
    .
• Since the induction hypothesis (**) is assumed to be true, each side of (**) can replace the other.
  • k

    ∑

    i

    =

    1

    (

    2

    i

    )

    +

    2

    (

    k

    +

    1

    )
    =
    2

    (

    k

    +

    1

    )

    −

    2

    +

    2

    (

    k

    +

    1

    )
    by
    the
    induction
    hypothesis.
• The induction hypothesis (**) can be used repeatedly. It must be cited whenever it is used in the proof!
• In this way, the left side of the induction claim (***) is transformed into the right side of (***).
  • 2

    (

    k

    +

    1

    )

    −

    2

    +

    2

    (

    k

    +

    1

    )
    =
    2

    *

    2

    (

    k

    +

    1

    )

    −

    2
    =
    2

    (

    k

    +

    1

    +

    1

    )

    −

    2
    ,
    which
    is
    the
    right
    side
    of
    the
    claim
    (***).
• The induction step is now complete. We have proven that if (*) is true when n is some natural number k, then (*) is also true for n = k + 1.
  • Therefore
    if
    k

    ∑

    i

    =

    1

    (

    2

    i

    )
    =
    2

    (

    k

    +

    1

    )

    −

    2
    is
    true,
    then
    k

    +

    1

    ∑

    i

    =

    1

    (

    2

    i

    )
    =
    2

    (

    k

    +

    1

    +

    1

    )

    −

    2
    is
    true.
• We already know from the base case that the statement (*) is true for n = n₀. Now, using the induction step, we know that (*) must also be true for n = n₀ + 1.
• Since the statement (*) is true for n = n₀ + 1, then by the induction step it must also be true for n = n₀ + 2, and then for n = n₀ + 3, and so on for all the infinitely many natural numbers greater than n₀.
• So, using proof by induction, the original statement (*) is shown to be true for all natural numbers greater than or equal n₀.
  • Therefore
    n

    ∑

    i

    =

    1

    (

    2

    i

    )
    =
    2

    (

    n

    +

    1

    )

    −

    2
    for
    all
    n > 0.

Further Comments

• To show that two expressions A and B are equal, you need to rearrange A into the form of B, B into the form of A, or both A and B into the form of C. It will not prove anything to start with A = B and derive an identity.
  • Example:
    5 = -5
    since
    5

    2
    =
    25
    =
    (-5)

    2
    .
  • Example:
    1 = 2
    since
    1

    *

    0
    =
    0
    =
    2

    *

    0
    .
  • Both conclusions are wrong.
  • Correct statements can be derived from incorrect statements, but incorrect statements cannot be derived from correct ones.
• A variation of induction is strong induction.
  • For some problems, to prove the induction claim for n = k + 1 it is not enough to assume that the induction hypothesis is true for n = k. Instead it needs to be assumed true for all n = n₀, ..., k.
  • The procedure is the same. After proving the induction claim for n = k + 1, you then know that if the statement is true for n = n₀, ..., k, it is also true for n= n₀, ..., k, (k + 1).
  • Not all problems require this more comprehensive form of proof by induction. An example that does is the proof that all positions in the game 'Chomp' are either winning or losing positions, seen here under Some food for thought > Some theorems and proofs > Is it possible that there are positions where neither side can enforce a win?
• Proof by induction is not only applicable for formulas with one parameter n, but also for formulas with multiple parameters.
  • For example, a proof that the number of staircases that are P steps high and Q steps wide is (P+Q)!/(P!Q!) is given for the game 'Chomp' here under Some food for thought > Some More Math Around Chomp > How many different positions ... fit into a rectangle with P rows and Q columns? > Proof of Explicit Formula by Induction.