1

Induccin matemtica

Introduccin

En los teoremas pueden distinguirse dos diferentes mtodos de prueba, el llamado directo y el indirecto. En el mtodo directo de prueba, procedemos de la hiptesis a la conclusin a travs de una serie de deducciones cada una de las cuales esta justificada por algn axioma o por algn teorema previamente probado. En las pruebas indirectas, comenzamos por suponer que la conclucion no es cierta a continuacin, a travs de una serie de deducciones, obtenemos una proposicin que contradice la hiptesis del teorema. Luego, bajo la hiptesis, la conclusin del teorema no puede ser falsa y debe, por tanto, ser cierta.

Si el teorema es una proposicin que ha de verificarse para todos los nmeros enteros positivos entonces es a menudo posible construir una prueba basada sobre un principio llamado de induccin matemtica.

Principio de Induccin Matemtica

Suponemos que los enteros positivos poseen la siguiente propiedad, llamada principio del buen orden. Todo conjunto no nulo de enteros positivos posee un elemento mnimo Por ejemplo, el entero mnimo en el conjunto de todos los enteros positivos pares es 2 y el entero mnimo en el conjunto de todos los enteros positivos impares es 1.

Usando el principio del buen orden, podemos probar:

Teorema: (Principio de induccin) Cualquier conjunto S de enteros positivos que

1. contiene a 1 y

2. contiene a m+1 siempre que contiene a m

es el conjunto de todos los enteros positivos.

2

Prueba Sea NS el conjunto de todos los enteros positivos que no estn en S. Se desea mostrar que NS es el conjunto nulo. Suponga que NS no es nulo, entonces por el principio del buen orden NS tiene un elemento mnimo; llammosle b. Como 1S; b 1. Luego b -1 es un entero positivo. Pero b -1 < b (mnimo de NS), entonces b -1 S. Pero entonces, (b-1)+1S, es decir bS, lo cual es absurdo pues bNS. Este resultado se debe a la suposicin que NS es no nulo. Por consiguiente NS es nulo; es decir, S es el conjunto de todos los enteros positivos.

Ejemplo 1 Pruebe que si 0 1x< < y n es un entero positivo cualquiera, 0 1nx< < .

Prueba

Sea S el conjunto de todos los enteros positivos n tales que 0 1nx< < Por el Principio de induccin:

1) Para n =1S se tiene 0 1x< < , lo cual es cierto por hiptesis. 2) Supongamos que para un n m= cualesquiera se cumple: 0 1mx< < 3) Probamos que se cumple tambin para el entero siguiente, para 1n m= +

10 1.1 1m mx x x+< = < = , entonces 10 1mx +< <

Ejemplo 2 Pruebe que para cualquier nmero real 1p y cualquier entero positivo n,

(1 ) 1np np+ + Prueba

Sea S el conjunto de todos los enteros positivos n para los cuales (1 ) 1np np+ + Por el Principio de induccin:

1) Para n =1S se cumple 1(1 ) 1 1. 1p p p+ + = + 2) Supongamos que para un n m= cualesquiera se cumple: (1 ) 1mp mp+ + 3) Probamos que se cumple tambin para el entero siguiente, para 1n m= +

( )1(1 ) (1 ) .(1 ) 1 (1 )m mp p p mp p++ = + + + + por paso 2 21 1 ( 1)p mp mp m p= + + + + +

Por tanto, podemos concluir que + se cumple (1 ) 1np np+ + .

3

Principio de Induccin Matemtica

Ejemplo 3

Demuestre que si n es un entero positivo cualquiera entonces 31 ( 2 )3

n n+ es un entero.

Demostracin

Sea S el conjunto de todos los enteros positivos n tales que 31 ( 2 )3

n n+ es un entero.

Por el Principio de induccin:

1) 1S ya que 1 (1 2) 13

+ =

2) Supongamos que para un n m= cualesquiera se cumple: 31 ( 2 )3

n n+

3) Probamos que se cumple tambin para el entero siguiente, para 1n m= + por paso 2

( )3 3 21 1( 1) 2( 1) 3 3 1 2 23 3m m m m m m + + + = + + + + + ( )3 21 2 13 m m m m+ + + + Por tanto, podemos concluir que ( )3 21 2 13 m m m m+ + + + es un entero.

Ejercicios 1. Si n es un entero positivo, muestre que ( 1)

2n n +

es un nmero entero.

2. Si n es un entero positivo, muestre que 3 23 2

3n n n+ +

es un nmero entero.

3. Si n es un entero positivo, muestre que 3 23 3

6n n n+ +

es un nmero entero.

4. Si n es un entero positivo, muestre que 4 3 22

4n n n+ +

es un nmero entero.

5. Pruebe que para cualquier nmero real 0p y cualquier entero positivo n;

( )2( 1)1 1

2n n n pp np + + + .

4

Sumas Finitas

Definicin: Si n es un entero positivo y 1 2, , ... na a a son nmeros, entonces

1 21

...

n

k nk

a a a a=

= + + +

1

n

kk

a=

se lee la suma de ka desde 1k = hasta k n=

( es la sigma mayscula, la letra griega correspondiente a S )

Ejemplo

La adicin de los primeros n enteros puede escribirse: 1

1 2 ...n

kn k

=

+ + + =

Y la suma de los primeros n enteros: 1

( 1)2

n

n

k

n nS k=

+= =

La prueba de la validez de esta frmula puede realizarse usando la induccin

matemtica.

Propiedades de 1

n

kk

a=

Para cualquier entero positivo n se cumplen:

1. 11 1

n n

k n kk k

a a +

= =

=

( ) ( )1 2 3 ... 2 1 ( 1) ( 2) ... 3 2 1n n n n n n+ + + + + + = + + + + + + Cada miembro de la igualdad tienen los mismos trminos pero el orden en que estn escritas es el inverso.

2. 1 1

n n

k kk k

ca c a= =

= ; donde c es una constante

En efecto: ( )1 2 3 1 2 3... ...n nca ca ca ca c a a a a+ + + + = + + + +

3. ( )1 1 1

n n n

k k k kk k k

a b a b= = =

+ = +

En efecto: ( ) ( )1 1 2 2 1 2 1 2... ... ...n n n na b a b a b a a a b b b+ + + + + + = + + + + + + +

5

4. 1

n

kc n c

=

= ; c es contante

En efecto: ...c c c c n c+ + + + = ( n sumandos)

5. ( )1 01

n

k k nk

a a a a

=

=

Justificacin:

1 1 1

1 0 01 1 1 0 1 1

n n n n n n

k k k k n k k nk k k k k k

a a a a a a a a a a

= = = = = =

= = + =

Usando la propiedad 5. y considerando 2ka k= y 2

0 0a = se tiene la frmula de la

suma de los n primeros nmeros enteros positivos.

( )( )22 2 21

1 0n

kk k n

=

= ( ) 21

2 1n

kk n

=

=

2

1 12 1

n n

k kk n

= =

=

2

12

n

kk n n

=

=

( )21

12 2

n

k

n nn nk=

++= =

En forma anloga se obtiene: ( )2 3 21

1 2 36

n

kk n n n

=

= + + ; cuando 3ka k= y 30 0a =

En efecto:

( )( )33 31

1n

kk k n

=

= ( )2 31

3 3 1n

kk k n

=

+ =

2 3

1 1 13 3 1

n n n

k k kk k n

= = =

+ =

22 3

13 3

2

n

k

n nk n n=

+ + =

Despejando 21

n

kk

=

se tiene: ( )2 3 21

1 2 36

n

kk n n n

=

= + +

Bibliografa HASSER, LASALLE, SULLIVAN; Anlisis matemtico, Cap.7. Pag.315. Editorial Trillas. Mexico, 1974.