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:

```
def list_length(l):
if is_null(l):
return 0
else:
return 1 + list_length(tail(l))
def replicate(v, n):
if n == 0:
return []
else:
return cons(v, replicate(v, n-1))
```

Prove the following claim using mathematical induction.

**Claim**: for all values `v`

and natural
numbers `n`

,
`list_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`

, `list_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:`0)) list_length(replicate(v, -->* list_length([]) -->* 0`

Which is the right-hand side of the equivalence.

`n`

=`k+1`

. We must prove that:**Goal**:`list_length(replicate(v, n))`

≡`0`

.From our induction hypothesis, we know that

`list_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\)). For example, \(d_2 = 3\),
\(d_3 = 5\), and \(d_4 = 7\). 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.