Consider a family of polynomials $\{P_0, P_1, P_2, \cdots\}$ where each $P_n$ has degree $n$. The polynomials are orthogonal if there is an inner product such that $(P_i, P_j) = 0$ if and only if $i\neq j$. Now, any given $P_{n+1}$ can be written in terms of all the lower-degree polynomials:
$$\displaystyle P_{n+1} = r_{n+1,n+1}xP_n + \sum_{k=0}^n r_{n+1,k} P_k $$
but if the $P_j$ are orthogonal then most of the coefficients are zero because each $P_j$ is orthogonal to all polynomials of lesser degree, in particular to the $P_k$ with lesser degree (i.e. $k < j$). See:
$$\displaystyle 0 \neq (P_{n+1}, P_{n+1}) = r_{n+1,n+1}(xP_n, P_{n+1}) + 0 $$
$$\displaystyle 0 = (P_{n+1}, P_n) = r_{n+1,n+1}(xP_n, P_n) + r_{n+1,n}(P_n, P_n) + 0 $$
$$\displaystyle 0 = (P_{n+1}, P_{n-1}) = r_{n+1,n+1}(xP_n, P_{n-1}) + r_{n+1,n-1}(P_{n-1}, P_{n-1}) $$
$$\displaystyle 0 = (P_{n+1}, P_{n-2}) = r_{n+1,n+1}(xP_n, P_{n-2}) + r_{n+1,n-2}(P_{n-2}, P_{n-2}) $$
The first term on the right-hand side of this last line is zero because $(xP_n, P_{n-2}) = (P_n, xP_{n-2})$ and $xP_{n-2}$ is a polynomial of degree $n-1$, so its inner product with $P_n$ is zero. By the same reasoning, most of the $r_{i,j}$ are zero and after some rearrangement we end up with:
$$\displaystyle c_nP_{n+1} = (x-a_n)P_n – b_n P_{n-1} $$
This equation is known as the “three-term recurrence relation”. Once the expressions for $a_n$, $b_n$, and $c_n$ are known, plus the first two polynomials $P_0$ and $P_1$, all higher-degree orthogonal polynomials in the family can be very efficiently obtained using this recurrence. The specific values of those coefficients depend on the nature of the inner product. In the rest of this post, we’ll derive them for three sets of orthogonal polynomials which happen to all be named after Frenchmen.
Laguerre Polynomials
The Laguerre polynomials are defined by the inner product
$$\displaystyle (f, g) = \int_0^\infty e^{-x} fg\,dx $$
with the first two polynomials being $P_0 = 1$ and $P_1 = x-1$. The orthogonality condition alone is not enough to uniquely define the $P_n$, because multiplying any $P_n$ by a nonzero constant does not affect the orthogonality property. To make the derivation easier, we will insist that the $P_n$ also be monic meaning that the leading coefficient of each $P_n$ is $1$. This condition immediately implies that $c_n = 1$ for all $n$, so the coefficients $a_n$ and $b_n$ which we want to find will be given by:
$$\displaystyle \begin{aligned} a_n &= \frac{(xP_n, P_n)}{(P_n, P_n)} \\ b_n &= \frac{(P_n, xP_{n-1)}}{(P_{n-1}, P_{n-1})} \end{aligned}$$
Using integration by parts and the definition of the inner product, observe that:
$$\displaystyle \begin{aligned} (xP_n, P_n) &= \int_0^\infty -xe^{-x} P^2_n\,dx \\ &= -xe^{-x} P^2_n(x)\Bigg|^{\infty}_0 + \int_0^\infty e^{-x} (2xP_n P’_n + P^2_n)\,dx \\ &= 0 + 2(P_n, xP’_n) + (P_n, P_n) \end{aligned} $$
Since $P_n$ is monic, $xP’_n$ has leading coefficient $n$ and can therefore be written as $nP_n$ plus some $P_j$’s of lower degrees. So $(P_n, xP’_n) = (P_n, nP_n) = n(P_n, P_n)$ and we have
$$\displaystyle (x P_n, P_n) = (2n+1)(P_n, P_n) \Rightarrow a_n = 2n+1 $$
Now for the $b_n$. First observe that because the $P_n$ are monic, $(xP_n, P_{n-1}) = (P_n, xP_{n-1}) = (P_n, P_n)$. Therefore $b_n = (P_n, P_n)/(P_{n-1}, P_{n-1})$. Integration by parts allows us to rewrite $(P_n, P_n)$:
$$\displaystyle (P_n, P_n) = \int_0^\infty e^{-x}P^2_n\,dx = -e^{-x}P^2_n\Bigg|^\infty_0 + 2(P_n, P’_n) = P_n(0)^2 $$
So we can also write $b_n = P^2_n(0)/P^2_{n-1}(0)$, which we can plug back into the three-term recurrence evaluated at $x=0$ to obtain:
$$\displaystyle P_{n+1}(0) = -(2n+1)P_n(0) – \frac{P^2_n(0)}{P^2_{n-1}(0)}P_{n-1}(0) $$
Letting $r_n = P_{n}(0)/P_{n-1}(0)$, this can be simplified to $r_{n+1} = -(2n+1) – r_n$ with $r_1 = -1$ (since the two starting polynomials $P_0$ and $P_1$ are known). This has the solution $r_n = -n$, from which it follows that $b_n = n^2$ and we have our recurrence.
$$\displaystyle P_{n+1} = (x-(2n+1))P_n – n^2 P_{n-1} $$
The Laguerre polynomials are often given not as monic polynomials, but as polynomials with $P_n(0) = 1$ which in view of the fact that $(P_n, P_n) = P^2_n(0)$ are also orthonormal polynomials. Knowing that $P_0 = 1$ and $r_n = -n$, we find that $P_n(0) = (-1)^n n!$ and hence $P_n = (-1)^n n! \hat{P}_n$ where $\hat{P}_n$ is the degree-$n$ orthonormal Laguerre polynomial. Substituting this expression into the three-term recurrence for $P_n$ we obtain one for $\hat{P}_n$:
$$\displaystyle (-1)^{n+1}(n+1)!\hat{P}_{n+1} = (x-(2n+1))(-1)^n n! P_n – (-1)^{n-1} n^2 (n-1)!\hat{P}_{n-1} $$
Dividing through by $(-1)^{n+1} n!$ and simplifying, we get:
$$\displaystyle (n+1)\hat{P}_{n+1} = ((2n+1)-x)\hat{P}_n – n\hat{P}_{n-1} $$
Hermite Polynomials
The Hermite polynomials are defined by the inner product:
$$\displaystyle (f,g) = \int_{-\infty}^\infty \frac{e^{-x^2/2}}{\sqrt{2\pi}} fg\,dx $$
In other words, an integral weighted by the standard normal distribution. The starting polynomials are $P_0 = 1$ and $P_1 = x$. Unlike with the Laguerre polynomials, this inner product does not allow us to easily deduce $(P_n, P_n)$ from the definition, so to simplify matters we will seek the orthonormal Hermite polynomials first for which that quantity is just 1 and we don’t have to compute it. The three-term recurrence will then have the form:
$$\displaystyle c_n \hat{P}_{n+1} = (x-a_n)\hat{P}_n – b_n \hat{P}_{n-1} $$
which, in fact, can be simplified further. We see that
$$\displaystyle a_n = (x\hat{P}_n, \hat{P}_n) $$
which is zero if $\hat{P}_n$ is an even function or an odd function. But then if $\hat{P}_{n-1}$ is also even or odd, with the opposite parity of $\hat{P}_n$, then $\hat{P}_{n+1}$ will have the same parity as $\hat{P}_{n-1}$. Since the first two functions are $\hat{P}_0 = 1$ (even) and $\hat{P}_1 = x$ (odd), it follows that the $\hat{P}_n$ are all alternatingly even or odd and $a_n = 0$ for all $n$.
Furthermore, $c_n = (x\hat{P}_n, \hat{P}_{n+1})$. But $b_n = (x\hat{P}_n, \hat{P}_{n-1}) = c_{n-1}$. So the recurrence has the simpler form:
$$\displaystyle c_n \hat{P}_{n+1} = x\hat{P}_n – c_{n-1} \hat{P}_{n-1} $$
To find $c_n$, integrate by parts:
$$\displaystyle \begin{aligned} c_n &= s\int_{-\infty}^\infty xe^{-x^2/2} \hat{P}_n \hat{P}_{n+1} \\ &= -s\hat{P}_n\hat{P}_{n+1}e^{-x^2/2}\Bigg|_{-\infty}^\infty + (\hat{P}’_n, \hat{P}_{n+1}) + (\hat{P}_n, \hat{P}’_{n+1}) \\ &= 0 + 0 + (n+1)\frac{[LC]_{n+1}}{[LC]_n} \end{aligned}$$
where $[LC]_n$ denotes the leading coefficient of $\hat{P}_n$ and $s = (2\pi)^{-1/2}$. From the recurrence relation, we see that $\frac{[LC]_{n+1}}{[LC]_n} = \frac{1}{c_n}$ so we have
$$\displaystyle c_n = \frac{n+1}{c_n} \Rightarrow c_n = \sqrt{n+1} $$
The orthonormality condition defines $\hat{P}_n$ only up to a sign change, so without loss of generality we can take the positive square root here. So we got the recurrence relatively easily thanks to the convenient factor of $x$ appearing in the integral:
$$\displaystyle \sqrt{n+1}\hat{P}_{n+1} = xP_n – \sqrt{n}P_{n-1} $$
The Hermite polynomials are usually defined as monic, but we can get those from this definition since we know the leading coefficients. Since $\frac{[LC]_{n+1}}{[LC]_n} = \frac{1}{c_n} = \frac{1}{\sqrt{n+1}} $ and the leading coefficient of $P_0$ is just $1$, we have that:
$$\displaystyle [LC]_n = \frac{1}{\sqrt{n!}} \Rightarrow P_n = \sqrt{n!}\hat{P}_n $$
which when plugged into the recurrence we have gives the recurrence for the monic Hermite polynomials $P_n$:
$$\displaystyle \frac{\sqrt{n+1}}{\sqrt{(n+1)!}}P_{n+1} = \frac{x}{\sqrt{n!}}P_n – \frac{\sqrt{n}}{\sqrt{(n-1)!}} P_{n-1} $$
$$\displaystyle P_{n+1} = xP_n – nP_{n-1} $$
Legendre Polynomials
Now the inner product is:
$$\displaystyle (f,g) = \int_{-1}^1 \frac{1}{2} fg\,dx $$
with the first two polynomials being $P_0 = 1$ and $P_1=x$. Like for the Hermite polynomials, the weighting function in the integral is symmetric and the starting polynomials are respectively even and odd, so all the Legendre polynomials will be alternatingly even and odd. We will start by seeking the monic Legendre polynomials, since that lets us write the recurrence using only one unknown coefficient:
$$\displaystyle P_{n+1} = xP_n – b_n P_{n-1} $$
Like with the monic Laguerre polynomials, we have that:
$$\displaystyle b_n = \frac{(xP_n, P_{n-1})}{(P_{n-1}, P_{n-1})} = \frac{(P_n, P_n)}{(P_{n-1}, P_{n-1})} $$
We can obtain an expression for $(P_n, P_n)$ from the definition of the inner product, integrating by parts:
$$\displaystyle \begin{aligned} (P_n, P_n) &= \frac{1}{2}\int_{-1}^1 P_n^2\,dx \\ &= \frac{x}{2}P^2_n\Bigg|^1_{-1} – 2(P_n, xP’_n) \\ &= \frac{P^2_n(1) – P^2_n(-1)}{2} – 2n(P_n, P_n)\end{aligned}$$
Since $P_n$ is either even or odd, $P^2_n(1) = P^2_n(-1)$. We then have:
$$\displaystyle (P_n, P_n) = \frac{2P^2_n(1)}{2n+1} $$
From which we can write $b_n$ as:
$$\displaystyle b_n = \frac{2n-1}{2n+1}\frac{P^2_n(1)}{P^2_{n-1}(1)} $$
which we can plug into the recurrence evaluated at $x=1$:
$$\displaystyle P_{n+1}(1) = P_n(1) – \frac{2n-1}{2n+1}\frac{P^2_n(1)}{P^2_{n-1}(1)}P_{n-1}(1) $$
Dividing through by $P_n(1)$ and defining $r_n = P_n(1)/P_{n-1}(1)$:
$$\displaystyle r_{n+1} = 1 – \frac{2n-1}{2n+1}r_n $$
with the initial value $r_1 = 1$ since $P_1(1) = P_0(1) = 1$. This recurrence has the solution $r_n = \frac{n}{2n-1}$, from which it follows that:
$$\displaystyle P_n(1) = P_0(1)\prod_{k=1}^n r_k = \prod_{k=1}^n \frac{k}{2k-1} = \frac{n!}{\prod_{k=1}^n (2k-1)} $$
So we can write $b_n$ as:
$$\displaystyle \begin{aligned} b_n &= \frac{2n-1}{2n+1}\frac{P^2_n(1)}{P^2_{n-1}(1)} \\ &= \frac{2n-1}{2n+1} \left( \frac{n!}{(n-1)!}\frac{\prod_{k=1}^{n-1} (2k-1)}{\prod_{k=1}^n (2k-1)} \right)^2 \\ &= \frac{2n-1}{2n+1}\frac{n^2}{(2n-1)^2} \\ &= \frac{n^2}{(2n+1)(2n-1)} \end{aligned} $$
So the monic Legendre polynomials satisfy:
$$\displaystyle P_{n+1} = xP_n – \frac{n^2}{(2n+1)(2n-1)}P_{n-1} $$
They are usually defined, however, by $\bar{P}(1) = 1$, but since we know $P_n(1)$ we can convert easily between the two forms:
$$\displaystyle \bar{P}_n = \frac{P_n}{P_n(1)} = \frac{\prod_{k=1}^n (2k-1)}{n!} P_n $$
Rewriting the recurrence in terms of $\bar{P}_n$ and simplifying:
$$\displaystyle \frac{(n+1)!}{\prod_{k=1}^{n+1} (2k-1)} \bar{P}_{n+1} = x\frac{n!}{\prod_{k=1}^n (2k-1)}\bar{P}_n – \frac{n^2}{(2n+1)(2n-1)} \frac{(n-1)!}{\prod_{k=1}^{n-1} (2k-1)} \bar{P}_{n-1} $$
$$\displaystyle \frac{n+1}{2n+1}\bar{P}_{n+1} = x\bar{P}_n – \frac{n}{2n+1}\bar{P}_{n-1} $$