Exam weight Low
Exam weight Low
Exam weight Low
Exam weight High
- To prove ∀n P(n): basis P(1); inductive step ∀k (P(k) → P(k + 1)).
🎯 How this can come up · 1 question
MCQ
In an induction proof, the assumption that P(k) is true is called the:
Correct: Inductive hypothesis.
Exam weight Low
Exam weight Low
- Template: state P(n) → basis → assume P(k) → show P(k + 1) → conclude.
Exam weight Low
Exam weight High
- Sum example: 1 + 2 + … + n = n(n + 1)/2. Add (k + 1) to both sides of P(k).
🎯 How this can come up · 1 question
Written
Prove 1 + 2 + … + n = n(n + 1)/2 for n ≥ 1.
Basis: n = 1: 1 = 1·2/2. Inductive step: assume 1 + … + k = k(k + 1)/2. Then 1 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, which is P(k + 1). So P(n) holds for all n ≥ 1.
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Medium
- Divisibility example: n³ − n divisible by 3. Expand (k + 1)³ − (k + 1) = (k³ − k) + 3(k² + k).
Exam weight Low
Exam weight Medium
- Inequality example: 2ⁿ < n!. The basis may start later than 1 (here n ≥ 4).
🎯 How this can come up · 1 question
MCQ
The basis step for "2ⁿ < n! for n ≥ 4" checks:
Correct: n = 4.
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
- Conjecture a formula by computing the first few values, then prove it by induction.
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight High
- Recursively defined function: basis f(0); recursive step f(n + 1) from f(n).
🎯 How this can come up · 1 question
MCQ
f(0) = 3, f(n + 1) = 2f(n) + 3. f(2) =
f(1) = 9, f(2) = 21.
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
Exam weight Low
No slides match this filter.