Strong Induction

Videos (~35 minutes)

Strong Induction (16:00)
More on Strong Induction (11:29)

Reading (~30 minutes)

Chapter 5 of Connecting Discrete Mathematics and Computer Science by David Liben-Nowell, pages 28-37.

Warmup (~50 minutes)

Problem 1

Write a proof of the following theorem using strong induction. State explicitly whether you are using bounded or unbounded strong induction.

Theorem 1 Suppose that a rectangular chocolate bar contains \(n\) identical squares of chocolate and that I am allowed to break the chocolate bar along any row or column. Prove that the number of breaks required to reduce the chocolate bar to individual pieces is exactly \(n-1\).

Problem 2

Liben-Nowell, Problem 5.38

Consider the following algorithm for determining whether an integer is odd. I’ll describe this algorithm as a Python function.

def is_odd(n):
    if n == 0:
        return False
    else:
        return not is_odd(n-1)

Consider the following theorem:

Theorem 2 The function is_odd(n) returns True if and only if n is an odd integer.

Part A

This theorem is incorrect! Please identify the issue. Then, suggest a small fix to the theorem statement so that the theorem would be correct.

Part B

Please prove your modified version of the theorem using any induction technique.