edited by
7,798 views
7 votes
7 votes

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?

  1. $L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\left(\frac{1-\sqrt{5}}{2}\right)^{n}$
  2. $L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{3}\right)^{n}$
  3. $L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\left(\frac{1-\sqrt{5}}{3}\right)^{n}$
  4. $L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}$
edited by

4 Answers

8 votes
8 votes

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$

 

edited by
4 votes
4 votes

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

  1. 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

 

 

 

 

2 votes
2 votes

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

1 votes
1 votes

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

Answer:

Related questions

14 votes
14 votes
3 answers
4
admin asked Feb 15, 2023
6,538 views
Which one of the following sequences when stored in an array at locations $A , \ldots, A[10]$ forms a max-heap?$23,17,10,6,13,14,1,5,7,12$$23,17,14,7,13,10,1,5,6,12$$23,1...