Dark Mode

1,338 views

4 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?

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

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

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 Linear Algebra.}$

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.

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