Divide et impera recurrence, why induction does not work? $$
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.

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.
