R A M A A Z U L V I I I
METODO DE INDUCCION
La idea de inducción se puede ilustrar de la siguiente manera: imagi-
nemos fichas de dominó colocadas de pie de modo tal que si cae una ficha, se-
guro se cae la siguiente.
__ __ __ __ __
| | | | | | | | | |
| | | | | | . . . | | | |
| | | | | | | | | |
-- -- -- -- --
1 2 3 k k+1
Si se cae la ficha colocada en la posición k empuja y hace caer a la
ficha que está en la posición k+1.
Enseguida se intuye qué sucederá si la ficha colocada en la posición 1
se hace caer: caerán todas las fichas.
Si queremos probar que cierta propiedad P es verdadera para todo núme-
ro natural podemos considerar a los números naturales 1, 2, 3, 4, ... como fi-
chas de dominó. Si demostramos que si uno cualquiera de estos números tiene la
propiedad P, entonces también el número siguiente la tiene, y a continuación
comprobamos que el número 1 tiene la propiedad P, podemos concluir que todos
los números naturales tienen la propiedad P.
Básicamente, en esto consiste el Método de Inducción. Cuando usamos
este método de demostración hay dos cosas importantes que debemos probar:
(1) El número 1 tiene la propiedad P.
(2) Si k tiene la propiedad P entonces también k+1 tiene la propiedad P.
Veamos cómo funciona esta estrategia en algunos ejemplos.
* La suma de los n primeros números naturales impares es igual a n².
1 + 3 + 5 + ... + (2k-1) = k².
El número 1 tiene la propiedad, pues 1 = 1².
Supongamos que k tiene la propiedad, o sea
1 + 3 + 5 + ... + (2k-1) = k² (hipótesis inductiva).
La suma de los primeros k+1 impares es
1 + 3 + 5 + ... + (2k-1) + ( 2(k+1)-1).
Si usamos la hipótesis inductiva,
1 + 3 + 5 + ... + (2k-1)+(2(k+1)-1) = k²+ (2(k+1)-1) = k²+ 2k + 1 = (k+1)²
y por lo tanto k+1 tiene esa propiedad.
Repasemos el esquema de la demostración precedente:
- Primero comprobamos que la propiedad P era válida para k=1.
- Luego demostramos que si la propiedad P era cierta para k (hipótesis induc-
tiva) entonces era también cierta para k+1.
De estas dos cosas concluimos que la propiedad P es verdadera para todos los
números naturales.
* El conjunto {1, 2, ..., n} tiene 2ü subconjuntos.
Si n=1, los subconjuntos de {1} son 2: í y {1}.
k
Supongamos que {1, 2, ..., k} tiene 2 subconjuntos (hipótesis inductiva).
Consideramos {1, 2, ..., k+1}. Hay dos tipos de subconjuntos de{1, 2,...,k+1}:
los que tienen a k+1 y los que no lo tienen.
Los del segundo tipo son los subconjuntos de {1, 2, ..., k}, y por la hipóte-
k
sis inductiva son en total 2 .
Los del primer tipo resultan de agregarle k+1 a cada subconjunto de
k
{1, 2,... k} y por lo tanto son también 2
k k k+1
Sumando los conjuntos de los dos tipos, tenemos 2 + 2 = 2 subconjuntos de
{1, 2, ..., k+1}.
PROBLEMA 1: Una desigualdad
Demostrar que si a>0 y b>0, entonces para todo n_1 se verifica:
n n n-1
(n-1) a + b _ n a b.
PROBLEMA 2: Muchos múltiplos de 7.
2n+2 n+1
Probar que para todo n entero positivo, 3 - 2 es divisible por 7.,
_
PROBLEMA 3: Construyendo ¹n. _
Probar que es posible construir ¹n con regla y compás para todo n î N.
PROBLEMA 4:
i) Probar que n rectas distintas de un plano que concurren en un punto
dividen al plano en............(completar y demostrar).
ii) Calcular el número de regiones en que el plano es dividido por n
rectas entre las cuales no hay dos paralelas ni tres concurrentes.
