The GATE Grind

GATE 2023 CS – Question 15

Engineering Mathematics · Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) · 1 mark · Multiple choice

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

  1. $L_n = \left(\frac{1+\sqrt5}{2}\right)^n + \left(\frac{1-\sqrt5}{2}\right)^n$
  2. $L_n = \left(\frac{1+\sqrt5}{2}\right)^n - \left(\frac{1-\sqrt5}{3}\right)^n$
  3. $L_n = \left(\frac{1+\sqrt5}{2}\right)^n + \left(\frac{1-\sqrt5}{3}\right)^n$
  4. $L_n = \left(\frac{1+\sqrt5}{2}\right)^n - \left(\frac{1-\sqrt5}{2}\right)^n$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $L_n = \left(\frac{1+\sqrt5}{2}\right)^n + \left(\frac{1-\sqrt5}{2}\right)^n$

Explanation

The characteristic roots are φ and ψ = (1±√5)/2. With L_n = φ^n + ψ^n, L_1 = φ+ψ = 1 and L_2 = φ²+ψ² = 3, matching the given values.