How do I show T(n) = 2T(n-1) + k is O(2^n)?

This is a practice problem I've come up with in order to study for an exam I have in a couple of hours.

Again, here's the problem: Show T(n) = 2T(n-1) + k is O(2^n) where k is some positive constant.

First of all, 2^n is indeed the upperbound, right? Since I've made this problem up myself, I'm not 100% sure, but from what I have seen, this should be O(2^n).

If so, here's my progress:

We want to show P(n) is true for all n > n0, where P(n) is the statement "T(n) 1. We want to show that P(n) holds.

T(n) = 2 T(n - 1) + k, by definition
    >= 2 (c * 2^(n-1) ) + k = c * 2^n + k

Here's where I get stuck. How can we possibly show that c 2^n + k <= c 2^n for any value of c? Did I make a mistake somewhere?

In this case, your best bet is to just solve the recurrence by direct substitution.

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

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

StackExchange Computer Science Q#18900, answer score: 6