5

If $T(n)= T(n-1) + 2T(n-2)$ with $T(0)=0$ and $T(1) = 1$

What is $T(n)$ (in $Θ$–notation) in terms of $n$?

I am trying to solve by substitution, but I am not sure if I am doing this right, as I get stuck. Can anybody tell me where to go from here?

$T(n)= T(n-1) + 2T(n-2)$

$T(n-1)= T(n-2) + 2T(n-3)$

$T(n-2)= T(n-3) + 2T(n-4)$

$T(n)= T(n-k) + 2T(n-(k+1))$

Substitute $n$ for $k$

$T(n)= T(n-n) + 2T(n-(n+1))$

$T(n)= T(0) + 2T(1)$

I am not sure where to go from here to find $T(n)$ (in $Θ$–notation) in terms of $n$.

Ken
  • 3,751
User
  • 907

4 Answers4

6

Generating functions for the win. Let $T(x) = \sum_{n=0}^{\infty}T_nx^n = \sum_{n=1}^{\infty}T_nx^n$, since $T_0 = 0$.

Then: $$\begin{split} T(x) &= x + \sum_{n=2}^{\infty}T_nx^n \\ &= x + \sum_{n=2}^{\infty}(T_{n-1} + 2T_{n-2})x^n \\ &= x + \sum_{n=2}^{\infty}T_{n-1}x^n + \sum_{n=2}^{\infty}2T_{n-2}x^n \end{split}$$

Let's rewrite those sums. The first one:

$$\begin{split} \sum_{n=2}^{\infty}T_{n-1}x^n &= x\sum_{n=2}^{\infty}T_{n-1}x^{n-1} \\ &= x\sum_{n=1}^{\infty}T_nx^n \\ &= xT(x) \end{split}$$

Likewise, the second sum works out to $2x^2T(x)$. Thus:

$$T(x) = x + xT(x) + 2x^2T(x)$$

So:

$$\begin{split} T(x) &= \frac{x}{1 -x - 2x^2} = \frac{x}{(1-2x)(1+x)} \\ &= \frac{\frac{1}{3}}{1-2x} + \frac{-\frac{1}{3}}{1+x} \\ &= \frac13\sum_{n=0}^{\infty}2^nx^n - \frac13\sum_{n=0}^{\infty}(-1)^nx^n \\ &= \sum_{n=0}^{\infty}\left(\frac{2^n - (-1)^n}{3}\right)x^n \end{split}$$

Which gives us our recurrence: $T_n = \left(\frac{2^n - (-1)^n}{3}\right) = \Theta(2^n)$

Barry
  • 2,268
3
  1. $\Theta$-notation is?
  2. The difference equation provided is that which defines the Jacobsthal numbers.
  3. The general method to define the Jacobsthal numbers is as follows.

Let $T(n) = r^{n}$ in the difference equation $T_{n+2} = T_{n+1} + 2 T_{n}$ to obtain $r^{2} - r - 2 = 0$ which yields the solutions $2r = 1 \pm 3 \in \{4, -2\}$ and leads to the general form $$T_{n} = A \, 2^{n} + B (-1)^{n}$$. Using the values $T_{0} = 0$ and $T_{1} = 1$ then $$T_{n} = \frac{2^{n} - (-1)^{n}}{3}$$

Leucippus
  • 26,329
  • And from this, $T(n) = \Theta(2^n)$. But presumably the OP wants to get this asymptotic info without fully solving. – GEdgar Jun 07 '15 at 22:43
1

we have $$t_n = t_{n-1} + 2t_{n-2}, t_0 = 0, t_1 = 2.$$ here are the first few numbers in the sequence: $$0, 2, 2, 6, 10, \cdots. $$

it looks like you can establish $$t_n > 0 \text{ for all } n \ge 1$$ by induction. once we have that can we use $$t_n \ge 2t_{n-2} $$ to conclude that $t_n = O(2^n)$ without solving the recurrence relation?

abel
  • 29,170
  • this is similar to my proof/my proof is correct? below. i think this establishes both upper and lower bounds and therefore Θ. – miniparser Jun 08 '15 at 15:38
0

i thought $2^n$ at first from similarity to Fibonacci #s.

from there it is just 2 trivial inductions to find for what $g(n)$ is $T(n)\in Θ(g(n)),$ because $T(n)\in Θ(g(n))$ when $T(n)\in O(g(n))$ and $T(n)\in$ (big omega)$(g(n))$, if i am not mistaken. And $T(n)\in O(g(n))$ when for some $c\in N,n_0\in Z$, $T(n)\le cg(n),n\ge n_0$. $T(n)\in $ (big omega)$(g(n))$ when for some $c\in N,n_0\in Z$, $T(n)\ge cg(n),n\ge n_0$.

$c=1,n_0=1$: base case: $T(1)=1\le 2^1$. Assume $T(n)\le (1)(2^n)$, $n\ge 1$. $T(n+1)=T(n)+2T(n-1)\le 2^n+2(2^{n-1})=2^n+2^n=2(2^n)=2^{n+1}$. so it holds by induction. similar proof for lower bound/big omega.

if i am not mistaken $2^n\Leftrightarrow log_2n$. $log_2n$ is the inverse of $2^n$ as $2^n$ is one-to-one.

edit: this part is incorrect: so is also $Θ(log_n)$.

miniparser
  • 1,197