Definiciones por recurrencia

Muchas veces, para definir una función f : IN $\rightarrow$ A, se hace uso implícito del principio de inducción. Por ejemplo, cuando se define

aⁿ = a^.a^{. ... .}a (n veces),
realmente se está pensando en la definición: a⁰ = 1, a^{n + 1} = a^{n .}a. Esto define a⁰, y asumiendo que aⁿ está definido, permite definir a^{n + 1}. El principio de inducción garantiza que esta es una buena definición de la función

f : IN $\displaystyle \rightarrow$ IR, f (n) = aⁿ.
En lo que sigue hacemos uso de este principio.

Ejemplo 2.3.8 (El factorial) Se define 0! = 1, y para n $\in$ IN, (n + 1)! = (n + 1)^.n!. Tenemos entonces 1! = 1^.0! = 1, 2! = 2^.1! = 2^.1, 3! = 3^.2^.1, y en general n! = n^.(n - 1)^...3^.2^.1.

Ejemplo 2.3.9 Dada una función f : IN $\rightarrow$ IR, podemos definir la suma

S_n = f (0) +...+ f (n)
inductivamente así:

S₀ = f (0), S_{n + 1} = S_n + f (n + 1).
A veces se usa la notación a_k = f (k), obteniendo

S_n = a₀ +...+ a_n,
que también se denota por

S_n = $\displaystyle \sum_{k=0}^{n}$ a_k.
Note que por definición se tiene

$\displaystyle \sum_{k=0}^{n+1}$ a_k = $\displaystyle \sum_{k=0}^{n}$ a_k + a_{n + 1}.
Si se comienza en 1, se denota

$\displaystyle \sum_{k=1}^{n}$ a_k = a₁ +...+ a_n.

Ejemplo 2.3.10 Un caso particular del ejemplo anterior es la suma

$\displaystyle \sum_{k=1}^{n}$ k = $\displaystyle {\frac{n(n+1)}{2}}$ ,
que estudiamos anteriormente.

Ejemplo 2.3.11 Demostrar que

$\displaystyle \sum_{k=0}^{n}$ k^.k! = (n + 1)! - 1, $\displaystyle \forall$ n $\displaystyle \in$ IN.
Para n = 0 la suma del lado izquierdo es 0^.0! = 0, mientras que al lado derecho tenemos (0 + 1)! - 1 = 0. Entonces la igualdad es válida para n = 0.
Supongamos que la igualdad es válida para n, y probémosla para n + 1. Tenemos

$\displaystyle \sum_{k=0}^{n+1}$ k^.k! = $\displaystyle \sum_{k=0}^{n}$ k^.k! + (n + 1)^.(n + 1)!,
y por hipótesis de inducción se sigue que

$\sum_{k=0}^{n+1}$ k^.k! = (n + 1)! - 1 + (n + 1)^.(n + 1)!

= (1 + n + 1)(n + 1)! - 1

= (n + 2)(n + 1)! - 1

= (n + 2)! - 1.

Esto demuestra la igualdad para n + 1, y por el principio de inducción se sigue que es válida para todo n $\in$ IN.

Ejemplo 2.3.12 Demostrar que 2ⁿ < n!, para todo n $\geq$ 4.
Para n = 4 tenemos 2⁴ = 16 < 24 = 4!. Ahora supongamos que 2ⁿ < n! para algún n $\geq$ 4. Entonces

2^{n + 1} = 2^.2ⁿ < 2^.n! < (n + 1)^.n! = (n + 1)!,
con lo que n + 1 también satisface la desigualdad. El principio de inducción se encarga del resto.

$\sum_{k=0}^{n+1}$ k^.k!	= (n + 1)! - 1 + (n + 1)^.(n + 1)!
	= (1 + n + 1)(n + 1)! - 1
	= (n + 2)(n + 1)! - 1
	= (n + 2)! - 1.