examples of simple recurrence relations

Many arithmetic functionsMathworldPlanetmath can be expressed as recurrence relations, even in those cases where it would be far more computationally efficient to use a non-recursive formulaMathworldPlanetmathPlanetmath. For example, n2 (whether n is an integer or any other kind of real number) is most easily calculated as n×n. The recurrence relation for n2 (with n a positive integer) is an=an-1+2n-1, with of course a1=1 (and if you like, a0=0). The value of these recurrence relations is to illustrate the basic idea of recurrence relations with examples that can be easily verified with only a small effort. Similarly, the nth triangular numberMathworldPlanetmath can be obtained from an=an-1+n (again with a1=1, which will be tacitly assumed for the rest of these examples unless otherwise explicitly noted). Another such recurrence relation is that for n!, namely an=n(an-1). For n3, just multiplying n thrice certainly looks more efficient than the recurrence relation an=an-1+3(n-1)2+3(n-1)+1.

Certain famous sequencesMathworldPlanetmath, such as the Fibonacci sequenceMathworldPlanetmath and the Padovan sequenceMathworldPlanetmath, are perhaps more easily calculated by their recurrence relations than by a formula. The recurrence relations for these explicitly set a1 and a2 (or a0 and a1, depending on taste), and the rest are given by an=an-2+an-1 (that is, add up the previous two terms). So, for the Fibonacci sequence, a1=a2=1, and we can easily verify that the next few terms are 2, 3, 5, 8, 13, 21, 34, 55, 89, etc. Adding up 34 and 55 is certainly quicker than computing


Moving on to a slightly more complicated recurrence relation: that for the Catalan numbersDlmfMathworldPlanetmath. With C0=1, the later numbers can calculated by


meaning that with the terms you do know, you multiply the first by the last, then multiply the second by the penultimate, etc., until reaching the middle terms, then add up those productsPlanetmathPlanetmath. For smaller terms, this can actually be faster than by calculating binomial coefficientsDlmfDlmfMathworldPlanetmath. Suppose you know the first eight terms (zeroeth to seventh): 1, 1, 2, 5, 14, 42, 132, 429. 429 plus 132, plus twice 42, plus twice 5 times 14, plus twice 42 again, and 132 and 429 again gives 1430. We doublecheck that by calculating the eight central binomial coefficientMathworldPlanetmath (which involves dealing with numbers as large as 20922789888000), 12870, and dividing that by 9 we get 1430, confirming our calculation by the recurrence relation. For a computer, there would be no appreciable differencePlanetmathPlanetmath for the smaller Catalan numbers, but for the larger ones the recurrence relation would show itself to be too stack-intensive to be practical.

Lastly, we wish to give two examples where the initial term is not 0 or 1. The Lucas-Lehmer primality test uses a sequence defined by the recurrence relation an=an-12-2 with initial term a1=4. The sequence thus begins: 4, 14, 194, 37634, 1416317954, 2005956546822746114, 4023861667741036022825635656102100994, etc. (see A003010 in Sloane’s OEIS). That the sequence has been calculated correctly can be verified by choosing some small Mersenne number 2n-1 one knows to be either prime or composite, then seeing if that Mersenne number is divisible by an-1. Then there’s the Perrin sequenceMathworldPlanetmath, where not one or two but three initial terms are explicitly defined: a0=3, a1=0, a2=2. The later terms are given by an=an-3+an-2 for n>2.

Title examples of simple recurrence relations
Canonical name ExamplesOfSimpleRecurrenceRelations
Date of creation 2013-03-22 17:52:51
Last modified on 2013-03-22 17:52:51
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 6
Author PrimeFan (13766)
Entry type Example
Classification msc 03D20
Classification msc 11B37