El principio de El principio de InducciónInducción

Lic. Clara GrinblatLic. Clara Grinblat

Partamos de un ejemploPartamos de un ejemplo

Ejemplo:Ejemplo:

Denótese por SDenótese por Snn=1+2+3+4+...+n =1+2+3+4+...+n Consideremos que se afirma que:Consideremos que se afirma que:

SSnn=n(n+1)/2 para n=1,2,... =n(n+1)/2 para n=1,2,... Se ha elaborado una sucesión de Se ha elaborado una sucesión de

proposiciones, a saberproposiciones, a saber

SS11=1(2)/2=1=1(2)/2=1

SS22=2(3)/2=3=1+2=2(3)/2=3=1+2

SS33=3(4)/2=6=1+2+3=3(4)/2=6=1+2+3

Continuamos con el Continuamos con el ejemplo….ejemplo….

Y podemos seguir escribiendo y verificando por Y podemos seguir escribiendo y verificando por ejemploejemplo

S(7)=7.8/2=28=1+2+3+4+5+6+7S(7)=7.8/2=28=1+2+3+4+5+6+7Esto no nos asegura que la forma de calcular la Esto no nos asegura que la forma de calcular la

suma sea cierta para todos los números suma sea cierta para todos los números naturales.naturales.

¿¿Cuándo una propiedad es cierta para todos los Cuándo una propiedad es cierta para todos los números naturales?números naturales?

Sabemos que para todo entero positivo n,Sabemos que para todo entero positivo n, n! ≤ nn! ≤ nnn.. La Inducción Matemática se usa para probar La Inducción Matemática se usa para probar

estos resultados:estos resultados:

Principio de inducciónPrincipio de inducción

Principio de inducciónPrincipio de inducción: Supóngase que se : Supóngase que se tiene una proposición P(n) para cada tiene una proposición P(n) para cada entero positivo n, consideremos:entero positivo n, consideremos:

a) Paso básicoa) Paso básico P(1) es verdaderaP(1) es verdadera, y, yb) Paso inductivob) Paso inductivo para todo número natural k, si P(k) espara todo número natural k, si P(k) esverdadera entonces P(k + 1) es verdadera.verdadera entonces P(k + 1) es verdadera.

Entonces la proposición P(n) es verdadera para todos los enteros positivos

Principio de inducción Principio de inducción (Formalizado)(Formalizado)

nP(n) 1)) P(k

(P(k)k P(1)

Si el primer dominó cae, y si cae un Si el primer dominó cae, y si cae un dominó entonces cae el siguiente,dominó entonces cae el siguiente,entonces todos los dominós caen.entonces todos los dominós caen.

Utilizando el principio de inducción vamos Utilizando el principio de inducción vamos

a probara probar que la suma de los n primeros que la suma de los n primeros números naturales es n (n+1)/2números naturales es n (n+1)/2

2

1)n(n j

nj

1j

Principio de inducción (continuación…)

Primero probamos que la propiedad se Primero probamos que la propiedad se cumple para 1 (cumple para 1 (paso básicopaso básico))

Se cumple en este caso pues 1 = 1(1+1)/2Se cumple en este caso pues 1 = 1(1+1)/2

Luego probamos el Luego probamos el paso inductivopaso inductivo: Si la : Si la propiedad se cumple en unpropiedad se cumple en un

numero k arbitrario numero k arbitrario (hipótesis inductiva(hipótesis inductiva) ) entonces también seentonces también se

cumple en k + 1.cumple en k + 1.

Principio de inducción (continuación…)

Sea k un entero positivo arbitrario. Por Sea k un entero positivo arbitrario. Por hipótesis inductiva:hipótesis inductiva:

k(k + 1)k(k + 1)1 + 2 + … + k =------------1 + 2 + … + k =------------ 22 Entonces,Entonces,1 + 2 + …. + k + (k + 1) =1 + 2 + …. + k + (k + 1) =k(k + 1)k(k + 1)---------- + (k + 1)=---------- + (k + 1)= 22

k(k + 1) + 2(k+ 1)k(k + 1) + 2(k+ 1)=-------------------------==-------------------------= 22

(k + 1)(k + 2)(k + 1)(k + 2)----------------- Entonces se concluye que----------------- Entonces se concluye que 22

2

1)n(n j

nj

1j

naturales los todosPara

La inducción también funciona si queremos probar algo para cada

entero n ≥ b. Ejemplo: Use inducción para demostrar que si a es Ejemplo: Use inducción para demostrar que si a es

distinto de 1, (Suma Geométrica).distinto de 1, (Suma Geométrica).

1+a1+a11+a+a22+...+a+...+ann=(a=(an+1n+1-1)/(a-1) (1)-1)/(a-1) (1)Paso BásicoPaso Básico: Se obtiene cuando n=0,: Se obtiene cuando n=0,1=(a1=(a11-1)/(a-1), lo cual es verdadero.-1)/(a-1), lo cual es verdadero.Paso InductivoPaso Inductivo:Supongamos que la proposición es :Supongamos que la proposición es verdadera para n. Ahoraverdadera para n. Ahora1+a1+a11+a+a22+...+a+...+ann+a+an+1 n+1 =(a=(an+1n+1-1)/(a-1)+a-1)/(a-1)+an+1n+1

=(a=(an+1n+1-1)/(a-1)+(a-1)/(a-1)+(an+1n+1(a-1))/(a-1)(a-1))/(a-1)=(a=(an+2n+2-1)/(a-1)-1)/(a-1)

Como el paso básico y el paso inductivo ya han sido Como el paso básico y el paso inductivo ya han sido verificados, el principio de inducción matemática verificados, el principio de inducción matemática establece que (1) es verdadera para n=0,1,2,...establece que (1) es verdadera para n=0,1,2,...

EJERCICIOEJERCICIO

Demostrar por inducción sobre n que Demostrar por inducción sobre n que

S(n)=(1+2+3+….+n)S(n)=(1+2+3+….+n)22 = 1 = 133+2+233+…+n+…+n33

S(1) es obviamente cierta; veamos que S(1) es obviamente cierta; veamos que se verifiquese verifique

S(k+1)= )=(1+2+3+….+k+(k+1))S(k+1)= )=(1+2+3+….+k+(k+1))22 = = 1133+2+233+…+k+…+k33 + (k+1) + (k+1)33

EJERCICIO (continuación…) EJERCICIO (continuación…) Por definición de S(k) se tiene que Por definición de S(k) se tiene que S(k+1)= (1+2+3+….+k+(k+1))S(k+1)= (1+2+3+….+k+(k+1))22

=(1+2+3+….+k)=(1+2+3+….+k)22 +2(1+2+3+….+k) +2(1+2+3+….+k)(k+1)+(k+1)(k+1)+(k+1)22 = =

=1=133+2+233+…+…+k+k33 +2(1+2+3+….+k)(k+1)+(k+1) +2(1+2+3+….+k)(k+1)+(k+1)22 por hipótesis inductivapor hipótesis inductiva

=1=133+2+233+…+…+k+k33 +(k+1) +(k+1)22+2.(K+1)k.(k+1)/2 por +2.(K+1)k.(k+1)/2 por resultado suma de los primeros k resultado suma de los primeros k naturalesnaturales

EJERCICIO (continuación…) EJERCICIO (continuación…)

=1=133+2+233+…+k+…+k3 3 +(k+1)+(k+1)22+(k+1)+(k+1)22k=k=

=1=133+2+233+…+k+…+k3 3 +(k+1)+(k+1)22.(1+k)=.(1+k)=

=1=133+2+233+…+k+…+k33 +(k+1) +(k+1)33

Con los pasos básicos e Inductivo se Con los pasos básicos e Inductivo se ha demostrado el enunciado.ha demostrado el enunciado.

n

1...

3

1

2

11H

n

122

2

2

2

1...

22

1

12

1H H

2

k1H

2

n1H queDemostrar

k1k

k

n

kkk

inductivaHipótesis

2

1

2

1.2

2

1...

22

1

12

111

k

k

kkk

Inducción en desigualdadesInducción en desigualdades

nn

H

kH

kH

n

k

k

2

1 inductivos e

básicos pasos los demostrado habiendo tantoloPor 2

11

precedente

expresióny inductiva hipótesispor 2

1

21

2

2

2

1

1

Inducción en desigualdadesInducción en desigualdades