The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2,…

A linear recurrence with constant coefficients, such as xn = xn−1 + xn−2, has a closed-form (Binet-type) solution built from the roots of its characteristic equation r2 = r + 1. If the roots are φ and ψ, the general solution has the form xn = A·φn + B·ψn, where the constants A and B are fixed by the given initial values.

1. Characteristic equation: r2 = r + 1, i.e., r2 − r − 1 = 0.

2. Solve the quadratic: r = (1 ± √5)/2. Call φ = (1 + √5)/2 and ψ = (1 − √5)/2.

3. General solution: Ln = A·φn + B·ψn.

4. Apply n = 1 (using L1 = 1): A·φ + B·ψ = 1.

5. Apply n = 2 (using L2 = 3): A·φ2 + B·ψ2 = 3.

6. Use the identities φ + ψ = 1 and φ·ψ = −1 (from the quadratic's coefficients): φ2 + ψ2 = (φ + ψ)2 − 2·φ·ψ = 1 − 2·(−1) = 3.

7. Since A = 1 and B = 1 satisfy both the n = 1 equation (φ + ψ = 1) and the n = 2 equation (φ2 + ψ2 = 3) simultaneously, the closed form is Ln = φn + ψn.

Independently check with n = 3: the recurrence gives L3 = L2 + L1 = 3 + 1 = 4. Using φ + ψ = 1 and φ·ψ = −1, φ3 + ψ3 = (φ + ψ)3 − 3·φ·ψ·(φ + ψ) = 1 − 3·(−1)·(1) = 4, which matches L3, confirming the closed form independently of the initial derivation.

Therefore Ln = ((1 + √5)/2)n + ((1 − √5)/2)n.