How do I show T(n) = 2T(n-1) + k is O(2^n)?
In this case, your best bet is to just solve the recurrence by direct substitution.

$$\begin{align*}
T(n) &amp;= 2T(n-1) + k \\
     &amp;= 2\big(2T(n-2) + k\big) + k \\
     &amp;= 2\big(2\big(2T(n-3) + k\big) + k\big) + k\\
     &amp;= \cdots\\
     &amp;= 2^rT(n-r) + k\sum_{i=0}^{r-1} 2^i\\
     &amp;= 2^rT(n-r) + k(2^r-1)\,.
\end{align*}$$

Putting $r=n$ gives
$$\begin{align*}
T(n) &amp;= 2^nT(0) + k(2^n-1) \\
     &amp;= 2^n(T(0) + k) - k \\
     &amp;= O(2^n)
\end{align*}$$
since, although you forgot to define $T(0)$, it is a constant and so is&nbsp;$k$.