Recursión

Un ejemplo de conjunto definido de forma recurrente es el de los números naturales, es decir, el conjunto de los números enteros no negativos:[2]

1. ${\displaystyle 0\,}$ pertenece a ℕ.
2. Si ${\displaystyle n\,}$ pertenece a ℕ, entonces ${\displaystyle n+1\,}$ pertenece a ℕ.
3. Si ${\displaystyle x\,}$ verifica las anteriores condiciones, entonces ${\displaystyle x\,}$ está incluido en ℕ ^{[cita requerida]}.

Aquellas funciones cuyo dominio es un conjunto a lo más enumerable [3] pueden ser definidas de forma recurrente.

Un ejemplo conocido es la definición recurrente de la función factorial n!:

${\displaystyle n!={\begin{cases}{\mbox{si }}n=0&\Rightarrow 1\\{\mbox{si }}n\geq 1&\Rightarrow n\;(n-1)!\end{cases}}}$

Veamos cómo se usa esta definición para hallar el valor del factorial de 3:

${\displaystyle {\begin{aligned}3!&=3\cdot (3-1)!\\{}&=3\cdot 2!\\{}&=3\cdot 2\cdot (2-1)!\\{}&=3\cdot 2\cdot 1!\\{}&=3\cdot 2\cdot 1\cdot (1-1)!\\{}&=3\cdot 2\cdot 1\cdot 0!\\{}&=3\cdot 2\cdot 1\cdot 1\\{}&=6\\\end{aligned}}}$

Otros ejemplos de funciones y sucesiones matemáticas definidas de forma recursiva son:

• Sucesión de Fibonacci — f(0)= 1, f(1) = 1; f(n) = f(n-1) + f(n-2) para n ≥ 2.
• Números de Catalan — C(2n, n)/(n+1)
• Función de Ackermann

La razón áurea se puede definir de forma recursiva, como una fracción continua en que todos los números son unos:

${\displaystyle \phi =1+{\frac {1}{\phi }}=1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+...}}}}}}}$.

De forma similar, la identidad ${\displaystyle {\sqrt {x}}=1+{\frac {x-1}{1+{\sqrt {x}}}}}$ da lugar a una definición como fracción continua de cualquier raíz cuadrada:[4]

${\displaystyle {\sqrt {x}}=1+{\cfrac {x-1}{2+{\cfrac {x-1}{2+{\cfrac {x-1}{2+{\ddots }}}}}}}}$

Resolución de ecuaciones homogéneas de primer grado, segundo orden:

a) Se pasan al primer miembro los términos ${\displaystyle a_{n}}$, ${\displaystyle a_{n-1}}$, ${\displaystyle a_{n-2}}$, los cuales también podrían figurar como ${\displaystyle a_{n+2}}$, ${\displaystyle a_{n+1}}$, ${\displaystyle a_{n}}$

b) Se reemplaza ${\displaystyle a_{n}}$ por ${\displaystyle r^{2}}$, ${\displaystyle a_{n-1}}$ por ${\displaystyle r}$ y ${\displaystyle a_{n-2}}$ por ${\displaystyle 1}$, quedando una ecuación de segundo grado con raíces reales y distintas ${\displaystyle r_{1}}$ y ${\displaystyle r_{2}}$.

c) Se plantea ${\displaystyle a=u\;r_{1}n+v\;r_{2}n}$

d) Debemos tener como dato los valores de los dos primeros términos de la sucesión: ${\displaystyle A_{0}=k\,}$ y ${\displaystyle A_{1}=k^{\prime }}$. Utilizando estos datos ordenamos el sistema de 2x2:

${\displaystyle {\begin{cases}u+v=k\\u\;r_{1}+u\;r_{2}=k^{\prime }\end{cases}}}$

La resolución de este sistema nos da como resultado los valores ${\displaystyle u_{0}}$ y ${\displaystyle v_{0}}$, que son números reales conocidos.

e) La solución general es:

${\displaystyle a_{n}=u_{0}\;r_{1}n+v_{0}\;r_{2}n}$