More Induction

Videos (~20 minutes)

Induction Proofs Involving Inequalities (6:34)
Strong Induction (10:08)

Reading (~30 minutes)

DMOI Chapter 2. The new stuff is in “Strong Induction” until end, but you will benefit from reviewing the entire chapter.

Warmup (~50 minutes)

Problem 1

You and your friend are playing the following (fun!) game. There are two piles of apples. The first player removes some positive integer number of apples from one of the piles. Then, the second player also removes some number of apples from one of the piles. Each player can remove any number of apples from one of the two piles, but cannot take apples from both piles simultaneously.

The players alternate until one of them removes the very last apple (from either pile). That player, who removes the very last apple, wins.

You deviously encourage your friend to go first. Then, you use a simple copycat strategy: whenever your friend removes \(j\) apples from one pile, you always remove the same number \(j\) apples from the second pile.

Prove the following statement using strong induction:

Proposition: If at the beginning of the game the two piles contain the same number of apples, then you (the second player) always win using your copycat strategy.

Problem 2

Motivation

In computer science, we often use induction to prove the correctness of a function – that is, we prove formally that the function does what it is supposed to do. This is sometimes called “proving a function.” For example, consider the Python function below, which reverses an input string using recursion.

def reverse_string(s):
    """
    reverse the string s. The first letter becomes the last letter, the second letter becomes the second-to-last letter, etc. 

    args: 
      s, the string to be reversed

    returns: the reversed string
    """

    if s == "":
        return ""
    else:
        return reverse_string(s[1:]) + s[0]

Here it is in action.

reverse_string("CSCI 0200")

'0020 ICSC'

We got the right answer for this input! But…would we get the right answer on every possible input? Let’s write a proof which will guarantee that we will.

Problem Statement

We’ll write a string with \(n\) characters as \(s_1s_2s_3\cdots s_{n-2}s_{n-1}s_n\).

Now we can state the thing we want to prove:

Proposition: For any \(n \in \mathbb{N}\), the result of calling the function reverse_string on the string \(s_1s_2s_3\cdots s_{n-2}s_{n-1}s_n\) is the reversal of \(s\), that is, the string \(s_ns_{n-1}s_{n-2}\cdots s_3s_2s_1\).

Prove this claim using induction.

Note: The empty string \(\epsilon\) is the string with no elements at all; this string is its own reversal.