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) &lt;= c * 2^n" (for some fixed c, to be determined)

For now, let's fix c at T(1).

Base case: n = 1

We want to show T(1) &lt;= c * 2. Since c = T(1), our equation becomes T(1) &lt;= T(1) * 2, which is trivially true.

Inductive step: Assume P(n - 1) is true for n > 1. We want to show that P(n) holds.

T(n) = 2 T(n - 1) + k, by definition
    &gt;= 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 &lt;= 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) &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$.