Induction and Recursion Clinic

Retrieval Prompts

1. List the five visible parts of a clean induction proof.
2. Explain when strong induction is more natural than ordinary induction.
3. Explain why structural induction mirrors a recursive definition.
4. State the difference between assuming P(n) and assuming the statement for all smaller values.

Compare and Distinguish

Write a short explanation separating:

• ordinary induction versus strong induction
• induction on integers versus structural induction on recursive objects
• inductive hypothesis versus theorem conclusion
• valid use of the inductive hypothesis versus circular reasoning

Common Mistake Check

Find the flaw in each move:

1. "Assume P(n + 1) and prove P(n + 1)."
2. "The base case is obvious, so I skipped it."
3. "In the inductive step, I used the theorem for all smaller values even though I set up ordinary induction."
4. "I used induction on string length even though the recursive constructors were easier to follow directly."

Mini Application

Do three pieces of work:

1. Write one full ordinary-induction proof.
2. Write one strong-induction proof or a least-counterexample proof.
3. Write one structural-induction proof on a recursively defined object such as strings, lists, or expressions.

Then revise one of the proofs after a self-review pass where you check:

• base case clarity
• exact statement of the hypothesis
• where the hypothesis is used
• whether the conclusion reconnects to the target proposition

Evidence Check

This page is complete only if at least one of your proofs was revised after finding a real weakness in the first draft.