Recursive Definitions

Definitions by Recursion

Many mathematical objects are defined recursively. A recursive definition specifies:

one or more initial values,
a rule for constructing later values from earlier ones.

The natural numbers themselves arise recursively through the successor operation:

1,2,3,\ldots

where each number is obtained from the preceding one by adding $1$ .

Recursive definitions are fundamental in number theory because arithmetic processes often proceed step by step. Sequences, algorithms, and arithmetic functions are naturally described in recursive form.

Recursive Sequences

A sequence is a function

a:\mathbb{N}\to\mathbb{Z}

that assigns an integer $a_n$ to each natural number $n$ .

A recursive sequence defines $a_n$ in terms of earlier terms.

For example, the Fibonacci sequence is defined by

F_1=1, \qquad F_2=1,

and

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

for all $n\ge3$ .

The first terms are therefore

1,1,2,3,5,8,13,\ldots

Each term depends on the two preceding terms.

Recursive sequences appear throughout number theory, combinatorics, and algebra.

Arithmetic Defined Recursively

Arithmetic operations themselves may be defined recursively.

Addition can be defined by:

a+0=a

and

a+(b+1)=(a+b)+1.

The first equation specifies the initial value. The second explains how to compute addition for larger integers.

Multiplication can similarly be defined recursively:

a\cdot0=0

and

a(b+1)=ab+a.

Thus multiplication is repeated addition.

Exponentiation is defined recursively by

a^0=1

and

a^{n+1}=a^n a.

These recursive definitions show that increasingly complicated arithmetic operations are built from simpler ones.

Factorials

One of the most important recursively defined functions is the factorial function.

For $n\in\mathbb{N}$ , define

n!=1\cdot2\cdot3\cdots n.

Recursively, factorials are defined by

0!=1

and

(n+1)!=(n+1)n!.

The first few values are

1,1,2,6,24,120,\ldots

Factorials appear in combinatorics, probability, analysis, and analytic number theory.

Recursive Algorithms

Many arithmetic algorithms are recursive.

The Euclidean algorithm computes the greatest common divisor of two integers $a$ and $b$ . It relies on the recursive relation

\gcd(a,b)=\gcd(b,r),

where $r$ is the remainder when $a$ is divided by $b$ .

Since the remainder satisfies

0\le r<b,

the problem is reduced to smaller integers. Repeated application eventually terminates.

Recursive reduction is one of the central ideas of computational number theory.

Well-Definedness

A recursive definition is meaningful only if it uniquely determines all terms.

For example, the Fibonacci recursion uniquely determines every term because the initial values

F_1 \quad\text{and}\quad F_2

are specified.

Without initial values, the recursion

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

would admit infinitely many different sequences.

Similarly, the recursion

a_{n+1}=a_n+2

does not determine a unique sequence unless one initial term is given.

Thus recursive definitions require both a starting point and a recursive rule.

Proofs by Recursion and Induction

Recursive definitions are closely connected with induction.

A recursively defined sequence is naturally analyzed by induction because each term depends on earlier terms.

For example, one may prove by induction that the Fibonacci numbers satisfy

F_n<2^n

for all $n\ge1$ .

Similarly, properties of factorials are usually established inductively.

Recursion defines objects step by step, while induction proves statements step by step. The two principles therefore complement one another.

Linear Recurrence Relations

A recurrence relation is called linear if later terms are linear combinations of earlier terms.

For example,

a_n=3a_{n-1}-2a_{n-2}

is a linear recurrence relation.

Such recursions can often be solved explicitly. Consider

a_1=1, \qquad a_n=a_{n-1}+2.

The resulting sequence is

1,3,5,7,\ldots

and satisfies

a_n=2n-1.

Finding explicit formulas for recursively defined sequences is an important theme in number theory and discrete mathematics.

Recursive Structures in Number Theory

Many central objects in number theory possess recursive structure.

Prime factorization repeatedly breaks integers into smaller integers. Continued fractions are built recursively from quotients and remainders. Euclidean algorithms repeatedly reduce divisibility problems to smaller cases.

Even proofs often proceed recursively through induction or descent arguments.

This recursive viewpoint is fundamental because arithmetic itself is inherently discrete. Large integers are understood by reducing them to simpler integers, and recursive definitions formalize this process mathematically.