Back to the on-screen lesson · Print

The recurrence relation

Turning the coefficient equation into a rule, running it from the two coefficients it leaves free, and recognising the even and odd branches as the two independent solutions.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to solve a coefficient equation for its highest index to get a recurrence, generate coefficients along the even and odd chains without mixing them, say which coefficients the recurrence leaves free and why there are exactly that many, produce the two independent solutions from the two obvious starting choices, and assemble a branch back into a polynomial in $x$.

2. What you already have

You can substitute a power series into an equation, shift the indices so the sums combine, and set the coefficient of each power to zero. That leaves a relation between coefficients rather than an answer. This lesson is what to do with the relation, and why what comes out is two solutions rather than one.

3. Words this lesson uses

4. One rule, two chains, two solutions

Matching coefficients leaves an equation for each power of $x$. Solved for the highest index it becomes a recurrence, for instance

$$a_{n+2} = \frac{2a_n}{n+2}.$$

Everything about the method follows from reading that literally. It determines $a_2$ from $a_0$, $a_3$ from $a_1$, $a_4$ from $a_2$, and so on for ever. It never determines $a_0$ or $a_1$ at all, because there is no rule with those on the left.

So two coefficients are free, and that is the two arbitrary constants of a second-order equation, arriving in a form you might not have recognised. The initial conditions set them: $y(0) = a_0$ and $y'(0) = a_1$, directly, with no algebra.

And they never mix. A rule stepping two places at a time keeps even indices with even and odd with odd, so the coefficients form two chains that share nothing. Taking $a_0 = 1$, $a_1 = 0$ gives a series in even powers only; taking $a_0 = 0$, $a_1 = 1$ gives one in odd powers only. Neither is a multiple of the other — one is an even function and the other an odd one — so the two branches are the fundamental set, produced by the method rather than looked for afterwards.

5. When the series turns out to be an old friend

Recurrences with simple factorials in them often generate a series that has a name, and spotting it is worth a moment's attention at the end of every calculation.

From $a_{n+2} = -\dfrac{a_n}{(n+2)(n+1)}$ with $a_0 = 1$, $a_1 = 0$, the coefficients are $1, 0, -\tfrac{1}{2!}, 0, \tfrac{1}{4!}, \ldots$ — the cosine. The other branch, from $a_0 = 0$ and $a_1 = 1$, is the sine. The equation was $y'' + y = 0$, and the method rediscovered both solutions without being told about trigonometry.

The habit that makes this visible is to leave the factorials unmultiplied. Writing $\tfrac{1}{24}$ hides what $\tfrac{1}{4!}$ announces, and a recognisable series written as decimals is a series nobody recognises. It also matters for a reason beyond elegance: a closed form, once spotted, is valid everywhere it is defined, while the series was only guaranteed as far as the nearest singular point.

6. Where this goes wrong

Working along the list. A two-step recurrence does not give $a_3$ from $a_2$. Following the list in order rather than following each chain produces coefficients that belong to no solution at all.

Expecting the recurrence to determine everything. If it appears to fix $a_0$ as well, something has gone wrong earlier — usually a lowest-power term that was swept into a sum instead of being matched on its own.

Confusing the index with the exponent. $a_4$ is the fifth coefficient and multiplies $x^{4}$. Both descriptions are right and mixing them shifts the whole answer by a power.

Reporting one branch as the general solution. Setting $a_0 = 1$, $a_1 = 0$ gives one solution. The general solution needs both, with a constant in front of each.

7. The method, step by step, and how to check it

Once a recurrence is in hand, reading a solution from it is a routine of its own.

1. Read the step size. $a_{n + 2}$ from $a_n$ steps by two, so the even and odd coefficients form two separate chains. $a_{n + 3}$ from $a_n$ steps by three, and then there are three chains, one of which may be forced to zero by a lowest-power equation.
2. Set the free coefficients. $a_0$ starts the even chain and $a_1$ the odd one; they are $y(0)$ and $y'(0)$. To build a fundamental set, run one chain with $a_0 = 1$, $a_1 = 0$ and the other with $a_0 = 0$, $a_1 = 1$.
3. Generate coefficients along each chain, putting $n = 0, 2, 4, \dots$ into the even chain and $n = 1, 3, 5, \dots$ into the odd one. Leave products unmultiplied: $\frac{1}{4 \cdot 3 \cdot 2 \cdot 1}$ is $\frac{1}{4!}$.
4. Look for a zero in the numerator. Factor it. If it vanishes at some $n$, every coefficient after that on the same chain is zero and the branch is a polynomial.
5. Look for a pattern. Write the general coefficient, such as $a_{2j} = \frac{(-1)^{j}}{(2j)!}$, and compare with the series you know: $e^{x}$, $\cos x$, $\sin x$, $\cosh x$, $\sinh x$ and $\frac{1}{1 - x}$.

Why chains never mix. The recurrence links $a_{n + 2}$ only to $a_n$, which has the same parity. So the value of $a_1$ can never affect an even coefficient, and the two branches are independent solutions. That independence is the series version of two linearly independent solutions of a second-order equation.

How to check the answer. For a polynomial branch, substitute it into the equation: every power must cancel. For a recognised closed form, check that its value and slope at $0$ match $a_0$ and $a_1$, and that it satisfies the equation. For a series that has no closed form, check the first two or three coefficients by substituting the truncated series and confirming the lowest powers cancel. A coefficient that comes out on the wrong chain, such as an odd one appearing when $a_1 = 0$, means the list was followed in order instead of the chain.

8. In the world: why energy comes in packets

In quantum mechanics a particle held by a spring-like force, a vibrating molecule for instance, is described by Hermite's equation, and solving it by series leads to the recurrence

$$a_{n + 2} = \frac{2(n - \lambda)}{(n + 2)(n + 1)}a_n,$$

where $\lambda$ is proportional to the particle's energy. For most values of $\lambda$ neither chain stops, and the resulting series grows like $e^{x^{2}}$, far too fast for the wave function to describe a particle that stays near its spring. Only when the numerator can vanish, when $\lambda$ is a whole number $n$, does one chain terminate in a polynomial, and only then is there a physical solution.

So the energies allowed are $E_n = \left(n + \frac{1}{2}\right)\hbar\omega$ and nothing between: the quantisation of energy is the condition that a recurrence terminates. This lesson's example with $2(n - 2)$ in the numerator is the case $\lambda = 2$, the second excited state, and the polynomial $1 - 2x^{2}$ found there is its wave function. Chemists read these energy gaps from the infrared light molecules absorb: each absorbed frequency is one step up the ladder that the recurrence allows.

9. In the world: how a calculator computes a cosine

A calculator does not store a table of cosines. It evaluates the series $\cos x = 1 - \frac{x^{2}}{2!} + \frac{x^{4}}{4!} - \cdots$, and it does not compute the factorials either: it uses exactly this lesson's recurrence, $a_{n + 2} = -\frac{a_n}{(n + 2)(n + 1)}$, and builds each term from the one before with one multiplication and one division, $t_{k + 1} = -t_k\frac{x^{2}}{(2k + 1)(2k + 2)}$.

For $x = 0.5$: $t_0 = 1$, $t_1 = -\frac{0.25}{2} = -0.125$, $t_2 = 0.125 \times \frac{0.25}{12} \approx 0.0026042$, $t_3 \approx -0.0026042 \times \frac{0.25}{30} \approx -0.0000217$. The sum is $0.8775825$, and the true value is $0.8775826$: four terms, twelve arithmetic operations, seven correct digits. Working chain by chain, and never recomputing a factorial, is what makes the method fast; reducing a large angle to a small one first, using the function's periodicity, is what keeps the number of terms small. Every sine, cosine and exponential on a phone is computed by a refinement of this recurrence.

10. In the world: a recurrence that decides a design

Engineers meet recurrences whenever a quantity is built step by step, and the question this lesson taught to ask, does the chain stop, or how fast do its terms shrink, is the practical one: a series used to compute a load, a probability or a signal is only useful if its terms shrink fast enough to stop after a few. The ratio $\frac{a_{n + 2}}{a_n}$, read from the recurrence, answers it before any term is computed.

11. In the world: counting with recurrences

Recurrences are also how combinatorics counts. The number of ways to tile a strip with squares and dominoes satisfies $a_{n + 2} = a_{n + 1} + a_n$, the Fibonacci rule, and generating functions, power series whose coefficients are those counts, turn such recurrences into equations for a function, the same exchange of coefficients for functions that this lesson used in reverse. Computer scientists use it to count the steps an algorithm takes, and the growth of the coefficients, read from the recurrence's ratio, is the algorithm's running time.

12. The two free coefficients are the two arbitrary constants, not a choice of example

Setting $a_0 = 1$, $a_1 = 0$ looks like picking a convenient special case to illustrate the method, and learners often produce that one series and stop, as though the general solution were somewhere further on. It is not: the two branches obtained from the two obvious choices are the fundamental set, and every other solution is a combination of them. Seeing why is worth the effort — a second-order equation has a two-dimensional solution space, the recurrence fixes everything except $a_0$ and $a_1$, so the solutions are parametrised by exactly two numbers and the two basis choices span them. The habit that follows is to run the recurrence twice, deliberately, and to write the answer with a constant in front of each branch.

13. Two branches, written out

1. For $y'' - y = 0$ the recurrence is $a_{n + 2} = \dfrac{a_n}{(n + 2)(n + 1)}$. Run the even chain from $a_0 = 1$, $a_1 = 0$.

   $a_2 = \dfrac{1}{2 \cdot 1} = \dfrac{1}{2!}, \quad a_4 = \dfrac{a_2}{4 \cdot 3} = \dfrac{1}{4!}, \quad a_{\text{odd}} = 0$

   One branch at a time; leaving the factorials visible makes the pattern recognisable.

2. Recognise the even branch.

   $1 + \dfrac{x^{2}}{2!} + \dfrac{x^{4}}{4!} + \cdots = \cosh x$

   The factorials give it away: the even-power half of $e^{x}$.

3. Run the odd chain from $a_0 = 0$, $a_1 = 1$.

   $a_3 = \dfrac{1}{3 \cdot 2} = \dfrac{1}{3!}, \qquad a_5 = \dfrac{a_3}{5 \cdot 4} = \dfrac{1}{5!}$

   The same recurrence, the other chain.

4. Recognise the odd branch.

   $x + \dfrac{x^{3}}{3!} + \dfrac{x^{5}}{5!} + \cdots = \sinh x$

   The odd-power half of $e^{x}$.

5. Write the general solution and check one branch.

   $y = c_1\cosh x + c_2\sinh x; \qquad (\cosh x)'' = \cosh x$

   The two branches were the fundamental set all along, and each satisfies $y'' = y$.

14. A branch that terminates

1. Legendre's equation with parameter $1$ has this recurrence. Look at its numerator.

   $a_{n + 2} = \dfrac{\left(n(n + 1) - 2\right)a_n}{(n + 2)(n + 1)}$

   The numerator can vanish, and a zero anywhere in a chain stops it.

2. Put $n = 1$ into the numerator.

   $1 \times 2 - 2 = 0 \quad\Rightarrow\quad a_3 = 0 \quad\Rightarrow\quad a_5 = a_7 = \cdots = 0$

   One zero link ends the whole chain.

3. Read off the odd branch.

   $y_{\text{odd}} = a_1x = x$

   A terminating branch is a polynomial solution: this is where the Legendre polynomials come from.

4. Check the polynomial in the equation $(1 - x^{2})y'' - 2xy' + 2y = 0$.

   $y = x: \quad (1 - x^{2}) \cdot 0 - 2x \cdot 1 + 2x = 0$

   It holds for every $x$, beyond the series' radius, as a polynomial must.

5. Run the even branch, which does not stop.

   $n = 0: \ a_2 = \dfrac{-2}{2}a_0 = -a_0; \qquad n = 2: \ a_4 = \dfrac{4}{12}a_2 = -\dfrac{a_0}{3}$

   The numerator $n(n + 1) - 2$ is zero only at $n = 1$, so the even chain runs for ever.

15. Hermite's equation, and a polynomial from the even chain

1. For $y'' - 2xy' + 4y = 0$, collect the coefficient of $x^{n}$.

   $(n + 2)(n + 1)a_{n + 2} - 2na_n + 4a_n = 0$

   $xy'$ contributes $na_n$ to the coefficient of $x^{n}$, and $y''$ its shifted term.

2. Solve that equation for the highest coefficient, $a_{n + 2}$.

   $a_{n + 2} = \dfrac{(2n - 4)a_n}{(n + 2)(n + 1)} = \dfrac{2(n - 2)a_n}{(n + 2)(n + 1)}$

   Factor the numerator to see where it vanishes: at $n = 2$.

3. Run the even chain from $a_0 = 1$.

   $n = 0: \ a_2 = \dfrac{2(-2)}{2 \cdot 1} = -2; \qquad n = 2: \ a_4 = \dfrac{2 \cdot 0}{4 \cdot 3}a_2 = 0$

   The zero at $n = 2$ ends the chain after $a_2$.

4. Write the even branch.

   $y_1 = 1 - 2x^{2}$

   A polynomial solution; up to a constant it is the Hermite polynomial of degree two.

5. Check it in the equation.

   $y_1' = -4x, \quad y_1'' = -4: \qquad -4 - 2x(-4x) + 4(1 - 2x^{2}) = -4 + 8x^{2} + 4 - 8x^{2} = 0$

   Every power cancels, so the polynomial is an exact solution.

6. Run the odd chain from $a_1 = 1$.

   $n = 1: \ a_3 = \dfrac{2(-1)}{3 \cdot 2} = -\dfrac{1}{3}; \qquad n = 3: \ a_5 = \dfrac{2 \cdot 1}{5 \cdot 4}a_3 = -\dfrac{1}{30}$

   The numerator vanishes only at $n = 2$, which the odd chain never visits, so this branch does not stop.

7. Write the general solution.

   $y = c_1\left(1 - 2x^{2}\right) + c_2\left(x - \dfrac{x^{3}}{3} - \dfrac{x^{5}}{30} - \cdots\right)$

   One branch is a polynomial and the other a genuine infinite series; both converge everywhere because the coefficients are polynomials.

16. Your turn: from $a_{n+2} = \dfrac{a_n}{n+2}$ with $a_0 = 1$ and $a_1 = 0$, write the first three non-zero terms

1. Decide which chain is alive.

   $a_1 = 0 \Rightarrow a_3 = a_5 = \cdots = 0$

   Only the even chain starts non-zero.

2. Your turn: work this step out. Its working is at the end of the packet.

   Apply the rule twice.

3. Your turn: work this step out. Its working is at the end of the packet.

   Write the terms and recognise them.

17. Guided practice

Each of these recurrences starts from $a_0 = 1$ and $a_1 = 0$. Match each to the series it generates.

18. Guided practice

Complete the worked solution: the series with $a_{n + 2} = 2a_n$, $a_0 = 5$ and $a_1 = 0$.

1. Put $n = 0$ into the rule.

   $a_{0 + 2} = 2 \cdot a_0 = 2 \times 5 =$ _p

   The rule reaches back two places, so $a_2$ comes from $a_0$.

2. Put $n = 1$ into the rule.

   $a_{1 + 2} = 2 \cdot a_1 = 2 \times 0 =$ _z

   The odd chain starts at zero, so it stays at zero.

3. Put $n = 2$ into the rule, using the value of $a_2$ you found.

   $a_{2 + 2} = 2 \cdot a_2 =$ _q

   Multiply the coefficient two places back by $2$ again.

4. Put each coefficient against the power equal to its index.

   $y = a_0 + a_2x^{2} + a_4x^{4} + \cdots$

   Only even powers appear, because the odd chain is zero.

19. Guided practice

A recurrence connects $a_{n+2}$ to $a_n$. With $a_0 = 0, \ a_1 = 5$, which powers of $x$ appear in the solution?

• Even powers only
• Odd powers only
• Both even and odd powers

20. Practice

A series solution has the recurrence $a_{n+2} = 2a_n$, with $a_0 = 2$ and $a_1 = 5$. Fill in the next four coefficients.

21. Practice

With the recurrence $a_{n+2} = 2a_n$ and $a_0 = 3$, what is $a_6$?

Answer:

22. Practice

A mass on a spring is released and its displacement is found by series: substituting a power series into its equation of motion gives the recurrence below, with $x$ the time in seconds. A series solution about $x = 0$ has the recurrence $a_{n + 2} = -\dfrac{9a_n}{(n + 2)(n + 1)}$ with $a_0 = 4$ and $a_1 = 3$. Find $y$ in closed form (type cos(...) and sin(...)).

Answer:

23. Somewhere new

A solution has $a_{n+2} = 3a_n$ with $a_0 = 3$ and $a_1 = 0$. Write its first three non-zero terms as a polynomial in $x$.

Answer:

24. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

25. Test question

A mass on a spring is released and its displacement is found by series: substituting a power series into its equation of motion gives the recurrence below, with $x$ the time in seconds. A series solution about $x = 0$ has the recurrence $a_{n + 2} = -\dfrac{4a_n}{(n + 2)(n + 1)}$ with $a_0 = 1$ and $a_1 = 4$. Find $y$ in closed form (type cos(...) and sin(...)).

Answer:

26. What you can do now

You can run a recurrence to generate coefficients and read the two independent solutions off its two branches. Say in your own words why exactly two coefficients are left free by a second-order equation.

Working for the steps left to you

16. Your turn: from $a_{n+2} = \dfrac{a_n}{n+2}$ with $a_0 = 1$ and $a_1 = 0$, write the first three non-zero terms, step 2

16. Your turn: from $a_{n+2} = \dfrac{a_n}{n+2}$ with $a_0 = 1$ and $a_1 = 0$, write the first three non-zero terms, step 3