2
$\begingroup$

I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it.

In standard induction proofs you prove a base case, assume it holds for n then show it holds for n+1 and therefore show it applies to integers larger than the base case.

For when you solve recurrences like T(n) = T(n/2) the proof has a base, assumes T(n/2) then proves it holds for T(n). Does this proof not only hold for the numbers that are multiples of two of the base cases? Would this not require an infinitely large number of base cases to show what it holds for?

Could someone please explain this to me?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
1
$\begingroup$

You're entirely correct - if all you prove is $T(1)$ and $T(n/2) \Rightarrow T(n)$, then you prove that $T(n)$ holds for all powers of $2$. One way to fix that is to prove $T(n)$ for all odd $n$, but that defeats the idea of induction. Instead, usually one actually proves the stronger $T(\lfloor n/2 \rfloor) \Rightarrow T(n)$ or $T(\lceil n/2 \rceil) \Rightarrow T(n)$, and both are enough to deduce $T(n)$ for all $n$.

In many cases, if you can prove $T(n/2) \Rightarrow T(n)$ then you can also prove the stronger claims, but it's technically more awkward. So instead of dealing with this mess, you are only shown the weaker claim. The "interesting" ideas are found already there, and to prove the stronger claim requires just working harder but no new ideas (other than routine tricks used for handling floors and ceilings).

Improve this answer
$\endgroup$
7
  • $\begingroup$ As far as I know, routine tricks are not everything required in order for this to work. $\endgroup$
    – Raphael ♦
    Jan 20, 2014 at 8:55
  • $\begingroup$ Ok, let me rephrase. Irrelevant tricks which serve but to obscure the proof. They are routine in the sense that they are the same whenever you generalize a proof from $n/2$ to $\lfloor n/2 \rfloor$. $\endgroup$
    – Yuval Filmus
    Jan 20, 2014 at 15:57
  • $\begingroup$ Well, I'm hesitant to call something an "irrelevant trick" as long as I can't get it to work out rigorously (see the question I linked; so for, a rigorous answer has not come up). But that may be just me. $\endgroup$
    – Raphael ♦
    Jan 20, 2014 at 16:07
  • $\begingroup$ These are just technicalities which obscure the picture. While technically difficult, they are not the main part of the argument, unless your analysis highlights the small perturbations originating in the bit-by-bit description of $n$. $\endgroup$
    – Yuval Filmus
    Jan 20, 2014 at 16:11
  • $\begingroup$ Are we talking about teaching big-picture ideas or teaching proven truth? (Ideally, both would be possible und compatible.) $\endgroup$
    – Raphael ♦
    Jan 20, 2014 at 16:16
1
$\begingroup$

I suppose what you mean by "substitution method" is guess & proof (by induction).

Be aware that you do perform an induction proof. By strengthening the induction hypothesis to all $n' < n$, the proof can go through -- if your parameters are naturals. That where you trip since $\frac{n}{2}$ is not always natural.

There are two ways for approaching this.

  • In the context of divide & conquer recurrences we usually solve the recurrence only for $n=2^k$ (that's how we get the form at hand); that should occur somewhere in the presentation/textbook. We do that because things become less messy to deal with, technically, and because we know that (under certain conditions¹) the result carries over.

  • Solve the original recurrence which probably has the form

    $\qquad T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + f(n)$.

    Many methods for solving recurrences become messy because of the rounding, but guess & proof should be fine.

  1. It's not trivial to see when and why we get the correct result by this method, but that's probably beyond your concern right now.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.