# Recursive Definitions

## Definitions by Recursion

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

1. one or more initial values,
2. 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.