Induction and recursion
Proof by induction (base case, inductive step, conclusion; simple and strong induction) and its programming twin: base case and recursive call, termination and correctness of a recursive function.
- 27 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Scenarios
- Understand
A few cards from the deck
Proof by induction: what is it?
Show the answer
A proof that a property holds for every integer from a given starting value: check it for that first value, then prove that whenever it holds for one integer, it holds for the next.
Think of dominoes: the first falls, and each domino that falls knocks over the next, so they all fall.
What does this program print?
```python
def f(n):
if n == 0:
return 1
return n * f(n - 1)
print(f(4))`24101206
Show the answer
24f(4) = 4 × f(3) = 4 × 3 × 2 × 1 × f(0) = 24, since the base case returns 1. 120 is f(5), 6 is f(3), and 10 would add instead of multiplying.
A proof by induction goes in three stages: the …, the …, then the conclusion.
Show the answer
A proof by induction goes in three stages: the base case, the inductive step, then the conclusion.
The base case checks the property for the first value, the inductive step carries it from n to n + 1, the conclusion deduces it holds for all n from that value on. Neither of the first two is enough alone.
Inductive step: what is it?
Show the answer
The step that proves, for an arbitrary integer n, that if the property holds for n, then it holds for n + 1.
The property for n is not proved, it is assumed: this is the induction hypothesis. What is proved is the implication P(n) ⟹ P(n + 1).
To prove that every integer n ≥ 2 is a product of primes, one writes n + 1 = a × b with 2 ≤ a, b ≤ n. Which kind of argument is needed?
- Simple induction, because the hypothesis for n alone is enough
- Double induction, with two consecutive base cases, n = 2 and n = 3
- No induction, because primes are handled by testing every divisor
- Strong induction, because a and b are two arbitrary integers ≤ n
Show the answer
Strong induction, because a and b are two arbitrary integers ≤ n
a and b can be any integers between 2 and n, not just n: the property is needed for all smaller integers, hence strong induction. When n + 1 is prime, it is directly a product of a single factor.