Lab: Mathematical Induction Practice

Now, we’ll practice writing inductive proofs, but this time, over the natural numbers. We’ll also begin to test our understanding of proof mechanics by exploring incorrect proofs of correct propositions. As we shall see, writing proofs is one thing, but identifying where proofs go wrong is quite tricky!

Problem 1: Mathematical Induction Practice

Consider the following Python definitions:

def cons(x, l):
    return [x, *l]

def length(l):
    match l:
        case []:
            return 0
        case [_, *tail]:
            return 1 + length(tail)

def replicate(v, n):
    if n == 0:
        return []
    else:
        return cons(v, replicate(v, n-1))

Prove the following claim using mathematical induction.

~~~admonish problem title=”Claim” For all values v and natural numbers n, length(replicate(v, n)) ≡ n.

## Problem 2: More Mathematical Induction Practice

Consider the following claim regarding the distribution of powers and multiplication.

~~~admonish problem title="Claim"
For all natural numbers $a$, $b$, and $n$, $(ab)^n = a^n b^n$.

Prove this claim by mathematical induction on $n$. In your proof, you may only rely on the following mathematical facts:

• For any numbers $x$ and $n$, $x \cdot x^{n-1} = x^n$
• Commutativity of multiplication: for any numbers $x$ and $y$, $xy = yx$.
• Associativity of multiplication: for any numbers $x$, $y$, and $z$, $x(yz) = (xy)z$.

Problem 3: Problem Proof

Here is a bogus claim about replicate and a corresponding “proof” of that claim:

~~~admonish problem title=”Bogus Claim and Proof” Claim: for all values v and natural numbers n, length(replicate(v, n)) ≡ 0.

Proof. Let v be a value and n be a natural number, we proceed by induction on n.

• n = 0. The left-hand side of the equivalence evaluates as follows:

       length(replicate(v, 0))
  -->* length([])
  -->* 0
  

  Which is the right-hand side of the equivalence.

• n = k+1. We must prove that:

  Goal: length(replicate(v, n) ≡ 0.

  From our induction hypothesis, we know that length(replicate(v, n)) ≡ 0 so we are done. ~~~

1. In a sentence or two, describe what the claim is saying and why it is incorrect.
2. In a sentence or two, describe the error in the “proof.”
3. Correct the error and attempt to finish the proof. You should get stuck, i.e., a point where you are unable to move further in the proof. Show your work to get to this point and describe in a sentence or two why you cannot proceed forward with the proof.

Problem 4: Even More Mathematical Induction Practice

We can formally define the $i$th odd number to be $d_i = 2i - 1$ (where $d_1$ is the first odd number: $d_1 = 2 \cdot 1 - 1 = 1$). Prove the following claim using mathematical induction on $n$:

~~~admonish problem title=”Claim” Claim: the sum of the first $n$ odd numbers $d_1 + \cdots + d_n = n^2$.

(_Hint_: where does the induction hypothesis appear in the left-hand side summation?)

## Problem 5: Another Problem Proof (Optional)

Here is yet another bogus claim and "proof" of that claim:

~~~admonish problem title="Bogus Claim and Proof"
**Claim**: For all natural numbers $n$, $n + 1 \leq n$.

_Proof_.
By induction on $n$.
In the inductive case where $n = k + 1$, our induction hypothesis states that $k + 1 \leq k$.
We must then show that $(k + 1) + 1 \leq k + 1$:

$$
\begin{align*}
(k + 1) &\;\leq k                & \text{inductive hypothesis} \\
(k + 1) + 1 &\;\leq k + 1        & \text{transitivity of $\leq$}
\end{align*}
$$

And thus our goal is immediately proven.

1. In a sentence or two, describe what the claim is saying and why it is incorrect.
2. In a sentence or two, describe the error in the “proof.”
3. Correct the error and attempt to finish the proof. You should get stuck, i.e., a point where you are unable to move further in the proof. Show your work to get to this point and describe in a sentence or two why you cannot proceed forward with the proof.

Lab part 2: Strong Induction

Consider the following classic numeric problem regarding making change:

Suppose that you live in a country where currency only comes in 3¢ and 10¢ denominations. Show that you can form any amount of money $n$ from 3¢ and 10¢ pieces as long as $n \geq 18$.

Let us attempt to prove this claim by induction. Really, the claims says that we can choose $x$ and $y$, such that $3x + 10y = n$ as long as $n \geq 18$. $x$ and $y$ here are the number of 3¢ and 10¢ pieces, respectively.

~~~admonish problem title=”Claim” Claim: for any natural number $n$ where $n \geq 18$, there exists natural numbers $x$ and $y$ such that $3x + 10y = n$. ~~~

1. Attempt to prove this claim by mathematical induction. Push the proof through as much as possible until you get stuck. Identify you get stuck and why you cannot make any more progress.

2. Since the proof did not work out, you might be tempted to believe that the claim is actually false; not an unreasonable conclusion. However, it turns out this claim is actually true. Develop a series of examples for $n = 18$ through $n = 26$ (9 examples in all) to convince yourself that this is the case.

3. Sometimes, a particular proof technique is not strong enough to prove a proposition. In these situations, we must resort to a different proof technique better suited for the situation at hand.

   Rather than using regular mathematical induction, we’ll invoke a variant of mathematical induction, strong induction, to prove this claim.

   Definition (Strong Induction): strong induction is a proof principle that is like mathematical induction, i.e., induction over a natural number $n$, except that we assume that our induction hypothesis holds for any natural number $k < n$.

   Regular mathematical induction allows us to handle situations where our recursive definitions decrease by one on each step. Strong induction allows us to handle situations where our recursive definitions steps by more than just one and more generally, in irregular patterns.

   Practically speaking, to use the strong induction principle:

   • We state that we are using strong induction instead of regular induction.
   • We change our induction hypothesis to reflect the fact that the hypothesis holds for any natural number $k < n$ rather than just $n-1$.
   • Finally, we also may need to include additional base cases to account for the potentially irregular pattern that our inductive object decreases by.

   Change your original, incomplete inductive proof to a strong induction proof and complete it.

   (Hint 1: now your induction hypothesis holds for any number less than $n$. Don’t overthink this part! Choose a convenient target value that is less than $n$ that you can apply your induction hypothesis to.)

   (Hint 2: now think about how much you decrease $n$ by in each inductive step. A single base case of $n = 18$ is no longer sufficient because you are no longer decreasing by one. What additional base cases do you need?)

4. Once you are done, you might think this proof feels “too simple!” In some sense it is because the corresponding algorithm for making change implied by this proof is also straightforward! In a sentence or two, describe the algorithm for making change that is suggested by your reasoning. This final bit highlights the connection between proving and algorithmic design. We can design an algorithm with correctness in mind; dually, we often can derive an algorithm from our reasoning!