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,\quad T(1)=2,\quad T(n)=5T(n-1)-6T(n-2)
\]Assume \(T(n)=r^n\). Then
\[
r^2-5r+6=0
\]

\[
(r-2)(r-3)=0 \Rightarrow r=2,3
\]

General solution:
\[
T(n)=A\cdot2^n+B\cdot3^n
\]From \(T(0)=1\)
\[
A+B=1   
\]From \(T(1)=2\)
\[
2A+3B=2
\]
On Solving A+B=1 & 2A+2B=2
We get  \(A=1,\;B=0\)

\[
\boxed{T(n)=2^n}
\]

$So$ $Ans.$ $is$ \[
\boxed{T(n)=\Theta(2^n)}
\]
Reference: recrel.pdf

---

nice approach

---

Nice reference

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.

Comments

I agree with your answer.
But your statement:

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

I think it is not necessary for them to satisfy always,
Can anyone please explain/prove/disprove this? 

---

@Devarapalli Vamsi 13 Yes you are right. The options only state the "asymptotic bounds" and not the actual values of the recurrence relation. Note that the asymptotic bound only cares about the value of the recurrence for large values of 'n'. For example consider this recurrence:

T(0) = 8

T(1) = 2

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

Above recurrence is theta(n) even if the base cases don't satisfy theta(n) relation.

---

Removed the wrong content.

Answer 2

$\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}$ 

Comments

Beautiful:)

---

beautiful approach. i don't think AI will be able to come up with this type of solution on its own.

---

Wow, this is amazing

---

Unnecessary complication final boss

Answer 3

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.

Comments

NICELY EXPLAINED SIR

Answer 4

Ans Is (A)

by puting n=0

B and D got elliminated  T(0)=1;

then 

by putting n=1 option c got elliminated because dont satisfyT(1)=2 and

only option remaining is A

 

Comments

it is wrong explanation i treated asymtotic expression as absolute
here is explanation https://gemini.google.com/share/1649e2e28a53

 

---

Great observation @Nilexh

---

😂🤣😂🤣

Answer 5

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.

Comments

Good question to keep in mind, was thinking option C is correct option as characteristic roots were 2 and 3. Was not expecting coefficient of $3^n$ to vanish like that!

Answer 6

So, Roughly solving

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

Considering values of n => {2, 3, 4, .....} (According to the given condition n>=2)

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

As, this follow pattern 2^n

Hence, Option (A) is correct.

Comments

nice