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:
- 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$?
- 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.
- Are there any issues with my attempted proof? Don't hold back, I would appreciate some formal criticism.
Best Answer
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.