GATE CSE 2023 | Memory Based Question: 15 [closed]

Answer 1

The given recurrence relation is $L_n = L_{n-1} + L_{n-2}$

$\therefore L_n - L_{n-1} - L_{n-2} = 0$

Therefore, the characteristic equation is $r^2 - r -1 = 0$

Solving for $r$ gives $r_1 = \frac{1+\sqrt5}{2}, r_2 = \frac{1-\sqrt5}{2}$

Therefore, the general solution is of the form $L_n = \alpha(r_1)^n + \beta(r_2)^n$

$\therefore L_n = \alpha(\frac{1+\sqrt5}{2})^n + \beta(\frac{1-\sqrt5}{2})^n$

Now, given $L_1 = 1$

$\therefore L_1 = 1 = \alpha(\frac{1+\sqrt5}{2}) + \beta(\frac{1-\sqrt5}{2}) = (\alpha + \beta) \frac{1}{2} + (\alpha - \beta) \frac{\sqrt5}{2}$

$\therefore \alpha + \beta = 2 \text{ and } \alpha - \beta = 0$

$\therefore \alpha = 1, \beta = 1$

$\therefore L_n = (\frac{1+\sqrt5}{2})^n + (\frac{1-\sqrt5}{2})^n$

Answer :- D.

Comments

Though you can easily eliminate options by $n=1$ and this is also a famous recurrence but it is good to see that you have solved it but could you please answer my two questions ?

$1)$ Can you prove that the characteristic equation is $r^2-r-1=0$ without assuming that solution of the recurrence in the form of $cr^n$ or $r^n \ ?$

$2)$ Why do you think that solution of this recurrence is unique ?

Answer 2

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. 

But Like last year I have written this answer which used limits to solve a  question related to generating function.

Now, I will solve the given recurrence $\textbf{using matrices.}$

It is always fun to solve questions by different methods,

it gives you reason to know how things are related in mathematics which makes the mathematics beautiful.

We can use this method to solve differential equations also.

This method also gives the proof of characteristic equation which mostly people use while solving linear homogeneous recurrence

with constant coefficient by assuming solution $r^n$ or $cr^n$ but the problem is:

Why we assume so ?  

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.

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$