Recursion and Special Sequences

Recursive Formulas

First, let's look at the notation. Take the sequence of integers \(1, 4, 9, 16, 25, 36, 49, \ldots\). To label the terms in the sequence, textbooks use \(a_n\) to denote the \(n^{th}\) term of a sequence, so the fourth term of the sequence is denoted as \(a_4=16\), and the first term of the sequence is \(a_1=1\).

Suppose you have a sequence

$$\{a_n\}=\{a_1, a_2, a_3, \ldots , a_n\},$$

where \(a_n\) is defined as the \(n^{th}\) term in the sequence. Recursion is when the output of one iteration becomes the input of the next. A recursive formula gives us a formula for the next term in the sequence as a function of its previous terms. This form of sequence explicitly demands that you know what the previous term of the term you are trying to find is. By this, there are two fundamental pieces of information you need.

• The value(s) of the first term(s) of the sequence.
• The pattern rule that gives you the subsequent terms.

Note that recursive formulas are also often referred to as recursive relations or recurrence relations.

Recursive Sequences: Examples

We will now have a look at a couple of examples of recursive sequences and their formulas.

Iteration

Iteration is defined as when the same procedure is repeated many times and is the process of composing a function with itself repeatedly. Recursion is when the output of an iteration is used as the input for the next iteration.

Let \(f(x)\) be a function, then the iterates of this function are:

$$f(x), f(f(x)), f(f(f(x))), f(f(f(f(x)))), \ldots $$

Starting with an initial value, you can use iteration to recursively generate a sequence.

Iteration is also useful for modelling real-life situations.

Special Sequences

Special sequences are sequences that have a unique pattern. Let's look at how to generate and spot them.

Special Sequences: Examples

There are many examples of special sequences. Let's take a close look at some well-known examples.

Fibonacci

The Fibonacci sequence, named after a 13^th-century century Italian mathematician, is a sequence in which each term is the sum of the two previous terms. The sequence is given by the following recursion equation,

$$F_n=F_{n-1}+F_{n-2}.$$

Setting \(F_0=0\) and \(F_1=1\), we have:

\[\begin{align} F_2&=F_{1}+F_{0}=1+0=1 \\ F_3&=F_{2}+F_{1}=1+1=2 \\ F_4&=F_3+F_2=2+1=3 \\ F_5&=F_4+F_3=3+2=5 \\ F_6&=F_5+F_4=5+3=8 \text{ etc.} \end{align}\]

This gives us the sequence:

$$\{0,1,1,2,3,5,8,13,21,34,55,89, \ldots \}.$$

The Fibonacci sequence is demonstrated in numerous patterns occurring in nature. For example, the petals of many plants are usually arranged in several clockwise and anti-clockwise spirals, and often the number of spirals in one direction and the other is given as consecutive Fibonacci numbers.

Square Numbers

Fig. 1. Square numbers.

The square numbers form a sequence with a formula given by \(S_n=n^2\):

\[\begin{align} S_0&=0^2=0 \\ S_1&=1^2=1 \\ S_2&=2^2=4 \\ S_3&=3^2=9 \\ S_4&=4^2=16 \text{ etc.} \end{align}\]

Triangle Numbers

Fig. 2. Triangle numbers.

The number of dots in each of the triangles in the above diagram represents the triangle numbers. Each triangle is made by increasing the number of dots in the base by one and then building an equilateral triangle.

The triangular numbers can be generated by the formula \(T_n=\sum_{k=0}^{n} k=0+1+2+\cdots+n=\frac{n(n+1)}{2}\), for example, the first \(6\) terms of the sequence are given by:

\[\begin{align} T_0&=0 \\ T_1&=0+1=\frac{1(1+1)}{2}=1 \\ T_2&=\sum_{k=0}^{2} k=0+1+2=\frac{2(2+1)}{2}=3 \\ T_3&=\sum_{k=0}^{3} k=0+ 1+2+3=\frac{3(3+1)}{2}=6 \\ T_4&=\sum_{k=0}^{4} k=0+1+2+3+4=\frac{4(4+1)}{2}=10 \\ T_5&=\sum_{k=0}^{5} k=0+1+2+3+4+5=\frac{5(5+1)}{2}=15. \end{align}\]

The recursive formula for this sequence of numbers is given as \(T_n=T_{n-1}+n\), so with a starting value of \(T_0=0\) we can yield the same result:

\[\begin{align} T_0&=0 \\ T_1&=T_{0}+1=0+1=1 \\ T_2&=T_{1}+2=1+2=3 \\ T_3&=T_{2}+3=3+3=6 \\ T_4&=T_{3}+4=6+4=10 \\ T_5&=T_{4}+5=10+5=15. \end{align}\]

An interesting feature of triangle numbers is that if you add consecutive triangle numbers, you will get a sequence of square numbers as follows:

\[\begin{align} T_0+T_1&=0+1=1\times1=1^2=S_1 \\ T_1+T_2&=1+3=4=2\times2=2^2=S_2 \\ T_2+T_3&=3+6=9=3\times3=3^2=S_3 \\ T_3+T_4&=6+10=16=4\times4=4^2=S_4 \\ T_4+T_5&=10+15=25=5\times5=5^2=S_5 \text{ etc.} \end{align}\]

Cube Numbers

Fig. 3. Cube numbers.

The general formula of cube numbers is \(C_n=n^3\). The first five terms of the sequence of cube numbers a given by:

\[\begin{align} C_0&=0^3=0 \\ C_1&=1^3=1 \\ C_2&=2^3=8 \\ C_3&=3^3=27 \\ C_4&=4^3=64. \end{align}\]

The sum of the first \(n\) cube numbers is equal to the square of their sum:

$$C_1+C_2+\ldots+C_n=1^3+2^3+\ldots+n^3=(1+2+\ldots+n)^2.$$

Alternatively, you can use the following formula for the sum of the first \(n\) cube numbers

$$\sum_{k=1}^{n} k^3= \frac{n^2(n+1)^2}{4},$$

Which has been derived from the triangle numbers, \(T_n=\sum_{k=1}^{n} k=\frac{n(n+1)}{2}\). The sum of the first \(n\) cube numbers is equal to the square of the \(n^{th}\) triangular number, as follows:

$$\sum_{k=1}^{n} k^3=\left(\frac{n(n+1)}{2}\right)^2=\frac{n^2(n+1)^2}{4}.$$

Arithmetic Sequences and Recursive Formulas

Another important type of special sequence is an arithmetic sequence. These are sequences where there is a common difference that remains constant between any two consecutive terms. You will need to be able to identify arithmetic sequences by looking at the difference between terms and find the corresponding recursive formula.

Let's look at an example:

Suppose you are given the \(n^{th}\) term and common difference of an arithmetic sequence, you can then find the next term in the sequence, \(a_{n+1}\) using the recursive formula for an arithmetic sequence.

Examples of Arithmetic Sequences and Recursive Formulas

Now, let's explore some examples.