Skip to main content

Induction and Recursion Clinic

Attempt P13–P17 after cluster 5. Allow 5–7 hours and save your first attempt. Then consult feedback.

  1. P13 — Ordinary induction. Prove 1+3+...+(2n−1)=n² for n≥0, interpreting n=0 as an empty sum. Write the induction hypothesis and its exact use.
  2. P14 — Strong induction. Prove every integer n≥12 is 4a+5b for nonnegative integers a,b. Identify enough initial cases and the lower bound on n in the step.
  3. P15 — Least counterexample. Prove every integer n≥2 has a prime factor. Do not assume uniqueness of prime factorization. Show the smaller number remains in the theorem's domain. Explain why halving positive reals need not stop.
  4. P16 — Structural induction. For the lab's full binary tree grammar, prove L=I+1 and N=2L−1. Then permit unary nodes: find a counterexample and derive the identity relating leaves to binary internal nodes when unary nodes exist.
  5. P17 — Loop invariant. Implement a positive-entry counter. Prove the prefix invariant, exit conclusion and termination. Diagnose a loop ending at n−1 rather than n with the smallest failing list. State the immutability assumption.

Review a peer proof or a deliberate faulty proof for one genuine logical gap. Using size induction instead of structural induction is valid if its hypothesis covers the required smaller objects. Preference for a method is not a correctness rule.