Inicio  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 

Inducción y buen orden

Una manera de iniciar el estudio de los números naturales es comenzar con los axiomas de Peano, que incluyen el principio de inducción. Si se está familiarizado con los números reales, se puede definir el conjunto IN de los números naturales como el menor subconjunto inductivo de IR. Aquí nos contentaremos con enunciar el principio de inducción como axioma.

Definición 2.3.1   Un conjunto A $\subseteq$ IR se llama inductivo si satisface:

(a)

0 $\in$ A.

(b)

Para todo n $\in$ A se tiene n + 1 $\in$ A.

Por ejemplo, A = [0,$\infty$[ es inductivo, lo mismo que IN y IZ. El conjunto

B = $$\left\{\vphantom{ n\in I\!\! N:2^{n}\geq n^{2}}\right.$$n $$\in$$ IN : 2ⁿ n²$$\left.\vphantom{ n\in I\!\! N:2^{n}\geq n^{2}}\right\}$$

no es inductivo, pues contiene a n = 2, pero no contiene a 2 + 1 = 3.

Principio de inducción (Versión 1) IN es el menor subconjunto inductivo de IR.

Así, si A $\subseteq$ IN es inductivo, debe tenerse A = IN. Podemos entonces escribir el principio en la forma alternativa:

Principio de inducción (Versión 2) Si A $\subseteq$ IN satisface la propiedades (a) y (b), entonces A = IN.

Ejemplo 2.3.1   Demostrar que 2ⁿ $\geq$ n + 1, para todo n $\in$ IN.

Definimos el conjunto

A : = $$\left\{\vphantom{ n\in I\!\! N:2^{n}\geq n+1}\right.$$n $$\in$$ IN : 2ⁿ $$\geq$$ n + 1$$\left.\vphantom{ n\in I\!\! N:2^{n}\geq n+1}\right\}$$.

Observe que 0 $\in$ A, pues 2⁰ = 1 $\geq$ 0 + 1.

Ahora, si n $\in$ A tenemos 2ⁿ $\geq$ n + 1. Entonces

2^{n + 1} = 2 ^. 2ⁿ $$\geq$$ 2$$\left(\vphantom{ n+1}\right.$$n + 1$$\left.\vphantom{ n+1}\right)$$ = 2n + 2 $$\geq$$ n + 2,

así que n + 1 $\in$ A. Esto demuestra que A es inductivo, y por el principio de inducción se concluye que A = IN. La desigualdad es válida entonces para todo n $\in$ IN.

Ejemplo 2.3.2   Demostrar que para todo n $\in$ IN se tiene

0 + 1 + ^... + n = $${\frac{n(n+1)}{2}}$$.

Se trata de demostrar que el conjunto

A : = $$\left\{\vphantom{ n\in I\!\! N:0+\cdots+n=\frac{n(n+1)}{2}}\right.$$n $$\in$$ IN : 0 + ^... + n = $${\frac{n(n+1)}{2}}$$$$\left.\vphantom{ n\in I\!\! N:0+\cdots+n=\frac{n(n+1)}{2}}\right\}$$

es igual a IIN, para lo cual basta demostrar que es inductivo.

Para n = 0, la suma del lado izquierdo solo tiene un término, y es igual a 0, mientras que el lado derecho es ${\frac{0(0+1)}{2}}$ = 0. Entonces 0 $\in$ A.

Si n $\in$ A, entonces tenemos que

0 + ^... + n = $${\frac{n(n+1)}{2}}$$,

y debemos demostrar que n + 1 $\in$ A. Veamos:

$$\begin{array}[c]{ccc}%% 0+1+\cdots+(n+1) & = & \left( 0+\cdots+n\... ...& \frac{n(n+1)+2(n+1)}{2}\smallskip\\ & = & \frac{(n+1)(n+2)}{2}, \end{array}$$

de donde n + 1 $\in$ A. Por el principio de inducción concluimos que A = IN.

Nota: En la práctica no se scodtumbra definir el conjunto A explícitamente, sino que se demuestra la propiedad planteada para n = 0, y luego se demuestra que si se cumple para n, debe cumplirse para n + 1.

Ejemplo 2.3.3   Demostrar que n³ + 5n es divisible por 6, para todo n $\in$ IN.

En efecto, para n = 0 tenemos n³ + 5n = 0, el cual es divisible por 6.

Si n³ + 5n es divisible por 6, tenemos n³ + 5n = 6k, para algún k $\in$ IN. Luego

$$\left(\vphantom{ n+1}\right.$$n + 1$$\left.\vphantom{ n+1}\right)^{3}_{}$$ + 5$$\left(\vphantom{ n+1}\right.$$n + 1$$\left.\vphantom{ n+1}\right)$$ = $$\left(\vphantom{ n^{3}+5n}\right.$$n³ + 5n$$\left.\vphantom{ n^{3}+5n}\right)$$ + 3n² + 3n + 6
= 6k + 3n(n + 1) + 6
= 6(k + 1) + 3n(n + 1).

Como n$\left(\vphantom{ n+1}\right.$n + 1$\left.\vphantom{ n+1}\right)$ es siempre par (¿por qué?), tenemos que 3n$\left(\vphantom{ n+1}\right.$n + 1$\left.\vphantom{ n+1}\right)$ es múltiplo de 6, y consecuentemente $\left(\vphantom{ n+1}\right.$n + 1$\left.\vphantom{ n+1}\right)^{3}_{}$ + 5$\left(\vphantom{ n+1}\right.$n + 1$\left.\vphantom{ n+1}\right)$ lo es.

El principio de inducción también es aplicable a propiedades que son válidas a partir de cierto valor de n. Veamos el siguiente resultado, que llamaremos inducción truncada.

Lema 2.3.1   (Inducción truncada) Sea A $\subseteq$ IN, y sea N $\in$ IN tales que

(a) N $\in$ A.

(b) Para todo n $\in$ A tal que n $\geq$ N, se tiene n + 1 $\in$ A.

Entonces A contiene todos los naturales a partir de N. Esto es:

{n $$\in$$ IN : n $$\geq$$ N} $$\subseteq$$ A.

Prueba:

Si N = 0, el resultado es precisamente el principio de inducción.

Si N > 0 considere el conjunto

B = A $$\cup$$ {0, 1,..., N - 1}.

Entonces claramente B es inductivo, y por el principio de inducción se concluye que B = IN. Ahora, dado  n $\geq$ N, tenemos que n $\in$ B, y n$\notin${0, 1,..., N - 1}, de donde concluimos que n $\in$ A.

Veamos algunos ejemplos donde se aplica este resultado:

Ejemplo 2.3.4   Demostrar que n + 3 < 2ⁿ, para todo n $\geq$ 3.

Note que en este caso la desigualdad es falsa para n = 0, 1, 2. Para n = 3 sí es válida pues tenemos 3 + 3 = 6 < 2³ = 8. Ahora, si se cumple para cierto n $\geq$ 3, tenemos n + 3 < 2ⁿ, y luego

(n + 1) + 3 = (n + 3) + 1 < 2ⁿ + 1 < 2ⁿ + 2ⁿ = 2^{n + 1}.

Entonces también se cumple para n + 1. Luego, por inducción truncada la desigualdad es válida para todo n $\geq$ 3.

Ejemplo 2.3.5   Demostrar que n² $\leq$ 2ⁿ, para todo n $\geq$ 4.

Note que aunque la desigualdad es válida para n = 1 y n = 2, no lo es para n = 3. Para n = 4 tenemos 4² = 16 = 2⁴, así que se cumple 4² $\leq$ 2⁴.

Ahora supongamos que se cumple para algún n $\geq$ 4, esto es n² $\leq$ 2ⁿ. Entonces

2^{n + 1} = 2 ^. 2ⁿ $$\geq$$ 2n².

Para demostrar la desigualdad para n + 1 basta con demostrar que 2n² $\geq$ (n + 1)², lo cual es equivalente a n² - 2n - 1 $\geq$ 0. Esto es cierto para n $\geq$ 4, pues

n² - 2n - 1 = n(n - 2) - 1 $$\geq$$ 4 ^. 2 - 1 = 7 > 0.

Esto demuestra entonces que 2n² $\geq$ (n + 1)², y luego

2^{n + 1} $$\geq$$ 2n² $$\geq$$ (n + 1)².

En algunos ejemplos, al demostrar que n + 1 $\in$ A, se debe hacer uso no solo del hecho que n $\in$ A, sino también de que n - 1 $\in$ A, o en general de que k $\in$ A para k $\leq$ n. El siguiente resultado permite hacer este tipo de razonamientos.

Lema 2.3.2   (Inducción completa) Sea A $\subset$ IN que satisface

(a)

0 $\in$ A.

(b)

Si k $\in$ A para todo k $\leq$ n, entonces n + 1 $\in$ A.

Entonces A = IN.

Prueba

Defina el conjunto

B = $$\left\{\vphantom{ n\in I\!\! N:k\in A\mbox{ para todo }k\leq n}\right.$$n $$\in$$ IN : k $$\in$$ A para todo k $$\leq$$ n$$\left.\vphantom{ n\in I\!\! N:k\in A\mbox{ para todo }k\leq n}\right\}$$.

Entonces B $\subseteq$ A, y por la propiedad (a) tenemos que 0 $\in$ B. Por otro lado, supongamos que n $\in$ B. Entonces por definición tenemos que k $\in$ A para todo k $\leq$ n, y por la propiedad (b) se tiene n + 1 $\in$ A. Consecuentemente

k $$\in$$ A para todo k $$\leq$$ n + 1,

lo que significa n + 1 $\in$ B. Por el principio de inducción se sigue que B = IN. Finalmente tenemos IN = B $\subseteq$ A, y por lo tanto A = IN.

Otra propiedad importante de los números naturales es el principio del buen orden . Como veremos, este principio es equivalente al principio de inducción. Para establecerlo necesitamos primero la siguiente definición.

Definición 2.3.2   Dado A $\subset$ IN, decimos que n₀ es el primer elemento de A si satisface:

1. n₀ $\in$ A.

2. n₀ $\leq$ n, $\forall$n $\in$ A.

El lector puede demostrar que de existir el primer elemento, este debe ser único. Note que 0 es el primer elemento de IN. Dado A $\subseteq$ IN, si 0 $\in$ A se sigue inmediatamente que 0 es el primer elemento de A.

Lema 2.3.3 (Principio del buen orden)   Si A es un subconjunto no vacío de IN, entonces A tiene primer elemento.

Prueba

Suponga que A no tiene primer elemento, y defina

B = IN - A = $$\left\{\vphantom{ n\in I\!\! N:n\notin A}\right.$$n $$\in$$ IN : n$$\notin$$A$$\left.\vphantom{ n\in I\!\! N:n\notin A}\right\}$$.

Tenemos que 0 $\in$ B, pues de lo contrario 0 sería el primer elemento de A. Ahora, si k $\in$ B para todo k $\leq$ n, entonces n + 1 $\in$ B, pues de lo contrario n + 1 sería el primer elemento de A.

Por el principio de inducción completa se sigue que B = IN, y consecuentemente A = $\emptyset$. Como esto contradice la hipótesis, A debe tener primer elemento.

Como una aplicación de este hecho, demostremos que todo número real tiene parte entera.

Ejemplo 2.3.6   (Parte entera) Sea x $\in$ IR. Entonces existe m $\in$ IZ tal que

m $$\leq$$ x < m + 1.

En efecto, sea x > 0. Por arquimedianidad, existe n $\in$ IN tal que n > x. Esto quiere decir que el conjunto

A = $$\left\{\vphantom{ k\in I\!\! N:k>x}\right.$$k $$\in$$ IN : k > x$$\left.\vphantom{ k\in I\!\! N:k>x}\right\}$$

es no vacío, y por lo tanto tiene primer elemento, el cual llamaremos n₀. Entonces tenemos que n₀ $\in$ A y n₀ - 1$\notin$A, lo cual implica

n₀ - 1 $$\leq$$ x < n₀.

Tomando m = n₀ - 1 obtenemos el resultado.

Si x < 0, se aplica lo anterior a - x y luego se multiplica por -1.

Nota: El lector puede convencerse de que m es único para x. Tal m se llama la parte entera de x, y se denota m = $\left[\vphantom{ x}\right.$x$\left.\vphantom{ x}\right]$.

Ejemplo 2.3.7   (Algoritmo de la división) Para a y b naturales, con b > 0, existen q y r tales que

a = bq + r,  0 $$\leq$$ r < b.

La idea es comenzar en el origen, ``pegando brincos'' de longitud b, hasta caer a la derecha de a. Entonces q es el mayor natural que cumple qb $\leq$ a. Basta entonces con tomar q = $\left[\vphantom{ \frac{a}{b}}\right.$${\frac{a}{b}}$$\left.\vphantom{ \frac{a}{b}}\right]$. Tenemos

q $$\leq$$ $${\frac{a}{b}}$$ < q + 1,

lo cual implica qb $\leq$ a < qb + b. Luego 0 $\leq$ a - bq < b, y tomamos r = a - bq.

Visto de otra forma, q = k₀ - 1, donde k₀ es el primer elemento del conjunto

A : = $$\left\{\vphantom{ k\in I\!\! N:kb>a}\right.$$k $$\in$$ IN : kb > a$$\left.\vphantom{ k\in I\!\! N:kb>a}\right\}$$.

Por ejemplo, si a = 145 y b = 15, tenemos a = b ^. 9 + 10, así que q = 9 y r = 10.

Inicio  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28