Divide et impera recurrence, why induction does not work?

Question

$$ T(n) = T\left(\frac n2\right) + 2^n $$

where $n \ge 1$ and $T(1) = 1$. If I understand the substitution method and the induction, I can guess that $T(n) = O(2^n)$.

I must prove that $T(n) = O(2^n)$, meaning constants $c$ and $n_0$ exist such that $T(n) \le c2^n$ for all $n \ge n_0$.

Base case

When $n = 1$ then $T(1) = 1$, choosing $c \ge \frac 12$ the inequality is satisfied:

$$ \\ 1 \le c2\\ $$

Inductive step

Hypothesis is that $T(k) = O(2^k)$ for all $k \lt n$ (hence $T\left(\frac n2\right) \le c2^{\frac n2}$). Then I show that is true for $n$:

$$ \begin{align} T(n) &= T\left(\frac n2\right) + 2^n = c2^{\frac n2} + 2^n = (c2^{\frac 12} + 1)2^n \\ &= (c\sqrt 2 +1)2^n \le c2^n \end{align} $$

So I ended up with $c \ge c\sqrt 2 +1$ that has no solution! I know that $T(n) = \Theta(2^n)$, so I'm wrong and I'd like to understand why.

Answer 1

It's just a minor mistake. The RHS of the line $$ T(n) = T\left(\frac n2\right) + 2^n = c2^{\frac n2} + 2^n = \color{red}{(c2^{\frac 12} + 1)2^n} $$ is wrong. $c2^{\frac n2}\neq(c2^{\frac 12})2^n=c2^{n+\frac12}$. The correct simplification is $c2^{\frac n2} + 2^n=\color{green}{2^{n/2}(c+2^{n/2})}$. You want this to be $\le 2^nc$. Therefore you need $c+2^{n/2}\le2^{n/2}c$ for all $n>1$. So you may pick $c=2$.

Answer 2

Suppose that for large $k$ and $k<n$, $T(k) = O(2^k)$ and that then $T(k)\leq c\cdot 2^k$

$$T(n) = T(\frac{n}{2})+2^n \leq 2^n\cdot(1+c\cdot 2^{-\frac{n}{2}})$$

which implies that for large $n$,$$T(n) \leq 2^n\cdot 1$$

But this reasoning looks completely false... And I don't know why.

Answer 3

From the definition, $T(2) = T(1)+2^2 = 5$, $T(3) = T(1)+2^3 = 9$, and $T(4) = T(2)+2^4 = 21$. So, for $1 \le n \le 4$, $T(n) < 2\cdot 2^n$.

Suppose $n > 4$ and $T(m) < c 2^m$ for $n/2 \le m < n$. Then, as before, $T(n) = T(n/2)+2^n < c 2^{n/2}+2^n = 2^n(1+c 2^{-n/2}) < c 2^n $ if $1+c 2^{-n/2} < c$ or $1 < c(1-2^{-n/2})$ or $c > 1/(1-2^{-n/2})$. Since $n > 4$, $2^{-n/2} < 2^{-2} = 1/4$, so this inequality becomes $c > 1/(1-1/4) = 4/3$. This is certainly true for $c = 2$, so we can substitute this value of $c$ in the original argument like this, and disguise how we came up with the value for $c$:

Suppose $n > 4$ and $T(m) < 2 \cdot 2^m$ for $n/2 \le m < n$. Then, as before, $T(n) = T(n/2)+2^n < 2\cdot 2^{n/2}+2^n = 2^n(1+2 \cdot 2^{-n/2}) < 2^n (1+2\cdot 2^{-2}) < (3/2) 2^n < 2 \cdot 2^n $.

This type of analysis is, in my experience, common. Some calculations are done which results in getting a value that allows an induction (or other) argument to succeed. Then the initial analysis is thrown away, and the magic constant is used to prove the result without any hint of how the constant was arrived at.