Recurrence Relations Explained in 5 Minutes

Recurrence Relations Explained in 5 Minutes

Recurrence equations are powerful things because they let you define a function in terms of itself!

Suppose we have a function of an integer variable f(n), then an example of a recurrence equation is..

f(n)=k*f(n-1)-f(n-2)

where n=2,3,4,5,.. and k is a constant.

So if k, f(0) and f(1) are given, then f(n) can be calculated for any n. It defines itself!

We can also solve recurrence equations. This is an area of mathematics called the Theory of Finite Differences. The solution of the above recurrence is a nice surprise..

f(n)=sin(n*a)

It's the famous sine function, where a is a constant and k=2*cos(a). So the solution is a wave? Yes, if you plot f(n) for n=2,3,4,5,... you get the beautiful sine wave, and the three numbers k, f(0) and f(1) determine the amplitude, wavelength and phase of the wave. Nature uses recurrence relations to generate all sort of amazing things, which is why the sine function shows up so often when we try to describe these things in physics. But we could bypass the sine function and describe them with a simple recurrence relation instead!

In fact, this difference equation is the equation of motion for a Simple Harmonic Oscillator which is usually written as a 2nd order differential equation. Difference equations can replace differential equations!

There are also such things as partial difference equations which replace partial differential equations.

Content written and posted by Ken Abbott abbottsystems@gmail.com