0

I'm studying an example (in Introduction to Algorithms) of using the substitution method to guess and then prove an upper bound on a recurrence.

I've almost fully understood the example given on pages 63-64 of the second edition (available to view at the link above). However, there is one thing I don't yet understand.

On page 64, near the end of the example, the authors argue as follows: 'Observe that for $n > 3$, the recurrence does not depend directly on $T(1)$. Thus we can replace $T(1)$ by $T(2)$ and $T(3)$ as the base cases in the inductive proof'.

Why does the fact that the recurrence doesn't depend directly on $T(1)$ for $n>3$ mean that this replacement can be made? (I think that the answer to this might involve a subtle concept/feature about/of the base case(s) of an inductive proof, but I'm not sure.)

I found this Mathematics post, the first answer of which made me feel as though I had a slightly clearer picture of why such a replacement is valid, but I'm not fully there just yet!

Caleb Owusu-Yianoma
  • 1,197
  • Well you need the mathematical proposition to be true for $n>3$ so you don't need it to be true for $n=1,2,3$ ...It must be true for $n=4$. If you want the proposition to be true for n>3 – user577215664 Sep 12 '17 at 12:21
  • 1
    @Isham, That is true. However, I still don't see how the observation made by the authors leads to the statement 'Thus we can replace...' Am I making sense? – Caleb Owusu-Yianoma Sep 12 '17 at 12:47
  • @MauroALLEGRANZA I understand that. But the induction proof starts from $n_0 = 2$, doesn't it (not $n_0 = 4$)? – Caleb Owusu-Yianoma Sep 12 '17 at 12:48
  • Correct; let $n_0=2$. – Mauro ALLEGRANZA Sep 12 '17 at 12:52
  • In general, an inductive proof can start from a number $n_0$ whatever; if we prove $P(n_0)$ and we prove that $\forall n (P(n) \to P(n+1))$, we can conclude that $P$ holds for every $n \ge n_0$. – Mauro ALLEGRANZA Sep 12 '17 at 12:54
  • @MauroALLEGRANZA Yes. I see that. :) But why, in this case, do we need to prove $P(n_0)$ and $P(n_1)$ as base cases? (And I still think the question in my original post remains unanswered. I wonder why the authors' observation means that the original base case ($n_0=1$) can be replaced with 2 base cases ($n_0=2$) and ($n_0 + 1 =3$). As I said in reply to Isham, I don't see how the observation leads to the statement 'Thus we can replace...') – Caleb Owusu-Yianoma Sep 12 '17 at 14:00

0 Answers0