Induction / Recurrences
Least You Need to Know: Recurrences and Strong Induction
Recurrence claims often need strong induction because the next term depends on several earlier terms, not just one.
Least you need to know
- A recurrence defines later terms from earlier ones.
- If the step uses two previous values, you usually need two base cases.
- Strong induction lets you assume all earlier cases up to k.
- Check that the recurrence claim matches the domain of the sequence.
Key notation
- a_n — the nth term of a sequence
- a_n = a_{n-1}+a_{n-2} — a recurrence
- P(1),…,P(k) — strong induction hypothesis
Worked example
- Suppose
a_n = a_{n-1}+a_{n-2}forn≥3. - To prove a property of all terms, a strong induction step may use both
P(k)andP(k-1). - That is why base cases for the first terms matter.
Common mistakes
- Students often try ordinary induction when the recurrence uses multiple earlier terms.
- Students often forget one needed base case.
- Students often use the recurrence before its starting index.
How to recognize it
- Count how many earlier terms the recurrence references.
- Base cases should cover every term used before the induction starts.
- Strong induction is about having enough hypotheses available.
บทเรียนถัดไปที่แนะนำ
เรียนต่อในหัวข้อนี้ด้วย Least You Need to Know: Strong Induction
Least You Need to Know: Strong Inductionบทเรียนที่เกี่ยวข้อง
เรียนต่อด้วยบทเรียนใกล้เคียงในหัวข้อเดียวกัน