5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Well, I can easily determine a closed form for T(n) as T(n) = 2^(n-1) * T(1) + (2^(n-1) - 1)k. But I'm more concerned about the inductive proof. Do you know how I could incorporate that into an inductive proof? $\endgroup$ – Trent Bing Dec 11 '13 at 22:23
  • $\begingroup$ Oh, could I simply prove the closed form inductively, and then show in a single step that the closed form is clearly O(2^n)? $\endgroup$ – Trent Bing Dec 11 '13 at 22:25
  • $\begingroup$ @Intredasting, yes, exactly! 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)$. $\endgroup$ – D.W. Dec 11 '13 at 22:51
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nitpicking: $\dots$ is not a formal proof, an induction is still necessary. It's a good way to generate guesses, though. $\endgroup$ – Raphael Dec 12 '13 at 9:28
  • $\begingroup$ "$\dots$" is quite formal enough for almost any situation, though the literal dots would normally be omitted. In a research paper, such a thing would be written as something like "Thus, it is easy to see that $T(n)=2^r T(n-r) + k(2^r-1)$ so $T(n)=2^n(T(0)+k)-k$." Setting up a formal induction would be unnecessarily labouring the point though it's necessary for more complicated recurrences. $\endgroup$ – David Richerby Dec 12 '13 at 9:35
  • 1
    $\begingroup$ I don't think the practices in TCS research papers should inform the level of detail in teaching. The face that experts communicate like this does not mean that it's a formal proof, and it does also not mean that beginners will understand and learn from it. (Also, there are many, many stories of similar sentences being blatantly wrong because some people don't seem to bother to check their statements rigorously before putting shortened versions in space-restricted papers. But that's a discussion for Academia.) $\endgroup$ – Raphael Dec 12 '13 at 9:42
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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*}

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.