GATE 2023 CS Q.15: solution and answer

GATE 2023 · CSQ.15 · 1 mark · MCQ

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

Which one of the options given is TRUE?

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option A: $L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n}$ .

Official answer: ASource: Official answer key, GATE 2023 CS (IIT Kanpur)

The characteristic equation of $L_{n} = L_{n - 1} + L_{n - 2}$ is $x^{2} = x + 1$ , that is $x^{2} - x - 1 = 0$ .
Its roots are $φ = \frac{1 + 5}{2}$ and $ψ = \frac{1 - 5}{2}$ , with $φ + ψ = 1$ and $φ ψ = - 1$ . These are distinct, so the general solution is $L_{n} = a φ^{n} + b ψ^{n}$ .
Options B and C contain $\frac{1 - 5}{3}$ , which is not a root of $x^{2} - x - 1 = 0$ . These expressions do not satisfy the recurrence, so B and C are false.
The initial values require $a φ + b ψ = 1$ and $a φ^{2} + b ψ^{2} = 3$ . Because $φ \neq = ψ$ , this linear system has exactly one solution $(a, b)$ .
Try $a = b = 1$ (option A). First, $L_{1} = φ + ψ = 1$ , which matches.
Next, $L_{2} = φ^{2} + ψ^{2} = (φ + ψ)^{2} - 2 φ ψ = 1 + 2 = 3$ , which matches. Since the solution is unique, $a = b = 1$ and $L_{n} = φ^{n} + ψ^{n}$ .
Check option D, which has $a = 1$ , $b = - 1$ : $L_{1} = φ - ψ = 5 \neq = 1$ , so D fails.
As a further check, $L_{3} = L_{2} + L_{1} = 4$ , and $φ^{3} + ψ^{3} = (φ + ψ)^{3} - 3 φ ψ (φ + ψ) = 1 + 3 = 4$ . The answer is option A.

KEY IDEA

Solve the linear recurrence through its characteristic roots $φ, ψ$ , then fit the two initial values. Because the roots are distinct, the fit is unique, so a candidate that satisfies both initial values is the answer.

WATCH OUT FOR

Picking D because it looks like the familiar Fibonacci (Binet) formula. That has a minus sign and a $5$ in the denominator. For Lucas numbers the two terms are simply added with coefficients 1 and 1. Options B and C can be dismissed at once because their second base is not a root.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 3 Recurrences questions, with notes

GATE 2023 CS Q.15: solution and answer

Answer and solution

More Recurrences questions