recurrence relation for coefficients
A power-series or Frobenius solution has infinitely many unknown coefficients a_0, a_1, a_2, and so on — far too many to solve all at once. The recurrence relation for coefficients is the formula that links them: it expresses each coefficient in terms of one or more earlier ones, so that once you fix the first one or two, all the rest tumble out by repeated application. It is the engine that turns a differential equation into an arithmetic crank.
It arises directly from substitution. When you plug y = sum a_k x^k (or the Frobenius form) into the equation and collect everything multiplying a common power x^k, the demand that this coefficient vanish gives an algebraic relation among the a's, for example a_{k+2} = -a_k/((k+2)(k+1)) for y'' + y = 0, or a two-term relation like a_{k+1} = c_k a_k for many special-function equations. A relation that connects a_{k+2} to a_k (a 'two-step' recurrence) splits the solution into an even series and an odd series; one that connects consecutive coefficients (a 'one-step' relation) builds a single chain. You start from the free constants and crank forward.
The recurrence is where the deep structure of the special functions hides. For Legendre's, Hermite's and Laguerre's equations the recurrence has a magic property: for special parameter values the relation makes some a_k exactly zero, and from then on every later coefficient is zero too — the infinite series truncates into a polynomial. That truncation is precisely the origin of the Legendre, Hermite, Laguerre and Chebyshev polynomials, and (in quantum mechanics) of energy quantization, since the requirement that the series terminate to stay finite forces the parameter to take discrete values.
Hermite's equation y'' - 2x y' + 2 lambda y = 0 yields a_{k+2} = 2(k - lambda)/((k+2)(k+1)) a_k. If lambda equals a non-negative integer n, then a_{n+2} = 0 and the whole even-or-odd chain above n dies, leaving a polynomial of degree n — the Hermite polynomial. For any other lambda the series runs forever and grows too fast to be physically admissible.
The recurrence terminating is the mechanism behind both polynomial solutions and quantization.
Do not confuse this with the recurrence relations between the named polynomials themselves (such as the three-term relation linking P_{n+1}, P_n, P_{n-1}). The coefficient recurrence is inside one series; the polynomial recurrence is between whole functions of different degree.