2
$\begingroup$

I have some questions about Strong Induction where the inductive procedure isn't entirely clear to me. I will use a specific example to demonstrate and present my attempt at a proof with questions following.

Suppose we have a recurrence relation $T(n)$ defined as follows \begin{align*} T(0) &= 0 \\ T(n) &= T\left(\left\lfloor n/3\right\rfloor\right) + T\left(\left\lfloor n/5\right\rfloor\right) + T\left(\left\lfloor n/7\right\rfloor\right) + n, \enspace n > 0 \end{align*}

Use Strong Induction to prove that $T(n) \in O(n)$.


Proof:

$\underline{\text{Base Case}}$: By definition of BigOh, we want to show that $\exists c > 0 \enspace \text{s.t.} \enspace T(n) \le cn, \enspace \forall n \ge n_0$. Since $T(0) = 0$, this holds for any choice of $c$ with $n=0$ and $n_0 = 0$.

$\underline{\text{Inductive Hypothesis (I.H.)}}$: Suppose there exists such a $c$ for all $0 \le n < k$.

$\underline{\text{Inductive Step}}$: We need to show that $T(n) \in O(n)$ for $n = k$.

Since $\lfloor k/3 \rfloor,\lfloor k/5 \rfloor,\lfloor k/7 \rfloor < k$, it follows by the I.H. that $T(\lfloor k/3 \rfloor) \le ck/3$, $T(\lfloor k/5 \rfloor) \le ck/5$, and $T(\lfloor k/7 \rfloor) \le ck/7$.

Then using the definition of $T(n)$ we can say that \begin{align*} T(k) &\le \frac{ck}{3} + \frac{ck}{5} + \frac{ck}{7} + k\\ &\le ck\left(\frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{c}\right) \end{align*} To prove that $T(n) \in O(n)$ for $n=k$, we need to show that this quantity is less than $ck$ as follows \begin{align*} ck\left(\frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{c}\right) &\le ck \\ \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{c} &\le 1 \\ \frac{71}{105} + \frac{1}{c} &\le 1 \\ \frac{1}{c} &\le \frac{34}{105} \\ c &\le \frac{105}{34} \end{align*}

So for any $c \ge 105/34$, $T(n) \in O(n)$ for $n = k$, and thus $T(n) \in O(n)$.


Questions:

  1. What is the particular reason that strong induction is necessary for this proof? Is it because $T(n)$ is defined in terms of three previous recursive instances with floor functions that don't follow the same $+1$ ordering as the natural numbers? Or does it relate to proving asymptotic complexity where a claim $P(n)$ involves $\forall n \ge n_0$ for each $n$?
  2. Is my base case sufficient? Since BigOh typically applies to asymptotic limits, I have trouble understanding how to prove BigOh for a base case when $n$ takes on a specific value.
  3. Are there any issues with my attempted proof? Don't hold back, I would appreciate some formal criticism.
$\endgroup$
2
  • 1
    $\begingroup$ I understand that the last inequality is with $\ge$, isn't it? $\endgroup$
    – ajotatxe
    Jul 19 '15 at 18:56
  • $\begingroup$ @ajotatxe, yes, sorry for the confusion. I am not (intentionally) asserting that the steps I used to find c ≤ 105/34 prove that c ≥ 105/34. I'm using the value I found as a choice of c that works for the BigOh notation, and so anything greater should also work. $\endgroup$ Jul 19 '15 at 20:20
1
$\begingroup$

Strong induction is necessary for this proof because weak induction isn't enough to solve the problem. Specifically, weak induction looks at $T(n-1)$, but you need to plug different values into $T$, so you need to assume the claim is true for more cases.

The base case is enough, you showed that $T(0)\leq c\cdot 0$.

Your attempted proof is backwards (it's more like scratch work). In your "proof," you found that $c\geq\frac{105}{34}$ (YOU FORGOT TO FLIP THE INEQUALITY). Your work helped you to figure out what $c$ should be. Now, you have to go back and start with an appropriate $c$ value and prove that that particular value for $c$ works. (You could round $c$ up to the nearest integer).

Therefore, start the entire proof over using $c=\frac{105}{34}$ (or any integer greater than this quotient) and prove that for the base case $T(0)\leq c\cdot 0$. Also, prove that $T(n)\leq cn$ by doing your work in the opposite direction.

$\endgroup$
3
  • $\begingroup$ Can you elaborate on your first point? Specifically, can you address the ordering difference between weak induction with T(n-1) vs. strong induction with T(n/3) + T(n/3) + T(n/7)? Can you also address if it matters that the claim to prove involves a range of values for n greater than a minimum n0 for each choice of n? $\endgroup$ Jul 19 '15 at 19:57
  • $\begingroup$ The difference in the types of induction are in the assumptions. Weak induction assumes the truth of one smaller case, while strong induction assumes the truth of all smaller cases. $\endgroup$ Jul 19 '15 at 20:58
  • $\begingroup$ When you invert fractions, the inequality reverses. For example, $2\leq 3$, but $\frac12\geq\frac13$. Take $2\leq3$, and divide through by $2\cdot 3$. $\endgroup$ Jul 19 '15 at 20:59
1
$\begingroup$

The "danger" in this exercise is in writing the proof in such a way that $c$ depends on $n$. But you haven't done this. I think that it is ok.

But to make things clearer, you can stablish from the beginning a value for $c$, say $c=4$. Your original work is useful as a draft, to find this $c$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.