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

Question

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) <= 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) <= c * 2. Since c = T(1), our equation becomes T(1) <= 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
    >= 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?

Answer 1

You are right. We can't show that $c \times 2^n + k \le c \times 2^n$. It doesn't matter how you choose $c$; you are doomed. So, this approach is a failure. You will need to find a different way to prove it.

This sometimes happens. Don't get discouraged. Often you'll need to try a couple different proof strategies before you find one that works. Back to the drawing board!

Here is what I suggest. To simplify your life, first pick a particular value of $k$: say, $k=1$, so your recurrence is $T(n) = 2 T(n-1) + 1$. Now, try writing out a table of the first 10 values of the recurrence, i.e., $T(1), $T(2), $T(3), \ldots$ Does that give you any clues or ideas about what you can say about $T(n)$? Do you spot a pattern?

---

This is a common strategy: look at small examples to see if you can spot a pattern, hypothesize a relationship (e.g., your closed form), then formally prove the relationship using proof by induction. If you read in a textbook, they might only show you the last step (the proof by induction) with no hint of where they got the relationship from in the first place, but now that you're doing it yourself, you get to learn how to do it for real. Once you've proved by induction that $T(n)=...$ (your expression), it is easy to prove in one step that this is $O(2^n)$.

This is also an instance of a common pattern when using proof by induction. The hardest step in proof by induction is figuring out what to prove: figuring out what the inductive predicate is. In your case, instead of trying to prove $T(n) \le 2^n$, you will fare better by proving something more specific: proving that $T(n) = 2^{n-1} T(1) + (2^{n-1}-1)k$. This is sometimes known under the name "strengthening the invariant". Here the invariant that we are trying to prove is $T(n) = 2^{n-1} T(1) + (2^{n-1}-1)k$. This is a "stronger" statement than $T(n) \le 2^n$ (it is more specific, it gives us more information, it narrows down the possible values of $T(n)$ further). Counter-intuitively, in this case, proving something more specific actually turns out to be easy. Sometimes induction is surprising!

Answer 2

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$.

Answer 3

Here is another idea, which works for the more general recurrence $T(n) = T(n-1) + k(n)$. Let $S(n) = T(n)/2^n$. Then $S(1) = 1/2$ and $$ S(n) = \frac{T(n)}{2^n} = \frac{2T(n-1)}{2^n} + \frac{k(n)}{2^n} = S(n-1) + \frac{k(n)}{2^n}. $$ If the series $\sum_{n=1}^\infty \frac{k(n)}{2^n}$ converges then we deduce that $S(n) = \Theta(1)$ and so $T(n) = \Theta(2^n)$. This is certainly the case in your example since $\sum_{n=1}^\infty \frac{1}{2^n}$ converges, and you get similar results even for $k(n) = c^n$ for any $c < 2$, for $k(n) = 2^n/n^t$ for all $t > 1$, and so on.

Answer 4

By characteristic roots

$$ \begin{align*} t_n - 2t_{n-1} &= k\\ t_{n-1} - 2t_{n-2} &= k \end{align*} $$

Subtract:

$$ t_n - 3t_{n-1}+ 2t_{n-2} = 0$$

Characteristic equation is:

$$ x^2 - 3x + 2 = 0 $$

Roots are: $$ \begin{align*} x &= 1\\ x &= 2 \end{align*} $$

so the general solution is:

$$ t_n = C_1 1^n + C_2 2^n $$

or

$$ t_n = O(2^n) $$

By generating functions

You get homogeneous recurrence in the same way.

Now,

$t_n = 3t_{n-1}-2t_{n-2}$

\begin{eqnarray*} G(x) &=& \sum\limits_{i=0}^\infty t_ix^i \\ &=& t_0 + t_1x + \sum_{i=2}^\infty (3t_{i-1}-2t_{n-1})x^i \\ &=& a_0 + t_1x + 3x\sum_{i=0}^\infty t_ix^i - 2k\sum_{i=0}^\infty t_ix^i \\ &=& t_0+ t_1x + 3xG(x)-2x^2G(x) \end{eqnarray*}

Now,

\begin{eqnarray*} G(x) &=& \frac{t_0+t_1x}{2x^2-3x+1} \\ &=& \frac{A}{1-x} + \frac{B}{1-2x} \end{eqnarray*}

As we know, \begin{equation*} \sum_{i=0}^\infty \alpha^i x^i = \frac{1}{1-\alpha x} \end{equation*} so \begin{equation*} \frac{1}{1-x} = 1 x + x^2 + \ldots \end{equation*} and \begin{equation*} \frac{1}{1-2x} = 1 +2x + 4x^2+ \ldots \end{equation*} Now,

\begin{equation*} G(x) = \sum_{i=0}^n (A\cdot 1+B\cdot 2^i)x^i, \end{equation*} so

\begin{equation*} t_n = A + B\cdot 2^n = O(2^n). \end{equation*}

Answer 5

Let $S(n) = T(n) + k$. Then $$ S(n) = T(n) + k = 2T(n-1) + 2k = 2S(n-1). $$ Therefore $S(n) = 2^n S(0)$, and so $$ T(n) = S(n) - k = 2^n S(0) - k = 2^n (k + T(0)) - k. $$