Chapter3 - Counting 101 - Recursion and Recurrence(2)
Book - Python Algorithms by Magnus Lie Hetland
Chapter 3 - Counting 101Permalink
Guessing and CheckingPermalink
Inductive Proof (κ·λ©μ μ¦λͺ )
Unraveling recurrence and finding a pattern is subject to unwarranted assumption. To be sure that a solution is correct, we should conjure up a solution by guess work or intuition and then show that itβs right.
For example, take
We want to check whether
To find this, we try to verify that
We set
How about large values for n?
This is where the induction comes in. The idea is quite simple: We start with
By proving an induction step, showing that if our solution is correct for
Strong InductionPermalink
Letβs do recurrence 8 from [table 3-1]. Now, an induction hypothesis will be about all smaller numbers. More specifically, Iβll assume that
[Table 3-1]
Leave a comment