Recursive Formula
Functions & Advanced AlgebraA recursive formula defines each term of a sequence using one or more previous terms, along with a starting value.
Definition
A recursive formula tells you how to find the next term using the term before it. You always start with a given first term and build from there.
Example
$a_1 = 3$, $a_{n+1} = a_n + 5$. Start: $3$. Next: $3 + 5 = 8$. Next: $8 + 5 = 13$. Next: $13 + 5 = 18$. This generates $3, 8, 13, 18, \ldots$
Key Insight
Recursive means "defined in terms of itself." You need a starting point (the first term) and a rule to step forward. Without the first term, you cannot begin.
Definition
A recursive formula defines $a_n$ in terms of one or more previous terms. Arithmetic: $a_n = a_{n-1} + d$. Geometric: $a_n = r \cdot a_{n-1}$. The Fibonacci sequence uses two previous terms: $a_n = a_{n-1} + a_{n-2}$, $a_1 = 1$, $a_2 = 1$.
Example
Geometric recursive formula: $a_1 = 5$, $a_n = 3 \cdot a_{n-1}$. Terms: $5, 15, 45, 135, 405, \ldots$ To find $a_{10}$ recursively requires computing all previous terms, unlike the explicit formula.
Key Insight
Recursive formulas are often simpler to write but require computing every previous term to find a specific term. Explicit formulas are more efficient for large n but sometimes harder to derive.
Definition
A recursive formula defines a sequence via a recurrence relation $a_n = F(a_{n-1}, \ldots, a_{n-k})$ with $k$ initial conditions. Linear recurrences with constant coefficients (like the Fibonacci recurrence) can be solved in closed form using the characteristic polynomial. If $r_1, \ldots, r_k$ are distinct roots of the characteristic equation, the general solution is $a_n = \sum C_i r_i^n$.
Example
Fibonacci: $a_n = a_{n-1} + a_{n-2}$. Characteristic equation: $x^2 = x + 1$, roots $\phi = (1 + \sqrt{5})/2$ and $\psi = (1 - \sqrt{5})/2$. Binet's formula: $a_n = (\phi^n - \psi^n) / \sqrt{5}$.
Key Insight
The connection between linear recurrences and characteristic polynomials mirrors the connection between linear ODEs and their characteristic equations, revealing a deep structural parallel between discrete and continuous mathematics.