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 ?

---

What if $\alpha+\beta = 4$ and $\alpha-\beta = \frac{-2}{\sqrt{5}} \;\;?$  

It also satisfies $(\alpha+\beta)\frac{1}{2} +(\alpha-\beta)\frac{\sqrt{5}}{2}=1$

You can't find two constants $\alpha$ and $\beta$ by only one equation here. You need to use two values of $n$ here.