Recurrence relations · Differential Equations

Intuition

The recurrence is the whole solution in compressed form. Unwound, it gives a formula for every coefficient, and from that formula two things can be read: whether the series stops, which makes the solution a polynomial, and how far from the starting point the series converges. The ratio of consecutive coefficients answers the second question, just as the ratio test does in the analysis course.

A family tree. Knowing how each generation follows from the one before, you can trace any descendant back to the founders without drawing the whole tree.

plot diagram: how-fast-the-coefficients-shrink

The coefficients $a_{n}$ against $n$ . Those of $e^{x}$ , $\tfrac{1}{n!}$ , shrink faster than any geometric sequence, so its series converges for every $x$ . Those of $\tfrac{1}{1-x}$ , the solution of $(1-x)y'=y$ with $y(0)=1$ , stay at $1$ , and the series converges only for $|x|<1$ — up to $x=1$ , where the coefficient of $y'$ vanishes.

From the recurrence to the series

A recurrence $a_{n+2}=\rho(n)\,a_{n}$ unwinds into a product: $a_{}$ . If some factor is zero, that family of coefficients stops and its solution is a polynomial. Otherwise the ratio test of the analysis course, applied to consecutive non-zero terms, gives the reach of the series: when , it converges for , and for every when .

\Bigl|\frac{a_{n+2}}{a_{n}}\Bigr|\to L\ \Longrightarrow\ \text{convergence for}\ |x|<\frac{1}{\sqrt{L}}

Reading a recurrence

$a_{n+2}=\tfrac{a_{n}}{n+2}$ gives .

A ratio tending to zero means convergence everywhere

\begin{aligned}&\Bigl|\frac{a_{n+2}}{a_{n}}\Bigr|\to0\\&\Longrightarrow\ \sum_{k}a_{2k}x^{2k}\ \text{converges for every}\ x\end{aligned}

Compare consecutive terms of the series at a fixed x. Their ratio is the ratio of the coefficients times x squared, and since the coefficient ratio tends to zero, so does this, whatever x is. The ratio test of the analysis course then gives convergence at every x.

Proof steps

\Bigl|\frac{a_{2k+2}x^{2k+2}}{a_{2k}x^{2k}}\Bigr|=\Bigl|\frac{a_{2k+2}}{a_{2k}}\Bigr|\,x^{2}

The ratio of consecutive terms of the series.

\Bigl|\frac{a_{2k+2}}{a_{2k}}\Bigr|\,x^{2}\to0\cdot x^{2}=0<1

For every fixed x the ratio tends to zero.

\sum_{k}a_{2k}x^{2k}\ \text{converges}

By the ratio test of the analysis course.

Applications

Practice

Unwinding a Recurrence

Apply the recurrence repeatedly from the first coefficient and look for the pattern in the product.

a_{n+2}=\frac{a_{n}}{n+2}\ \Longrightarrow\ a_{2k}=\frac{a_{0}}{2^{k}k!}

Try it

$a_{n+1}=\dfrac{a_{n}}{n+1}$ with $a_{0}=1$ . What is $a_{n}$ ?