araceli guzm an y guillermo garro · 2017. 8. 1. · 1.carmen g omez laveaga, algebra superior ,...

Induccion Matematica

Algebra

Araceli Guzman y Guillermo Garro

Facultad de CienciasUNAM

Semestre 2018-1

doyouwantmektalwar.wordpress.com

Principio de induccion Matematica Algebra

Referencias

1. Bulajich, Gomez, Valdez, Topics in algebra and analysis, 2015. Bajar aquı

2. Bulajich, Gomez, Valdez, Algebra, 2016.

3. I. S. Sominskii, El metodo de la Induccion Matematica, 1990. Bajar aquı.

Otras referencias:

1. Carmen Gomez Laveaga, Algebra Superior, 2014. Bajar aquı.

2. A. Bravo, H. Rincon, C. Rincon, Algebra Superior, 2006. Bajar aquı.

Araceli Guzman y Guillermo Garro doyouwantmektalwar.wordpress.com Facultad de Ciencias UNAM

https://drive.google.com/file/d/0B12efZWbDYZbRkpIeTh0enpNRGc/view?usp=sharing

https://www.scribd.com/doc/133460368/Metodo-de-Induccion-Matematica-Sominski-1975

https://es.scribd.com/document/342373161/Carmen-Gomez-Laveaga-Algebra-Superior-Curso-Completo

https://es.scribd.com/document/249209475/Algebra-Superior-Bravo-Rincon-Rincon


Principio de Induccion Matematica

Si P (x) es una propiedad referida a numeros naturales x, tal que

PI-1: Base de Induccion. P (1) es verdadera (o bien, P (0) es verdadera, siconsideramos 0 ∈ N).

PI-2: Paso Inductivo. La afirmacion

P (n)⇒ P (n+ 1) (o bien P (n− 1)⇒ P (n))

es verdadera.

Entonces P (n) es verdadera para toda n ∈ N,



Ejemplo (Formula del nino Gauss)

Probar que la indentidad

1 + 2 + 3 + · · ·+ n =n(n+ 1)

2

es validad para todo n ≥ 1.

Solucion.

PI-1. Si n = 1 tenemos

1 =1(1 + 1)

2.

Ası que la formula es valida para n = 1.





1 + 2 + 3 + · · ·+ n =n(n+ 1)

2


Solucion.

PI-2. Supongamos que la formula es valida para n –esto generalmente se conoce comoHipotesis de Induccion (HI). Es decir, supongamos que

1 + 2 + 3 + · · ·+ n =n(n+ 1)

2.

Queremos probar a partir de aquı que la formula es valida para n+1. Es decir, queremosprobar la identidad

1 + 2 + 3 + · · ·+ n+ (n+ 1) =(n+ 1)(n+ 2)

2.





1 + 2 + 3 + · · ·+ n =n(n+ 1)

2


Solucion.

PI-2. Tenemos,

1 + 2 + 3 + · · ·+ n+ (n+ 1) = (1 + 2 + 3 + · · ·+ n) + (n+ 1) – agrupamos los n primeros terminos.

=n(n+ 1)

2+ (n+ 1) – HI

= (n+ 1)(n

2+ 1

)=

(n+ 1)(n+ 2)

2.

Como querıamos probar.



Ejemplo

Prueba que n(n+ 1) es par para toda n ≥ 1.

Solucion.

PI-1. Si n = 1,n(n+ 1) = 1(1 + 1) = 2.

Ası que se cumple para n = 1.

PI-2. Supongamos que n(n+1) es par, es decir, que n(n+ 1) = 2k para algun enterok (HI). Queremos probar que (n+ 1)((n+ 1) + 1) = (n+ 1)(n+ 2) es par. Tenemos,

(n+ 1)(n+ 2) = n(n+ 1) + 2n = 2k + 2n = 2(k + n).

De modo que (n+ 1)(n+ 2) es par, como querıamos probar.



Ejemplo

Demostrar que n3 − n es un multiplo de 6 para toda n ≥ 0.

Solucion.

PI-1. Si n = 0, entoncesn3 − n = 0 = 6 · 0.

Por lo que la afirmacion es valida para n = 0.

PI-2. Supongamos ahora que n3−n es multiplio de 6, esto es, n3−n = 6k para algunentero k (HI). Queremos probar que (n+ 1)3 − (n+ 1) es multiplo de 6. Tenemos,

(n+ 1)3 − (n+ 1) = n3 + 3n2 + 3n+ 1− n− 1

= (n3 − n) + 3(n2 + n)

= 6k + 3n(n+ 1).

Pero n(n+ 1) = 2k para algun k′, por lo que

(n+ 1)3 − (n+ 1) = 6k + 3n(n+ 1)

= 6(k + k′).

Ası que (n+ 1)3 − (n+ 1) es multiplo de 6, como querıamos probar.



Ejemplo

Encontrar el valor de la suma

Sn =1

1 · 2+

1

2 · 3+

1

3 · 4+ · · ·+

1

n(n+ 1),

para cada n ≥ 1.

Solucion.

Primero enumeramos los primeros valores de esta suma:

S1 =1

2

S2 =1

2+

1

6=

4

6=

2

3

S3 =1

2+

1

6+

1

12=

9

12=

3

4

S4 =1

2+

1

6+

1

12+

1

20=

16

20=

4

5.



Ejemplo


Sn =1

1 · 2+

1

2 · 3+

1

3 · 4+ · · ·+

1

n(n+ 1),

para cada n ≥ 1.

Solucion.

Conjeturamos entonces que

Sn =n

n+ 1.

Vamos a ver si se puede probar por induccion.

PI-1. Ya vimos que se vale para n = 1. La base de induccion ya esta hecha.

PI-2. Supongamos que se vale para n (HI). Queremos probar que se vale para n + 1.Observamos primero que

Sn+1 =1

1 · 2+

1

2 · 3+

1

3 · 4+ · · ·+

1

n(n+ 1)+

1

(n+ 1)(n+ 2)

= Sn +1

(n+ 1)(n+ 2).



Ejemplo


Sn =1

1 · 2+

1

2 · 3+

1

3 · 4+ · · ·+

1

n(n+ 1),

para cada n ≥ 1.

Solucion.

Por lo tanto,

Sn+1 =n

n+ 1+

1

(n+ 1)(n+ 2)

=1

n+ 1

(n+

1

n+ 2

)=

1

n+ 1

(n2 + 2n+ 1

n+ 2

)=

1

n+ 1·(n+ 1)2

n+ 2

=n+ 1

n+ 2.



Ejemplo

Demuestra la igualdad

sinx+ sin 2x+ · · ·+ sinnx =sin n+1

2x

sin x2

sinnx

2.

Solucion.

PI-1. Si n = 1,

sinx =sin 1+1

2x

sin x2

sinx

2.

Ası que en efecto sa vale para n = 1.



Ejemplo

Demuestra la igualdad

sinx+ sin 2x+ · · ·+ sinnx =sin n+1

2x

sin x2

sinnx

2.

Solucion.

PI-2. Supongamos que la formula se vale para n (HI). Tenemos,

sinx+ sin 2x+ · · ·+ sinnx+ sin(n+ 1)x =sin n+1

2x

sin x2

sinnx

2+ sin(n+ 1)x

=sin n+1

2x

sin x2

sinnx

2+ 2 sin

n+ 1

2x cos

n+ 1

2x

=sin n+1

2x

sin x2

(sin

nx

2+ 2 cos

n+ 1

2x sin

x

2

)

=sin n+1

2x

sin x2

sinn+ 2

2x



Principio de Induccion Modificado

Sea k un numero natural. Sea P (x) una propiedd referida a numeros naturales x ≥ k,tal que

1. Base de Induccion. P (k) es verdadera.

2. Paso Inductivo. La afirmacion

P (n)⇒ P (n+ 1) (o bien P (n− 1)⇒ P (n))

es verdadera.

Entonces P (n) es verdadera para toda n ≥ k.



Ejemplo

Demuestra que, para toda n ≥ 2,

Sn =1

n+ 1+

1

n+ 2+ · · ·+

1

2n>

13

24.

Solucion.

PI-1. Si n = 2,

S2 =1

3+

1

4=

7

12=

14

24>

13

24.

Ası que la formula es validad para n = 2.



Ejemplo


1

n+ 1+

1

n+ 2+ · · ·+

1

2n>

13

24.

Solucion.

PI-2. Ahora supongamos que Sn > 1324

. Queremos probar que Sn+1 > 1324

. Tenemos,

Sn+1 =1

(n+ 1) + 1+

1

(n+ 1) + 2+ · · ·+

1

(n+ 1) + (n− 1)+

1

(n+ 1) + n+

1

2(n+ 1)

=1

n+ 2+

1

n+ 3+ · · ·+

1

2n+

1

2n+ 1+

1

2(n+ 1)

= Sn +1

2n+ 1+

1

2(n+ 1)−

1

n+ 1

= Sn +1

2n+ 1+

1

n+ 1> Sn.

En consecuencia, dada HI, Sn+1 > 1324

, como querıamos probar.



Ejemplo


Sn =1

22+

1

32+ · · ·+

1

n2<

3

4.

Solucion.

Desde luego que se vale para n = 2, pues en tal caso

S2 =1

22=

1

4<

3

4.

Pero probar que Sn+1 < 34

a partir de la HI Sn < 34

no parace que pueda hacerseusando las mismas tecnicas que hemos visto hasta ahora. “El margen de maniobra paramostrar esta desigualdad es muy limitado”.



Ejemplo


Sn =1

22+

1

32+ · · ·+

1

n2<

3

4.

Solucion.

Proponemos trabajar con un resultado mas fuerte del estilo

Sn ≤3

4− an, para toda n ≥ 2,

donde an son numeros positivos por determinar.

Primero necesitamos que se cumpla la base de induccion para n = 2,

S2 =3

4≤

3

4− a2.

De donde

a2 ≤1

2.



Ejemplo


Sn =1

22+

1

32+ · · ·+

1

n2<

3

4.

Solucion.

En cuanto al paso inductivo, necesitamos que la condicion siguiente sea valida:

si se cumple Sn ≤3

4− an entonces se cumple Sn+1 ≤

3

4− an+1.

Pero observamos que Sn+1 = Sn + 1(n+1)2

.

Ası que, suponiendo que Sn ≤ 34− an, la condicion Sn+1 ≤ 3

4− an+1 se cumple si se

cumple3

4− an +

1

(n+ 1)2≤

3

4− an+1.

Esto es,

an − an+1 ≥1

(n+ 1)2



Ejemplo


Sn =1

22+

1

32+ · · ·+

1

n2<

3

4.

Solucion.

Tenemos entonces que verificar dos condiciones para los numeros an, a saber

a2 ≥1

2y an − an+1 ≥

1

(n+ 1)2, si n ≥ 2.

Bastarıa entonces definir

a2 =1

2,

y entonces recursivamente

an+1 = an −1

(n+ 1)2si n ≥ 2.



Ejemplo


Sn =1

22+

1

32+ · · ·+

1

n2<

3

4.

Solucion.

O bien, podemos elegir, por ejemplo,

an =1

n,

para toda n ≥ 2, puesto que de esta forma se tendrıa

a2 =1

2

y para toda n ≥ 2,

an − an+1 =1

n−

1

(n+ 1)=

1

n(n+ 1)>

1

(n+ 1)2.



Principio de Induccion Fuerte

Sea P (x) una propiedad referida a numeros naturales x tal que

1. Base de Induccion. P (1) es verdadera.

2. Paso inductivo. La afirmacion

P (1) ∧ P (2) ∧ · · · ∧ P (n) ⇒ P (n)

es verdadera.

Entonces P (n) es verdadera para toda n ≥ 1.



Ejemplo

Si a es un numero real tal que a+ 1a

es un entero, entonces para toda n ≥ 1, an + 1an

es un entero.

Solucion.

BI. Para n = 1 la afirmacion se cumple trivialmente por ser parte de la hipotesis.

PI. Supongamos que para toda k = 1, 2, ..., n se cumple que ak + 1ak es un entero.

Queremos probar que an+1 + 1an+1 es un entero.

Veamos primero como deberıa cumplirse que a2 + 1a2 . Esto nos dara una idea de como

debe cumplirse para an+1 + 1an+1 .

Tenemos pues que, (a+

1

a

)2

= a2 + 2 +1

a2.

De donde

a2 +1

a2=

(a+

1

a

)(a+

1

a

)−

(a0 +

1

a0

).

Este es un numero entero.



Ejemplo

Si a es un numero real tal que a+ 1a

es un entero, entonces para toda n ≥ 1, an + 1an

es un entero.

Solucion.

Veamos como se cumple para n = 3:(a2 +

1

a2

)(a+

1

a

)= a3 +

1

a3+ a+

1

a.

De donde,

a3 +1

a3=

(a2 +

1

a2

)(a+

1

a

)−

(a+

1

a

).

Este numero es entero.

En general se cumple

an+1 +1

an+1=

(an +

1

an

)(a+

1

a

)−

(an−1 +

1

an−1

).

El cual es entero si an + 1an , an−1 + 1

an−1 y a+ 1a

son enteros.



Demostraciones por induccion

Teorema

Si p es primo, y p∣∣m1m2 · · ·mn, entonces p divide al menos a uno de los numeros

m1,..., mn.

Demostracion.

Ya tenemos la prueba para n = 2. Supongamos que se vale para n (HI). Sea p unprimo tal que p

∣∣m1m2 · · ·mnmn+1. Entonces p divide a m1m2 · · ·mn, en cuyo caso

p divide a alguno de los numeros m1,...,mn por HI, o bien p∣∣mn+1.



Teorema Fundamental de la Aritmetica

Teorema

Para todo m > 1, existe una colecion finita de primos p1,...,pn tales que

m = p1p2 · · · pn.

Demostracion.

Los casos particulares m = 2, m = 3, m = 4 = 2 · 2, m = 5, m = 6 = 2 · 3, m = 7,m = 8 = 2 · 2 · 2, m = 9 = 3 · 3, m = 10 = 2 · 5 son evidentes.

Sea m > 1 y supongamos que para todo 1 ≤ a ≤ m, se cumple que a es un productofinito de primos (HI). Queremos probar que m + 1 tambien es un producto finito deprimos.

Si m+ 1 es primo, no hay nada que hacer.

Si no es ası, existen enteros a y b tales que m + 1 = ab, y tambien 1 < a < m + 1 y1 < b < m+1. Por (HI), a y b son productos finitos de numeros primos, ası que m+1es tambien un producto de primos.



Principio del Buen Orden

Si A ⊂ N y A es no vacıo, entonces existe a∗ ∈ N tal que

PBO-1. a∗ ∈ A,PBO-2. Para todo a ∈ A, a ≤ a∗.

Decimos que A tiene elemento mınimo y que a∗ es el elemento mınimo de A.

El PI y PBO son equivalentes

Teorema

El Principio del Buen Orden y el Principio de Induccion son equivalentes



Algoritmo de la division de Euclides

Teorema

Si a y b son enteros y b 6= 0, existen enteros unicos q y r tales que

a = q · b+ r y 0 ≤ r < |b|.

Demostracion.

Solo el caso a ≥ 0 y b > 0. Sea el conjunto

R = {a− bx : x ∈ Z y a− bx ≥ 0}.

Observamos que R ⊂ N, y dado que

a− b0 = a ≥ 0,

se tiene que R 6= ∅. Por el PBO, existeel mınimo r de R. Sea q ∈ Z tal quer = a− bq, i.e., a = bq + r.

Ahora veamos que r < b. Si b ≤ r, en-tonces para algun entero r′ ≥ 0, se cumpler = b + r′. Y como b > 0, de hecho0 ≤ r′ < r. Luego

r′ = r − b = a− bq − b = a− b(q + 1),

ası que r′ ∈ R. Contradiccion.


araceli guzm an y guillermo garro · 2017. 8. 1. · 1.carmen g omez laveaga, algebra superior ,...

Documents