The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln-1 + Ln-2, for n 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE? A) Ln = ( 1 + 52 )n + ( 1 - 52 )n B) Ln = ( 1 + 52 )n - ( 1 - 53 )n C) Ln = ( 1 + 52 )n + ( 1 - 53 )n D) Ln = ( 1 + 52 )n - ( 1 - 52 )n

Official answer: A) Ln = ( 1 + 52 )n + ( 1 - 52 )n. Explanation: The recurrence relation is given by: Ln - Ln-1 - Ln-2 = 0 The characteristic equation is: r2 - r - 1 = 0 Solving for the roots r using the quadratic formula: r = 1 1 - 4(1)(-1)2 = 1 52 Let = 1+ 52 and = 1- 52. The general solution to the recurrence relation is: Ln = c1 n + c2 n We can find the constants c1 and c2 using the initial conditions L1 = 1 and L2 = 3: 1. For n = 1: c1 ( 1+ 52 ) + c2 ( 1- 52 ) = 1 (c1 + c2) + 5(c1 - c2) = 2 2. For n = 2: c1 ( 1+ 52 )2 + c2 ( 1- 52 )2 = 3 Since 2 = 3+ 52 and 2 = 3- 52: c1 ( 3+ 52 ) + c2 ( 3- 52 ) = 3 3(c1 + c2) + 5(c1 - c2) = 6 Subtracting the first equation from the second equation: 2(c1 + c2) = 4 c1 + c2 = 2 Substituting c1 + c2 = 2 back into the first equation: 2 + 5(c1 - c2) = 2 5(c1 - c2) = 0 c1 = c2 Since c1 + c2 = 2 and c1 = c2, we obtain c1 = 1 and c2 = 1. Therefore, the closed-form expression is: Ln = ( 1+ 52 )n + ( 1- 52 )n This matches option A.

A) Ln = ( 1 + 52 )n + ( 1 - 52 )n

B) Ln = ( 1 + 52 )n - ( 1 - 53 )n

C) Ln = ( 1 + 52 )n + ( 1 - 53 )n

D) Ln = ( 1 + 52 )n - ( 1 - 52 )n

Engineering Mathematics · Recurrence Relations

Official IIT answer key · IIT Kanpur · Audited Aug 2026

Take topic test

GATE CSE 2023 Q15 · MCQ · 1 mark

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?

Select an option to check

Key concept

Recurrence Relations

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Recurrence Relations

In GATE CS, Recurrence Relations under Engineering Mathematics is tested as a concise 1-mark topic focused on linear homogeneous recurrence relations of degree 2. Questions either require setting up a recurrence relation from a combinatorial constraint (e.g., restricted binary strings) or solving a second-order linear recurrence relation using characteristic roots to find either an explicit closed-form formula or its asymptotic tight bound ( ). All provided PYQs are conceptual, analytical 1-mark multiple-choice questions without diagrams.

Full Recurrence Relations guide →

More on Recurrence Relations

All 4 questions on Recurrence Relations →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Engineering Mathematics · Recurrence Relations

Official IIT answer key · IIT Kanpur · Audited Aug 2026

Take topic test

GATE CSE 2023 Q15 · MCQ · 1 mark

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?

Select an option to check

Key concept

Recurrence Relations

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Recurrence Relations

Full Recurrence Relations guide →

More on Recurrence Relations

All 4 questions on Recurrence Relations →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

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?

Step-by-step verified solution

Check you can still solve Recurrence Relations under a clock

More from GATE CSE 2023

More on Recurrence Relations

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?

Step-by-step verified solution

Check you can still solve Recurrence Relations under a clock

More from GATE CSE 2023

More on Recurrence Relations

The Lucas sequence LnL_nLn​ is defined by the recurrence relation: Ln=Ln−1+Ln−2,for n≥3,L_n = L_{n-1} + L_{n-2}, \quad \text{for } n \ge 3,Ln​=Ln−1​+Ln−2​,for n≥3, with L1=1L_1 = 1L1​=1 and L2=3L_2 = 3L2​=3. Which one of the options given is TRUE?

Step-by-step verified solution

Check you can still solve Recurrence Relations under a clock

More from GATE CSE 2023

More on Recurrence Relations

Share this solution

The Lucas sequence LnL_nLn​ is defined by the recurrence relation: Ln=Ln−1+Ln−2,for n≥3,L_n = L_{n-1} + L_{n-2}, \quad \text{for } n \ge 3,Ln​=Ln−1​+Ln−2​,for n≥3, with L1=1L_1 = 1L1​=1 and L2=3L_2 = 3L2​=3. Which one of the options given is TRUE?

Step-by-step verified solution

Check you can still solve Recurrence Relations under a clock

More from GATE CSE 2023

More on Recurrence Relations

Share this solution

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?

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?