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? A. L_n = ((1 + sqrt(5))/2)^n - ((1 - sqrt(5))/2)^n B. L_n = ((1 + sqrt(5))/2)^n + ((1 - sqrt(5))/2)^n C. L_n = F_n + F_{n+2} where F_n is the standard Fibonacci number (F_1=F_2=1) D. L_n = F_n + 2*F_{n-1} where F_0 = 0, F_1 = 1

GATE 2023 · Discrete Mathematics · Recurrence Relation · medium

Answer: L_n = phi^n + psi^n = ((1+sqrt(5))/2)^n + ((1-sqrt(5))/2)^n. Option B is TRUE.

1. Write the general solution: Characteristic equation: r^2 - r - 1 = 0, roots phi = (1+sqrt(5))/2 and psi = (1-sqrt(5))/2. General solution: L_n = A*phi^n + B*psi^n.
2. Determine constants using L_1=1 and L_2=3: Equation 1: A*phi + B*psi = 1. Equation 2: A*phi^2 + B*psi^2 = 3. Using phi^2 = phi+1 and psi^2 = psi+1: A*(phi+1) + B*(psi+1) = 3 => (A*phi + B*psi) + (A+B) = 3 => 1 + (A+B) = 3 => A+B = 2. Also A*phi + B*psi = 1 and phi + psi = 1: subtracting phi*(A+B) gives B*(psi-phi) = 1 - 2*phi. Since psi - phi = -sqrt(5) and 1-2*phi = -sqrt(5): B = 1. Similarly A = 1.
3. Verify and eliminate wrong options: Option A uses subtraction (phi^n - psi^n): that gives sqrt(5)*F_n (Fibonacci times sqrt(5)), which gives L_1 = sqrt(5) ≠ 1. FALSE. Option B: phi^1 + psi^1 = phi + psi = 1 = L_1; phi^2 + psi^2 = phi^2+psi^2 = (phi+psi)^2 - 2*phi*psi = 1 - 2*(-1) = 3 = L_2. TRUE.