The Lucas sequence L_n is defined by the recurrence relation: L_n = L_n-1 + L_n-2, for n ≥ 3, with L_1 = 1 and L_2 = 3. Which one of the options given is TRUE?

L_n = ≤ft(1+52)^n + ≤ft(1-52)^n

L_n = ≤ft(1+52)^n - ≤ft(1-53)^n

L_n = ≤ft(1+52)^n + ≤ft(1-53)^n

L_n = ≤ft(1+52)^n - ≤ft(1-52)^n

GATE CSE 2023 Q15: Closed form of the Lucas sequence with L1 = 1, L2 = 3

The Lucas sequence $L_n$ is defined by the recurrence relation:

$L_n = L_{n-1} + L_{n-2}, \quad \text{for } n \ge 3,$

with $L_1 = 1$ and $L_2 = 3$ .

Which one of the options given is TRUE?

Try it: multiple choice: exactly one correct option

Wrong answer costs 1/3 mark in GATE.

Show answer and explanation

Answer: A (official GATE 2023 final answer key)

Concept used: Linear recurrences: the solution is a combination of powers of the roots of $x^2 = x + 1$ .

First step: Check each option at $n = 1$ and $n = 2$ ; the two roots $\frac{1 \pm \sqrt{5}}{2}$ sum to 1.

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key