Recursive Definitions

From a Rule to a Recursive Definition

In the previous tutorial, sequences were treated as indexed lists of real numbers, and induction was used to prove claims about their terms. A sequence can also be specified by describing how to obtain each new term from earlier information. Such a description is a recursive definition. It gives a starting value and a rule that advances from one index to the next.

For example, the instructions $a_0=3$ and $a_{n+1}=a_n+4$ specify the first term and how to calculate every subsequent term. They give $a_1=7$, $a_2=11$, and $a_3=15$. To make this a complete definition, the starting index and the range of the rule must be clear: here $a_n$ is defined for $n\in\mathbb{N}_0$, and the rule applies for every $n\in\mathbb{N}_0$.

Definition (Recursive definition of a real sequence). A real sequence $(a_n)_{n=0}^{\infty}$ is defined recursively by an initial value and a rule if a starting term, such as $a_0$, is specified and each later term is specified from the preceding term or terms. A first-order recursive rule has the form $$ a_{n+1}=F(n,a_n), $$ where $F$ is a specified function and the rule applies for each $n\in\mathbb{N}_0$.

The initial value is sometimes called the initial condition, and the rule is called the recurrence relation. The word “recursively” does not remove the need to state either one. A rule such as $a_{n+1}=a_n+4$, without a starting value, allows many sequences: any choice of $a_0$ produces a different one. Likewise, a starting value without a rule gives no instructions for later terms.

Reading and Checking a Recursive Definition

To use a recursive definition, begin at the specified initial index and apply the rule in order. In the example $a_0=3$, $a_{n+1}=a_n+4$, the rule at $n=0$ gives $a_1=a_0+4=7$. At $n=1$, it gives $a_2=a_1+4=11$. The subscript on the left is one larger than the subscript on the right; this is the central index change in a first-order recurrence.

Worked Example: Generating Terms from a Recurrence

Let $u_0=2$, and define $u_{n+1}=u_n+2n+1$ for $n\in\mathbb{N}_0$. Apply the rule successively:

\begin{aligned} u_1&=u_0+2\cdot0+1=2+1=3,\\ u_2&=u_1+2\cdot1+1=3+3=6,\\ u_3&=u_2+2\cdot2+1=6+5=11,\\ u_4&=u_3+2\cdot3+1=11+7=18. \end{aligned}

The term added depends on the index $n$, not on the new index $n+1$. For instance, $u_3$ is calculated by using $n=2$ in the rule, so the increment is $2\cdot2+1=5$. This distinction prevents a common off-by-one error.

A recursive definition gives a procedure for generating terms, but it does not always display a term directly in terms of its index. An explicit formula does that. For the sequence in the example, one can check that $u_n=n^2+2$: this gives $u_0=2$, and the difference between the formula at $n+1$ and at $n$ is $2n+1$. The next theorem explains a general way to obtain explicit formulas for an important class of recurrences.

Uniqueness of a Recursive Definition

A recursive rule is useful only if it consistently determines the terms. The uniqueness statement below says that two sequences with the same initial value and the same rule cannot differ at a later index. Its proof uses the Principle of Mathematical Induction from the tutorial “Mathematical Induction.”

Theorem (Uniqueness for a first-order recurrence). Suppose $(a_n)$ and $(b_n)$ are real sequences with $a_0=b_0$, and suppose that for every $n\in\mathbb{N}_0$, $$ a_{n+1}=F(n,a_n) \qquad\text{and}\qquad b_{n+1}=F(n,b_n), $$ where the same rule $F$ is used for both sequences. Then $a_n=b_n$ for every $n\in\mathbb{N}_0$.

Proof. Let $P(n)$ be the statement $a_n=b_n$. The initial condition gives $a_0=b_0$, so $P(0)$ holds. Now let $n\in\mathbb{N}_0$, and suppose $P(n)$ holds. Applying the recurrence rules and then the assumed equality gives

a_{n+1}=F(n,a_n)=F(n,b_n)=b_{n+1}.

Thus $P(n)$ implies $P(n+1)$. By the Principle of Mathematical Induction, $P(n)$ holds for every $n\in\mathbb{N}_0$. Therefore the two sequences agree at every index. $\square$

The theorem establishes uniqueness, not a formula for calculating the terms. In practice, the recurrence generates terms one at a time, while an explicit formula—when one is available—can make a particular term easier to calculate. A proposed explicit formula can be checked by verifying its initial value and showing that it satisfies the recurrence at every index. The uniqueness theorem then guarantees that it is the sequence specified by the recursion.

Solving an Affine Recurrence

A first-order affine recurrence has a rule that multiplies the current term by a fixed real number and then adds another fixed real number. Both constants matter: the multiplier controls how earlier values are carried forward, while the added constant shifts the terms. The following theorem gives an explicit formula, including the special case where the multiplier is $1$.

Theorem (Explicit formula for an affine recurrence). Let $x_0,c,r\in\mathbb{R}$, and define $$ x_{n+1}=rx_n+c $$ for every $n\in\mathbb{N}_0$. If $r\neq1$, then for every $n\in\mathbb{N}_0$, $$ x_n=r^n x_0+c\frac{1-r^n}{1-r}. $$ If $r=1$, then $x_n=x_0+nc$ for every $n\in\mathbb{N}_0$.

Proof. First suppose $r\neq1$, and let $P(n)$ be the claim that $x_n=r^n x_0+c(1-r^n)/(1-r)$. At $n=0$, the right-hand side is

r^0x_0+c\frac{1-r^0}{1-r}=x_0+c\frac{1-1}{1-r}=x_0,

which equals $x_0$, so the base case holds. Suppose the formula holds at $n$. The recurrence gives

\begin{aligned} x_{n+1} &=rx_n+c\\ &=r\left(r^n x_0+c\frac{1-r^n}{1-r}\right)+c\\ &=r^{n+1}x_0+c\frac{r-r^{n+1}}{1-r}+c\\ &=r^{n+1}x_0+c\frac{r-r^{n+1}+1-r}{1-r}\\ &=r^{n+1}x_0+c\frac{1-r^{n+1}}{1-r}. \end{aligned}

This is the formula at $n+1$. Induction proves it for every $n\in\mathbb{N}_0$. Now suppose $r=1$. The claimed formula is $x_n=x_0+nc$. At $n=0$ it equals $x_0$. If $x_n=x_0+nc$, then

x_{n+1}=x_n+c=x_0+nc+c=x_0+(n+1)c.

This proves the formula for $r=1$ by induction as well. $\square$

Worked Example: Solving a Recurrence with a Constant Added Term

Let $x_0=5$ and $x_{n+1}=2x_n+3$. Here $r=2$, $c=3$, and $r\neq1$. The theorem gives

x_n=2^n\cdot5+3\frac{1-2^n}{1-2} =5\cdot2^n+3(2^n-1) =8\cdot2^n-3.

The initial value checks: $8\cdot2^0-3=8-3=5=x_0$. The recurrence also checks directly:

2x_n+3=2(8\cdot2^n-3)+3=16\cdot2^n-6+3 =8\cdot2^{n+1}-3=x_{n+1}.

The first few recursively generated terms are $5$, $13$, and $29$. The formula gives $x_1=8\cdot2-3=13$ and $x_2=8\cdot4-3=29$, matching the recurrence.

Worked Example: A Recurrence with a Negative Multiplier

Let $y_0=4$ and $y_{n+1}=-y_n+6$. Now $r=-1$, $c=6$, and $r\neq1$. Substitution into the theorem gives

y_n=(-1)^n\cdot4+6\frac{1-(-1)^n}{1-(-1)} =4(-1)^n+3\bigl(1-(-1)^n\bigr) =3+(-1)^n.

For even $n$, $(-1)^n=1$, so the formula gives $y_n=4$. For odd $n$, $(-1)^n=-1$, so it gives $y_n=2$. In particular, the first terms are $y_0=4$, $y_1=2$, $y_2=4$, and $y_3=2$. The recurrence verifies the alternation: if $y_n=4$, then $y_{n+1}=-4+6=2$; if $y_n=2$, then $y_{n+1}=-2+6=4$.

Worked Example: The Special Case with Multiplier One

Let $z_0=-2$ and $z_{n+1}=z_n+5$. This has $r=1$ and $c=5$, so the special case of the theorem gives

$$ z_n=-2+5n. $$

The formula gives $z_0=-2+5\cdot0=-2$. If $z_n=-2+5n$, then the recurrence yields

z_{n+1}=z_n+5=(-2+5n)+5=-2+5(n+1),

as required. The first terms are $-2,3,8,13$. The separate case $r=1$ is necessary in the theorem because its other formula divides by $1-r$, which would be zero.

What to Check Before Using a Recurrence

A recursive definition is a complete specification only when the starting data, the rule, and the range of indices are all clear. For a first-order rule, one starting value is enough to determine at most one sequence, as the uniqueness theorem shows. For a rule involving two preceding terms, such as $a_{n+2}=a_{n+1}+a_n$, two starting values are needed. More generally, the number of initial terms must match how many earlier terms the rule requires.

There is also a difference between showing that a formula satisfies a recursion and merely checking several terms. Calculating $a_0,a_1,a_2$ can catch an arithmetic or indexing mistake, but it does not verify the rule at every index. When an explicit formula is proposed, check the initial condition and perform the recurrence calculation for an arbitrary index $n$. The uniqueness theorem then connects those checks to the entire recursively defined sequence.

Record the initial data.
Write down the specified starting value or values and their indices.

Read the recurrence at index $n$.
Identify exactly which earlier terms and which index-dependent quantities determine the next term.

Generate terms in order.
Substitute the known term or terms into the rule, keeping the index on the right-hand side clear.

Check a proposed explicit formula.
Verify the starting value, then show that the formula obeys the recurrence for an arbitrary permitted index.

Use uniqueness when appropriate.
If the initial data and recurrence agree, the uniqueness theorem shows that the sequences agree at every index.

Key takeaway. A recursive definition specifies a starting value and a rule for obtaining later values. Induction proves that the same initial data and rule determine at most one sequence; for affine recurrences, induction can also verify a useful explicit formula.

Check Your Understanding

Use the definitions and results in this tutorial to answer the following questions.

What two ingredients are needed for a first-order recursive definition to specify a sequence?
If $a_0=1$ and $a_{n+1}=a_n+3n$, calculate $a_1$, $a_2$, and $a_3$. Which index is used to calculate $a_3$?
Why does the uniqueness theorem require both sequences to have the same initial value and use the same recurrence rule?
For $x_0=2$ and $x_{n+1}=3x_n+1$, identify $r$ and $c$, and write the explicit formula supplied by the affine recurrence theorem.
Why must the affine recurrence theorem treat $r=1$ separately?

What You'll Learn