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 Racket definitions:

(define length
  (lambda (l)
    (if (null? l)
        0
        (+ 1 (length (cdr l))))))

(define replicate
  (lambda (v n)
    (if (zero? n)
        '()
        (cons v (replicate v (- n 1))))))

Prove the following claim using mathematical induction.

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.

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 an bogus claim about replicate and a corresponding “proof” of that claim:

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.

In a sentence or two, describe what the claim is saying and why it is incorrect.
In a sentence or two, describe the error in the “proof.”
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$:

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:

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.

In a sentence or two, describe what the claim is saying and why it is incorrect.
In a sentence or two, describe the error in the “proof.”
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.

CSC 208-01 (Fall 2023)

Lab: Mathematical Induction Practice

Problem 1: Mathematical Induction Practice

Problem 2: More Mathematical Induction Practice

Problem 3: Problem Proof

Problem 4: Even More Mathematical Induction Practice

Problem 5: Another Problem Proof (Optional)