GATE CS 2023 Q5 — Combinatorics: Counting, Recurrence Relations, Generating Functions

The recurrence relation is given by $L_n = L_{n-1} + L_{n-2}$ for $n \geq 3$ with $L_1 = 1$ and $L_2 = 3$.

The characteristic equation of this recurrence relation is:

The roots of this equation are:

The general solution is of the form $L_n = c_1 r_1^n + c_2 r_2^n$. We can find the correct option by testing the base cases $n=1$ and $n=2$ for Option A:

• For $n=1$: $$L_1 = \left(\frac{1+\sqrt{5}}{2}\right)^1 + \left(\frac{1-\sqrt{5}}{2}\right)^1 = \frac{1+\sqrt{5} + 1-\sqrt{5}}{2} = 1$$
• For $n=2$: $$L_2 = \left(\frac{1+\sqrt{5}}{2}\right)^2 + \left(\frac{1-\sqrt{5}}{2}\right)^2 = \frac{6+2\sqrt{5}}{4} + \frac{6-2\sqrt{5}}{4} = \frac{12}{4} = 3$$

Since both initial conditions are satisfied, Option A is the correct closed-form expression.