GATE CSE 2023 | Question: 5

Question

The Lucas sequence $L_{n}$ is defined by the recurrence relation:
\[
L_{n}=L_{n-1}+L_{n-2}, \quad \text { for } \quad n \geq 3,
\]
with $L_{1}=1$ and $L_{2}=3$.

Which one of the options given is TRUE?

• A. $L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\left(\frac{1-\sqrt{5}}{2}\right)^{n}$
• B. $L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{3}\right)^{n}$
• C. $L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\left(\frac{1-\sqrt{5}}{3}\right)^{n}$
• D. $L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}$

Comments

can you please reupload with a clearer picture? cant decipher remaining half. Thanks for the help !

---

@mk_007 we can extend the given sequence in the backward direction. Please check here 

@mikasa_ackermann is it okay now ?

You can also verify the solution programmatically using sympy module in Python:

 

 

---

yeah fine @ankitgupta.1729 thanks

Answer 1

By using $n=1,$ options can be eliminated easily and there are methods like solving linear homogeneous recurrence

by making characteristic equation, generating function etc. 

As answer is added here by converting $L_n-L_{n-1}-L_{n-2}=0$ to characteristic equation $r^2-r-1=0$

by assuming solution $L_n=cr^n; c>0$

But the question is “why” we assume so ?  

So, we can use an approach of Linear Algebra and prove that our assumption is correct because it is difficult to assume

something while solving this question first time because we might find difficulty to assume it without having any reason.

So,this method is long but answer your question of $\textbf{"Why ?"}$

Here, we have given a difference equation of order two as $L_n = L_{n-1}+L_{n-2} \ \ ; n\geq 3$

The idea is, we will make the system of two simultaneous difference equations of order one from this linear difference equation

of order 2 and then write it in the matrix form and solve this system.

Assume, $L_{n-2}=M_{n-1}$ or $M_n = L_{n-1}$ 

And this way, we have a system of two difference equations of order one as :

$$L_n = L_{n-1}+ M_{n-1} \ \ \ \ (1)$$
$$M_n = L_{n-1} + 0M_{n-1}\ \ \ \ (2)$$

Now, if we write this system in the matrix form as:

$\begin{pmatrix}
L_n  \\
M_n
\end{pmatrix} = \begin{pmatrix}
1 & 1  \\
1 & 0
\end{pmatrix}\begin{pmatrix}
L_{n-1}  \\
M_{n-1}
\end{pmatrix}$

Now, we replace $\begin{pmatrix}
L_{n-1}  \\
M_{n-1}
\end{pmatrix}$ by $\begin{pmatrix}
1 & 1  \\
1 & 0
\end{pmatrix}\begin{pmatrix}
L_{n-2}  \\
M_{n-2}
\end{pmatrix}$

So, $\begin{pmatrix}
L_n  \\
M_n
\end{pmatrix} = \begin{pmatrix}
1 & 1  \\
1 & 0
\end{pmatrix}^2\begin{pmatrix}
L_{n-2}  \\
M_{n-2}
\end{pmatrix}$

In this way, we get,

$\begin{pmatrix}
L_n  \\
M_n
\end{pmatrix} = \begin{pmatrix}
1 & 1  \\
1 & 0
\end{pmatrix}^{n-2}\begin{pmatrix}
L_{2}  \\
M_{2}
\end{pmatrix}$

Hence,

$\begin{pmatrix}
L_n  \\
M_n
\end{pmatrix} = \begin{pmatrix}
1 & 1  \\
1 & 0
\end{pmatrix}^{n-2}\begin{pmatrix}
3  \\
1
\end{pmatrix} \ \ \ \ \ (3)$

Now, say, $A=\begin{pmatrix}
1 & 1  \\
1 & 0
\end{pmatrix}$

Now, to find $A^{n-2},$ we need to find $A^n$ and for that we can use the idea of Cayley-Hamilton theorem.

($A^n$ can be computed with the use of Diagonalization concept by finding eigenvalues and eigenvectors for the matrix $A.$)

Suppose, $\lambda$ is an eigenvalue for the matrix $A.$ So characteristic equation will be:

$\det (A \ - \ \lambda I) = 0$

So, characteristic equation will be:

$\lambda^2 \  - \lambda  \ - \ 1 = 0$

This is the same characteristic equation which we got while solving linear homogeneous recurrence and

so, you can say, this is a proof for making that characteristic equation for linear homogeneous recurrence with

constant coefficient  without assuming solution of the recurrence

in the form of $c\lambda^n$ or $\lambda^n$.

Now, According to the Cayley-Hamilton theorem, every square matrix $A$ satisfies its characteristic equation and so,

$A^2 - A - I = 0$

$A^2 = A+I$

$A^3= A^2 + A = 2A + I$

$A^4 = 2A^2 + A = 3A+2I$

Hence, you can write $A^n = aA + bI$ for some arbitrary constant $a$ and $b.$

Hence, 

$\lambda_1^n = a\lambda_1 + b$ and 

$\lambda_2^n = a\lambda_2 + b$

So, $a= \dfrac{\lambda_1^n - \lambda_2^n}{\lambda_1-\lambda_2}$ and 

$b = \lambda_1^n - a\lambda_1$

Since, $\lambda^2 \  - \lambda  \ - \ 1 = 0$ gives

$\lambda_1 = \dfrac{1+\sqrt{5}}{2}$ and $\lambda_2 = \dfrac{1-\sqrt{5}}{2}$ 

So, we get,

$a = \dfrac{1}{\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2}\right)^n - \dfrac{1}{\sqrt{5}}\left(\dfrac{1-\sqrt{5}}{2}\right)^n$

$b = \dfrac{\sqrt{5}-1}{2\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2}\right)^n - \dfrac{\sqrt{5}+1}{2\sqrt{5}}\left(\dfrac{1-\sqrt{5}}{2}\right)^n$

Now, put $a$ and $b$ in $A^n = aA+bI,$ we get:

$A^n = \begin{pmatrix}
\dfrac{\sqrt{5}+1}{2\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2}\right)^n + \dfrac{\sqrt{5}-1}{2\sqrt{5}}\left(\dfrac{1-\sqrt{5}}{2}\right)^n &  \dfrac{1}{\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2}\right)^n - \dfrac{1}{\sqrt{5}}\left(\dfrac{1-\sqrt{5}}{2}\right)^n \\
... & ...
\end{pmatrix}$

And so,

$A^{n-2} = \begin{pmatrix}
\dfrac{2}{\sqrt{5}(\sqrt{5}+1)}\left(\dfrac{1+\sqrt{5}}{2}\right)^n + \dfrac{2}{\sqrt{5}(\sqrt{5}-1)}\left(\dfrac{1-\sqrt{5}}{2}\right)^n &  \dfrac{4}{\sqrt{5}(1+\sqrt{5})^2}\left(\dfrac{1+\sqrt{5}}{2}\right)^n - \dfrac{4}{\sqrt{5}(1-\sqrt{5})^2}\left(\dfrac{1-\sqrt{5}}{2}\right)^n \\
... & ...
\end{pmatrix}$

Now, finally, by $(3),$ we get:

$L_n = \dfrac{2\times 3}{\sqrt{5}(\sqrt{5}+1)}\left(\dfrac{1+\sqrt{5}}{2}\right)^n + \dfrac{2 \times 3}{\sqrt{5}(\sqrt{5}-1)}\left(\dfrac{1-\sqrt{5}}{2}\right)^n +  \dfrac{4}{\sqrt{5}(1+\sqrt{5})^2}\left(\dfrac{1+\sqrt{5}}{2}\right)^n - \dfrac{4}{\sqrt{5}(1-\sqrt{5})^2}\left(\dfrac{1-\sqrt{5}}{2}\right)^n$

After solving it, we get,

$L_n = \left(\dfrac{1+\sqrt{5}}{2}\right)^n + \left(\dfrac{1-\sqrt{5}}{2}\right)^n$

 

Comments

$L_n=\frac{x(x+1)^2}{\left(\left(\frac{\sqrt{5}-1}{2}\right)-x\right)\left(\left(\frac{\sqrt{5}+1}{2}\right)+x\right)}$

$\therefore L_n=-x(x+1)^2\left(x+\left(\frac{1+\sqrt{5}}{2}\right)\right)^{-1}\left(x+\left(\frac{1-\sqrt{5}}{2}\right)\right)^{-1}$

@ankitgupta.1729 sir after finding closed form I'm stuck here, we have to find coefficient of $x^n$, but in closed form there are infinite combinations are possible such that  we'll get $x^n$.

 

 

---

@parth023 your generating function seems incorrect. Can you please explain how did you get it ?

I have added answer here. So, in case if it is not correct or you are stuck somewhere then you can check it. 

---

understood my mistake sir.

Answer 2

---

Proof of how to derive this has been given in above answer but in exam we can save the time by just putting the initial condition and eliminate options.

As given L1 = 1

• A. 1 + √5 + 1 - √5   => 1 + √ 5 + 1 - √5 => 2/2 = 1 = Ans

             2            2                      2

       B)  1 + √5 – (1 - √5)   => 3 + 3√5 -2 + 2√5  => (1 + 5√5)/2  ≠ 1 hence wrong

                  2         3                             6

 

       C)  1 + √5 + (1 - √5)   => 3 + 3√5 +2 - 2√5  => (5 + √5)/2  ≠ 1 hence wrong

                 2        3                             6

         D) 1 + √5 – ( 1 - √5)   => 1 + √5 - 1 + √5  => (2 *√5)/2 => √5 ≠ 1 = hence wrong

                 2            2                        2

 

 

 

 

Answer 3

Since, $L_1=1$ and $L_2=3,$ So, $L_0=L_2-L_1=3-1=2$

Hence, the sequence $\{L_n\}_{n\geq0}$ is $<L_0,L_1,L_2,...>=$ $<2,1,3,4,7,11,18,...>$ 

So, Generating Function corresponding to sequence $\{L_n\}_{n\geq0}$ is:

$G(x)=2+x+3x^2+4x^3+7x^4+11x^5+18x^6+...$                     $(1)$

Now, multiply by $x$ both sides and writing right hand side by leaving one place

$xG(x)=\;\;\;\;2x+x^2+3x^3+4x^4+7x^5\;+\;11x^6+18x^7+...$      $(2)$

Now, add $(1)$ and $(2)$ vertically

 $(1+x)G(x)= 2+3x+4x^2+7x^3+11x^4+18x^5+29x^6+...$

Multiply again by $x$ both sides

$x(1+x)G(x)= 2x+\underbrace{3x^2+4x^3+7x^4+11x^5+18x^6+29x^7+...}_{G(x)-2-x}$

$x(1+x)G(x)= 2x+G(x)-2-x$

$$G(x)=\dfrac{2-x}{1-x-x^2}=\dfrac{2}{1-x-x^2}-\dfrac{x}{1-x-x^2}$$

Now, as it is mentioned here that coefficient of $x^n$ in $\dfrac{1}{1-x-x^2}$ is $\frac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1} -\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right]$

Hence,

$[x^n]\dfrac{1}{1-x-x^2}=\frac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1} -\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right]$

$[x^n]\dfrac{2}{1-x-x^2}=\frac{2}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1} -\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right]$

Similarly,

$[x^n]\dfrac{x}{1-x-x^2}=[x^{n-1}]\dfrac{1}{1-x-x^2}=\frac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n} -\left(\dfrac{1-\sqrt{5}}{2}\right)^{n}\right]$

So,

$[x^n]G(x)=[x^n]\dfrac{2}{1-x-x^2} -[x^n]\dfrac{x}{1-x-x^2}$

$[x^n]G(x)= \frac{2}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1} -\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right] – \frac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n} -\left(\dfrac{1-\sqrt{5}}{2}\right)^{n}\right]$

After simplification, we get

$[x^n]G(x)=\left(\dfrac{1+\sqrt{5}}{2}\right)^{n} +\left(\dfrac{1-\sqrt{5}}{2}\right)^{n}$

Answer 4

$\underline{\textbf{Given}}$

$T_1 = 1; \ T_2 = 3; \ T_n = T_{n-1} + T_{n-2} \text{ for } (n \ge 3)$

---

$\underline{\textbf{Observations}}$

$$\begin{align}
\begin{pmatrix}T_n \\ T_{n-1}\end{pmatrix} &= \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix} T_{n-1}\\ T_{n-2}\end{pmatrix} \\ 
&= \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}\begin{pmatrix} T_{n-2}\\ T_{n-3}\end{pmatrix} \\ 
&= \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^{n-2}\begin{pmatrix} T_{n-(n-2)}\\ T_{n-1-(n-2)}\end{pmatrix} = \underbrace{\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^{n-2}}_{A^{n-2}}\underbrace{\begin{pmatrix} 3 \\ 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-2}$ 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-2}F = P \Lambda^{n-2}P^{-1}F}$ 

Eigen values of $A$ are $\boxed{\lambda_1 = \frac{1+\sqrt{5}}{2}, \ \lambda_2 = \frac{1-\sqrt{5}}{2}}$

so $\Lambda = \begin{pmatrix}\lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}$. $e_1 = \begin{pmatrix}\lambda_1 \\ 1 \end{pmatrix}$ and $e_2 = \begin{pmatrix}\lambda_2 \\ 1 \end{pmatrix}$, so $P = \begin{pmatrix}\lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix}$ and $P^{-1} = \frac{1}{\lambda_1-\lambda_2}\begin{pmatrix}1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix}$ 

$$\begin{align}
A^{n-2}F &= \begin{pmatrix}\lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} ^{n-2} \frac{1}{\lambda_1-\lambda_2}\begin{pmatrix}1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \begin{pmatrix} 3 \\ 1\end{pmatrix} \\ 
&=  \frac{1}{\lambda_1-\lambda_2}\begin{pmatrix}\lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}\lambda_1^{n-2} & 0 \\ 0 & \lambda_2^{n-2} \end{pmatrix} \begin{pmatrix}1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \begin{pmatrix} 3 \\ 1\end{pmatrix} \\ 
&= \frac{1}{\lambda_1-\lambda_2}\begin{pmatrix}\lambda_1^{n-1} & \lambda_2^{n-1} \\ \lambda_1^{n-2} & \lambda_2^{n-2}  \end{pmatrix} \begin{pmatrix} 3-\lambda_2 \\ -3+\lambda_1\end{pmatrix} \\ 
&= \cancel{\sqrt{5}} \frac{1}{\cancel{\sqrt{5}}} \begin{pmatrix}\lambda_1^{n-1} & \lambda_2^{n-1} \\ \lambda_1^{n-2} & \lambda_2^{n-2}  \end{pmatrix} \begin{pmatrix} \lambda_1 \\ \lambda_2\end{pmatrix} \\ 
A^{n-2}F &=  \begin{pmatrix}\lambda_1^{n} + \lambda_2^{n} \\ \lambda_1^{n-1} + \lambda_2^{n-1}  \end{pmatrix}
\end{align}$$   

---

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

$\begin{pmatrix}T_n \\ T_{n-1}\end{pmatrix} = A^{n-2}F  = \begin{pmatrix}\lambda_1^{n} + \lambda_2^{n} \\ \lambda_1^{n-1} + \lambda_2^{n-1}  \end{pmatrix} \implies T_n = \lambda_1^{n} + \lambda_2^{n}$. 

Hence $\boxed{T_n = \Big(\frac{1+\sqrt{5}}{2}\Big)^n + \Big(\frac{1-\sqrt{5}}{2}\Big)^n}$

  

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