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.

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 , , and , .

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

  • For any numbers and ,
  • Commutativity of multiplication: for any numbers and , .
  • Associativity of multiplication: for any numbers , , and , .

Problem 3: Problem Proof

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

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 th odd number to be (where is the first odd number: ). Prove the following claim using mathematical induction on :

Claim

Claim: the sum of the first odd numbers .

(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:

Bogus Claim and Proof

Claim: For all natural numbers , .

Proof. By induction on . In the inductive case where , our induction hypothesis states that . We must then show that :

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.