1

$T(0) = 1, T(1) = 0$

I ain't able to get answer from any of the methods.

Substitution:

$T(n) = x^n $

\begin{align} & x^n = x^{n-1} + 2x^{n-2} + 2 \\ & x^2 = x + 2 + 2x^2\\ & x^2 + x + 2 =0 \end{align}

solving this I will get a complex root.

\begin{align} x & = \frac{-1 \pm \sqrt{1-8}}{2} x & = \frac{-1 \pm 7i}{2} \end{align}

Now how to go further.

General:

\begin{align} T(2) & = 4\\ T(3) & = 6\\ T(4) & = 16\\ T(5) & = 30\\ T(6) & = 64\\ T(7) & = 126\\ T(8) & = 256 \end{align}

From this i can deduce if $n$ is even then $2^n$. I cant deduce for if $n$ is odd.

Michael Hardy
  • 1
Pygirl
  • 199
  • When you divide both sides of your first line by $x^{n-2}$ you get $$x^2+2+\frac{2}{x^{n-2}}.$$ So, what went wrong? – user539887 Jun 24 '18 at 10:16
  • I don't know how to solve for complex root – Pygirl Jun 24 '18 at 10:17
  • 1
    Solve the homogeneous recurrence $T_n=T_{n-1}+2T_{n-2}$ first. – Angina Seng Jun 24 '18 at 10:19
  • @user539887 sorry , I didn't notice it's is not linear equation. I don't know how to solve it further. If i am right then there is some set of conditions depending on the equation. I studied the concept 2 years back now have no idea how to do such questions. – Pygirl Jun 24 '18 at 10:19
  • @LordSharktheUnknown: what about non homeogeneous part ? There are some set of conditions right depending on the root. If you can provide me some reference i would be able to solve this. – Pygirl Jun 24 '18 at 10:21
  • It is a linear nonhomogeneous recurrence equation. – user539887 Jun 24 '18 at 10:21
  • Okay when would it be non linear then .T(n) = T(n/2) is it linear or non linear ? – Pygirl Jun 24 '18 at 10:21
  • 1
    $T(n)=T(n/2)$ is not a recurrence relation (in the usually sense of the word). An example of a nonlinear recurrence relation is $T(n)=(T(n-1))^2$. – user539887 Jun 24 '18 at 10:26

3 Answers3

4

Put $U(n) - 1 = T(n)$ and the equation is $$ U(n+2) = U(n-1) + 2U(n) $$ let as you do $U(n) = x^n$ and we get $$ x^{n+2} = x^{n-1}+2x^n $$ or we need to solve $$ x^2-x-2 = 0 $$

hence $$ x = \frac{1}{2} \pm \sqrt{1/4+8/4} = \frac{1 \pm 3}{2} $$

So $$ U(n) = A 2^n + B (-1)^n $$ and $$ T(n) = A 2^n + B (-1)^n - 1 $$ So $$ T(0) = A+B-1 = 1 $$ and $$ T(1) = 2A-B -1 = 0 $$ gives $$ A = 1, \,B=1 $$ And we conclude $$ T(n) = 2^n+(-1)^n-1 $$

Stefan
  • 889
3

Hint try to make it homogeneous, from $$T(n) = T(n-1) + 2T(n-2) + 2$$ $$T(n+1) = T(n) + 2T(n-1) + 2$$ we have $$T(n)-T(n+1)=T(n-1) + 2T(n-2) - T(n) - 2T(n-1) \iff \\ T(n+1)-2T(n)-T(n-1)+2T(n-2)=0$$ leading to characteristic polynomial $$x^3-2x^2-x+2=0 \iff (x-2)(x-1)(x+1)=0$$

rtybase
  • 16,907
1

Another way to solve the problem: note that you have

$$ \begin{bmatrix} a_{n+1}\\ a_n \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 2 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a_{n}\\ a_{n-1} \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 2 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^n \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} $$

tomasz
  • 35,474
  • how did u get that matrix? – Pygirl Jun 24 '18 at 14:53
  • 1
    @KritiSahu: From the recursive definition. $a_{n+1}=a_n+2\cdot a_{n-1}+2\cdot 1$, $a_n=a_n+0\cdot a_{n-1}+0\cdot 1$ and $1=0\cdot a_n+0\cdot a_{n-1}+1\cdot 1$. – tomasz Jun 24 '18 at 17:25