ALGEBRA y ALGEBRA LINEAL
520142
Primer Semestre
INDUCCION MATEMATICA
DEPARTAMENTO DE INGENIERIA MATEMATICA
Facultad de Ciencias Fsicas y Matemticas
Universidad de Concepcin
1
Induccin Matemtica
Principio de la buena ordenacin
Todo subconjunto no vaco de IN tiene un elemento menor que los
restantes. Es decir, si S IN , S 6= , entonces existe p S tal que
rS:
p r.
TEOREMA: Principio de induccin matemtica
Sean S IN y p IN tales que
pS
kS
(k + 1) S
Entonces S contiene a todos los naturales mayores o iguales que p,
es decir: k IN, k p : k S
2
Induccin Matemtica
DEMOSTRACION
Por el mtodo de contradiccin: ( H T ) P P
Supongamos que existe k IN , k > p, tal que k 6 S, y definamos:
G := {m IN :
m > p m 6 S}
Es claro que G 6= ya que k G. Luego, por el principio de la buena
ordenacin, existe r G tal que r m m G. Notar que r > p y
r 6 S. As, como r es el menor elemento de G, se deduce que r 1 6 G,
lo cual implica dos posibilidades: ( r 1 p ) ( r 1 S ).
Si r 1 p, entonces r p + 1, y puesto que r > p, se deduce
que r = p + 1. As, como p S, se concluye por hiptesis que
r = p + 1 S, lo cual contradice el hecho que r 6 S.
Si r 1 S, entonces por hiptesis nuevamente se deduce que
r = (r 1) + 1 S, lo cual contradice el hecho que r 6 S.
3
Induccin Matemtica
EJEMPLO
Pruebe que:
n IN, 8n1 + 6
es divisible por 7.
Solucin
n1
Sea S = n IN : 8
+ 6 es divisible por 7
Si n = 1
8n1 + 6 = 1 + 6 = 7 = 7 1
1S
Hiptesis de Induccin: Supongamos que k S, es decir,
8k1 + 6 es divisible por 7.
Induccin Matemtica
Tesis de Induccin: Probemos que k + 1 S, es decir, |8k+11
{z + 6}
8k +6
es divisible por 7.
8k + 6 = 8k1 8 + 6
= 8k1 8 + 6 8 6 8 + 6
= 8 (8k1 + 6)
| {z }
es divisible por 7,
por Hip. de Induccin
+ 6 (8 + 1)
| {z }
7
es divisible por 7
k + 1 S.
Luego S = IN
5
Induccin Matemtica
Factorial y Coeficiente Binomial
Dado k IN , se define el factorial de k, denotado por k!, como
sigue
1! = 1
k 2 :
k! = k (k 1)!
Adems, se define 0! = 1.
Sean k, n IN {0} tales que
k n.
Se define el coeficiente
binomial de n y k, y se denota
n
k
n
k
, al nmero:
n!
k! (n k)!
Induccin Matemtica
Propiedades de los Coeficientes Binomiales
Sean k, n IN {0} tales que k < n. Entonces, se tiene:
n
n
=
= 1
0
n
n
= n
n
n
nk
k
n+1
n
n
=
+
k+1
k+1
k
7
Induccin Matemtica
El Operador Sumatoria
Dados n nmeros reales indexados como a1 , a2 , . . . , an , se define la
n
X
ak , a:
sumatoria de ellos, y se denota
n
X
k=1
ak = a1 + a2 + + an1 + an
k=1
EJEMPLOS
n
X
k 2 = 12 + 22 + 32 + + (n 1)2 + n2
k=1
n
X
(2k 1) = 1 + 3 + 5 + 7 + + (2n 3) + (2n 1)
k=1
n
X
3k = 30 + 31 + 32 + 33 + + 3n1 + 3n
k=0
8
Induccin Matemtica
Propiedades del Operador Sumatoria
n
X
ai =
aj
j=1
i=1
n
X
n
X
n
X
ai =
n+1
X
ai1 =
i=1
i=0
n+2
X
i=2
ai2 =
n+k
X
aik
i=k
a = a + a + + a + a = na
i=1
n
X
c ai = c
(ai + bi ) =
i=1
n
X
i=1
n
X
ai +
constante)
m
X
j=1
bj ai =
n
X
bi
i=1
i=1
i=1
n
X
(c
ai
i=1
i=1
n
X
n
X
m
X
j=1
n
X
i=1
(ai+1 ai ) = an+1 a1
ai
bj
(propiedad telescpica)
9
Induccin Matemtica
EJEMPLO
Sea m IN fijo, establecer que
n IN, n m :
n
X
kk! = (n + 1)! m!
k=m
SOLUCION
Observar que cualquiera sea k IN :
kk! = (k+1 1)k! = (k + 1)! k!
Luego, si ak = k!, entonces
n IN :
n
X
k=m
kk! =
n
X
(ak+1 ak ) = (n + 1)! m!
k=m
gracias a la propiedad telescpica del operador sumatoria.
10
Induccin Matemtica
TEOREMA DEL BINOMIO
Sean a, b R {0}, y sea n IN . Entonces:
(a + b) =
n
X
k=0
n
k
ank bk
Algunas observaciones
El desarrollo de (a + b)n consta de n + 1 trminos.
La suma de los exponentes de a y b en cada trmino es n.
Los coeficientes de los trminos equidistantes del centro son
iguales.
El trmino que ocupa el lugar k + 1 est dado por
Tk+1
n
k
ank bk
11
Induccin Matemtica
DEMOSTRACION DEL TEOREMA DEL BINOMIO
Dado n IN consideremos la proposicin:
n
X
n
n
ank bk .
p(n) :
(a + b) =
k
k=0
Entonces, se define el subconjunto de IN dado por:
S := { n IN :
1 S.
En efecto,
p(n) es verdadera } .
p(1) es claramente verdadera.
HIPOTESIS DE INDUCCION
Sea m IN tal que m S, es decir, (a+b)
m
X
k=0
TESIS DE INDUCCION
m + 1 S, es decir, (a + b)
m+1
m+1
X
k=0
m+1
k
m
k
amk bk .
am+1k bk .
12
Induccin Matemtica
DEMOSTRACION DE LA TESIS DE INDUCCION
(a + b)m+1 = (a + b) (a + b)m
= a (a + b)m + b (a + b)m
Luego, de acuerdo a la Hiptesis de Induccin y a propiedades del
operador sumatoria y de los coeficientes binomiales, se sigue que
m
X
k=0
m+1
=a
m
X
k=1
m
k
m+1
m
k
k=0
am+1k bk +
am+1k bk +
= a
m+1
X
m
X
k=1
m+1
k
m
X
k=1
m+1
m
X
k=0
k1
amk bk+1
am+1k bk + bm+1
am+1k bk + bm+1
am+1k bk ,
lo cual prueba que (m + 1) S .
13
Induccin Matemtica
EJEMPLO
Considere el desarrollo de:
y
2x
y
x
45
a) Encuentre las potencias de y en los trminos centrales.
b) Encuentre, si existe, el trmino independiente de x.
14
Induccin Matemtica
SOLUCION
a) Tk+1
T23
T24 =
=
45
45
22
1 23
45
23
1 22
2x
y
45k
y
x
2 22
= y 23+44 = y 21
2x
y
y
4522
y
2x
y
2 23
= y 22+46 = y 24
y
x
k
22
4523
y
x
23
Las potencias de y en los trminos centrales son 21 y 24.
15
Induccin Matemtica
SOLUCION
b)
Tk+1
45
k
3 45k
= x
2x3
y
45k
1 k
y 2
x
k
= x0
= 135 3k k = 0
= 4k = 135
135
6 IN {0}
= k =
4
No existe el trmino independiente de x.
16
Induccin Matemtica
PROGRESION ARITMETICA
Sean a1 , d R nmeros dados. Se llama PROGRESION
ARITMETICA (PA) con trmino inicial (primer trmino) a1 y
diferencia comn d a la sucesin de nmeros a1 , a2 , . . . , an , . . .,
donde
n 2 :
an = an1 + d
Notar que n IN : an = a1 + (n 1) d
(demostracin por induccin).
La suma de los n primeros trminos de una Progresin Aritmtica
con primer trmino a1 y diferencia comn d, est dada por
n
X
k=1
ak =
n
n
(2a1 + (n 1)d) =
(a1 + an )
2
2
(demostracin por induccin).
n IN
17
Induccin Matemtica
PROGRESION GEOMETRICA
Sean a1 , r R nmeros dados. Se llama PROGRESION
GEOMETRICA (PG) con trmino inicial a1 y razn (cuociente)
comn r a la sucesin de nmeros a1 , a2 , . . . , an , . . ., donde
n 2 :
an = r an1
Notar que n IN : an = r n1 a1
(demostracin por induccin).
La suma de los n primeros trminos de una Progresin Geomtrica
con primer trmino a1 y razn comn r, est dada por
n
X
k=1
ak = a1
1r
1r
n IN
r 6= 1
(demostracin por induccin).
18
Induccin Matemtica
EJEMPLO
Una persona lee un libro de tal manera que cada da aumenta en 4 el
nmero de pginas que ley el da anterior, es decir, si el da k-simo
ley ak pginas el da siguiente leer ak + 4 pginas. Si despus de 18
das ha ledo los 21/55 del libro, y 6 das ms tarde le faltaban nicamente
los 19/55 del libro, cuntas pginas tiene el libro?
19
Induccin Matemtica
SOLUCION
Sea P el nmero total de pginas que tiene el libro en
cuestin. Denotando por ak la cantidad de pginas que lee el alumno en
el k-simo da, del enunciado se rescata que
ak+1 = ak + 4 ,
k = 1, 2, 3, ... ,
lo cual nos dice que {a1 , a2 , a3 , ...} define una progresin aritmtica de
diferencia comn d = 4 y primer elemento a1 .
Adems, del enunciado se pueden extraer la siguiente informacin:
18
X
k=1
24
X
k=1
21
P
ak =
55
36
P
ak =
55
7
2 a1 + 17 4 =
P
165
3
2 a1 + 23 4 =
P
55
(i)
(ii)
De (ii) (i) se tiene
1
4(23 17) =
(9 7)P
165
P = 1980 pginas.
20
