GATE CSE 2024 | Set 2 | Question: 5

Question

​​​​​Let $\text{T(n)}$ be the recurrence relation defined as follows:

\[
\begin{array}{l}
T(0)=1, \\
T(1)=2, \text { and } \\
T(n)=5 T(n-1)-6 T(n-2) \text { for } n \geq 2
\end{array}
\]

Which one of the following statements is TRUE?

• A. $T(n)=\Theta\left(2^{n}\right)$
• B. $T(n)=\Theta\left(n 2^{n}\right)$
• C. $T(n)=\Theta\left(3^{n}\right)$
• D. $T(n)=\Theta\left(n 3^{n}\right)$

Comments

• $T(0)=1=2^0$
• $T(1)=2=2^1$
• $T(2)=5T(1)-6T(0)=5*2-6*1=4=2^2$
• $T(3)=5T(2)-6T(1)=5*4-6*2=8=2^3$
• $T(4)=5T(3)-6T(2)=5*8-6*4=16=2^4$
• $T(5)=5T(4)-6T(3)=5*16-6*8=32=2^5$...so on

$\therefore T(n)=\theta(2^n)$, Option $(A)$ is correct.

Answer 1

I believe Correct answer will be (A).

Given , $T(n)=5T(n-1)-6T(n-2)$ ; $n \geq2$

            $T(0)=1$

            $T(1)=2$

            Calculate ,$T(2)=5*T(1)-6*T(0)=5*2-6*1=4=2^{2}$

                             $T(3)=5*T(2)-6*T(1)=5*4-2=8=2^{3}$

                              $T(4)=5*T(3)-6*T(2)=5*2^{3}-6*2^{2}=2^4$

so we can see the trend it is for $n \geq 2$ is $2^{n}$ .

Let's try to proof this formally using mathematical Induction ,

Assumption is $T(n)=2^{n}$

Base case :

For n=0 , $T(0)=2^{0}=1$ and n=0 , $T(1)=2^{1}=2$ .

So it is true for base cases.

Let us assume it is true for $n \leq k$ .

So , $T(k)=2^{k}$.

Now we have to show it is true for k+1 as well .

$T(k+1)=5*T(k)-6*T(k-1)$

$T(k+1)=5*2^k-6*2^{k-1}$

$T(k+1)=2^{k-1}(5*2-6*1)$

$T(k+1)=2^{k-1}*4=2^{k+1}$

So we proof our assumption $T(n)=2^{k}$ is true using mathematical induction .

[** Other options does not even satisfy the Base case so straight away can be eliminated by option test**]

Answer 2

NOTE that $T(n) = 2^n $ satisfies the given recurrence relation. So, $T(n) = 2^n$ is the EXACT value of the function $T(n).$ Hence, $T(n) = \Theta(2^n).$ See HERE.

Answer 3

$\underline{\textbf{Given}}$

$T_0 = 1; \ T_1 = 2; \ T_n = 5T_{n-1} - 6T_{n-2} \text{ for } (n \ge 2)$

---

$\underline{\textbf{Observations}}$

$$\begin{align}
\begin{pmatrix}T_n \\ T_{n-1}\end{pmatrix} &= \begin{pmatrix}5 & -6 \\ 1 & 0\end{pmatrix}\begin{pmatrix} T_{n-1}\\ T_{n-2}\end{pmatrix} \\ 
&= \begin{pmatrix}5 & -6 \\ 1 & 0\end{pmatrix}\begin{pmatrix}5 & -6 \\ 1 & 0\end{pmatrix}\begin{pmatrix} T_{n-2}\\ T_{n-3}\end{pmatrix} \\ 
&= \begin{pmatrix}5 & -6 \\ 1 & 0\end{pmatrix}^{n-1}\begin{pmatrix} T_{n-(n-1)}\\ T_{n-1-(n-1)}\end{pmatrix} = \underbrace{\begin{pmatrix}5 & -6 \\ 1 & 0\end{pmatrix}^{n-1}}_{A^{n-1}}\underbrace{\begin{pmatrix} 2 \\ 1\end{pmatrix}}_{F} \\ 
\end{align}$$  

$A$ is invertible $2\times 2$ matrix. Hence, we can use the power of diagonalization to solve for $A^{n-1}$ neatly. 

---

$\underline{\textbf{Diagonalization}}$

$\Lambda = P^{-1}AP$ or $A = P\Lambda P^{-1}$, where $\Lambda$ is $2\times 2$ diagonal matrix and $\Lambda_{i,i} = \lambda_i$, here $\lambda_i$ is eigen value of $A$. $P$ is $2\times 2$ invertible matrix such that $P = \begin{pmatrix}e_1 & e_2 \end{pmatrix}$, where $e_i$ is eigenvector corresponding to $\lambda_i$. Hence, using diagonalization we can represent any matrix in terms of its eigenvalues and eigenvectors. 

$A^m = \underbrace{(P\Lambda P^{-1})(P\Lambda P^{-1})\dots(P\Lambda P^{-1})}_{m \text{ times}} = P\Lambda^m P^{-1} \implies \boxed{A^{n-1}F = P \Lambda^{n-1}P^{-1}F}$ 

Eigen values of $A$ are $\lambda_1 = 3$, $\lambda_2 = 2$, so $\Lambda = \begin{pmatrix}3 & 0 \\ 0 & 2 \end{pmatrix}$. $e_1 = \begin{pmatrix}3 \\ 1 \end{pmatrix}$ and $e_2 = \begin{pmatrix}2 \\ 1 \end{pmatrix}$, so $P = \begin{pmatrix}3 & 2 \\ 1 & 1 \end{pmatrix}$ and $P^{-1} = \begin{pmatrix}1 & -2 \\ -1 & 3 \end{pmatrix}$ 

$$\begin{align}
A^{n-1}F &= \begin{pmatrix}3 & 2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}3 & 0 \\ 0 & 2 \end{pmatrix} ^{n-1} \begin{pmatrix}1 & -2 \\ -1 & 3 \end{pmatrix} \begin{pmatrix} 2 \\ 1\end{pmatrix} \\ 
&= \begin{pmatrix}3 & 2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}3^{n-1} & 0 \\ 0 & 2^{n-1} \end{pmatrix}  \begin{pmatrix}1 & -2 \\ -1 & 3 \end{pmatrix} \begin{pmatrix} 2 \\ 1\end{pmatrix} \\ 
&= \begin{pmatrix}3^{n} & 2^{n} \\ 3^{n-1} & 2^{n-1}  \end{pmatrix} \begin{pmatrix} 0 \\ 1\end{pmatrix} \\ 
A^{n-1}F  &= \begin{pmatrix} 2^n \\ 2^{n-1} \end{pmatrix} \\
\end{align}$$  

---

$\underline{\textbf{Final Solution}}$

$\begin{pmatrix}T_n \\ T_{n-1}\end{pmatrix} = A^{n-1}F  = \begin{pmatrix} 2^n \\ 2^{n-1} \end{pmatrix} \implies T_n = 2^n$. Hence $\boxed{T_n = \Theta(2^n)}$. 

$\textbf{Option (A) is correct}$ 

Answer 4

We can use the characteristic root method to solve this recurrence relation:

Given T(n) = 5T(n-1) - 6T(n-2) n >=2

T(0) = 1 and T(1) = 2

We can write it as: 

a_n = 5a_n-1 - 6a_n-2  n >= 2

a₀ = 1 and a₁ = 2

Now solving the recurrence relation:

a_n - 5a_n-1 + 6a_n-2 = 0

We can also write the relation as follows by shifting n to n+2:

a_n+2 - 5a_n+1 + 6a_n = 0

Using the shift operator we get the characteristic eqn.,

E²(a_n) - 5E(a_n) + 6a_n = 0

a_n(E² - 5E + 6) = 0

Finding the characteristic roots of above eqn. we will get roots as 3 and 2 [(t-3)(t-2) = 0]

As the roots are real and distinct, the complimentary function will be c₁.(3)ⁿ + c₂.(2)ⁿ

Hence, a_n = c₁.(3)ⁿ + c₂.(2)ⁿ

Put n = 0, a₀ = c₁ + c₂ = 1

Put n = 1, a₁ = 3c₁ + 2c₂ = 2

Solving both eqn, we get c₁ = 0 and c₂ = 1

Therefore, a_n = 0.(3)ⁿ + 1.(2)ⁿ = 2ⁿ

Hence the exact answer will be T(n) = 2ⁿ. Option (A) is correct.