ALGEBRA y ALGEBRA LINEAL
520142
Primer Semestre
INDUCCION MATEMATICA
DEPARTAMENTO DE INGENIERIA MATEMATICA
Facultad de Ciencias Físicas y Matemáticas
Universidad de Concepción
1
Inducción Matemática
Principio de la buena ordenación
Todo subconjunto no vacío de IN tiene un elemento menor que los
restantes. Es decir, si S ⊆ IN, S ƒ= φ, entonces existe p ∈ S tal que
∀ r∈ S: p ≤r.
TEOREMA: Principio de inducción matemática
Sean S ⊆ INy p ∈ INtales que
p∈ S
k∈S ⇒ (k + 1) ∈ S
Entonces S contiene a todos los naturales mayores o iguales que p,
es decir: ∀ k ∈ IN, k ≥ p : k∈ S
2
Inducción Matemática
DEMOSTRACION
Por el método de contradicción: ( H ∧ ∼ T ) ⇒ P ∧ ∼ P
Supongamos que existe k ∈ IN, k > p, tal que k ƒ∈ S, y definamos:
tt := {m ∈ IN : m > p ∧ m ƒ∈ S}
Es claro que tt ƒ= φ ya que k ∈ tt. Luego, por el principio de la
buena ordenación, existe r ∈ tt tal que r ≤ m ∀ m ∈ tt. Notar que r >
p y r ƒ∈ S. Así, como r es el menor elemento de tt, se deduce que r − 1
ƒ∈ tt, 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 hipótesis que
r = p + 1 ∈ S, lo cual contradice el hecho que r ƒ∈ S.
Si r − 1 ∈ S, entonces por hipótesis nuevamente se deduce que
r = (r − 1) + 1 ∈ S, lo cual contradice el hecho que r ƒ∈ S.
3
Inducción Matemática
EJEMPLO Pruebe que:
∀ n ∈ IN, 8n−1 + 6 es divisible por 7.
Solución
. n−1
Σ
Sea S = n ∈ IN : 8 + 6 es divisible por 7
Si n = 1
8n−1 + 6 = 1 + 6 = 7 = 7 · 1
∴ 1∈S
Hipótesis de Inducción: Supongamos que k ∈ S, es decir,
8k−1 + 6 es divisible por 7.
4
Inducción Matemática
Tesis de Inducción: Probemos que k + 1 ∈ S, es decir, 8k+1−1 + 6
s ˛¸ x
8k + 6
es divisible por 7.
8k + 6 = 8k−1 · 8 + 6
= 8k−1 · 8 + 6 · 8 − 6 · 8 + 6
k−1
= 8 (8
s ˛¸+ 6)x + 6 (−8 + 1)
es divisible por 7,
s ˛¸ x
por Hip. de Inducción −7 por 7
es divisible
por Hip. de Inducción
∴ k + 1 ∈ S.
Luego S = IN
5
Inducción Matemática
Factorial y Coeficiente Binomial
Dado k ∈ IN, se define el factorial de k, denotado por k!, como
sigue
1! = 1 y ∀k ≥2: k! = k · (k − 1)!
Además, se define 0! = 1.
Sean k, n ∈ IN∪ {0} tales que k ≤ n. Se define el coeficiente
n
binomial de n y k, y se denota , al número:
n!
n =
k! (n − k)!
k
6
Inducción Matemática
Propiedades de los Coeficientes Binomiales
Sean k, n ∈ IN∪ {0} tales que k < n. Entonces, se tiene:
n n
= = 1
0 n
n
= n
1
n n
=
n −k
k
n n +1
n =
+ k+1
k +1
k
7
Inducción Matemática
El Operador Sumatoria
Dados n números reales indexados como a1, a2, . . . , an, se define la
Σn
sumatoria de ellos, y se denota ak, a:
k=1
Σn
ak = a1 + a2 + · · · + an−1 + an
k=1
EJEMPLOS
n
Σ
k2 = 12 + 22 + 32 + · · · + (n − 1)2 + n2
k=1
n
Σ
(2k − 1) = 1 + 3 + 5 + 7 + · · · + (2n − 3) + (2n − 1)
k=1
n
Σ
3k = 30 + 31 + 32 + 33 + · · · + 3n−1 + 3n
k=0
8
Inducción Matemática
Propiedades del Operador Sumatoria
n n n n+1 n+2 n+k
Σ Σ Σ Σ Σ Σ
ai = aj y ai = ai−1 = ai−2 = ai−k
i=1 j=1 i=0 i=1 i=2 i=k
n
Σ
a = a + a + · · · + a + a = na
i=1
Σn n
Σ
c ai = c ai (c constante)
i=1
i=1
n n n
Σ Σ Σ
(ai + bi) = ai + bi
i=1 i=1 i=1
m
. n Σ
n m
Σ
Σ ai = Σ
Σ bj ai bj
j=1 i=1
i=1 j=1
n
Σ
(ai+1 − ai) = an+1 − a1 (propiedad telescópica)
i=1
Inducción Matemática
EJEMPLO
Demuestre que
n
∀ n ∈ IN, n ≥ 2 : Σ k (k!) = (n + 1)! − 2!
k=2
SOLUCION
. n Σ
Σ
Sea S := n ∈ IN : n ≥ 2 ∧ k (k!) = (n + 1)! − 2!
k=2
¿2 ∈ S?
Σ
2
En vista que k (k!) = 2(2!) = 4 y (2 + 1)! − 2! = 4, se concluye
k=2
que 2 ∈ S.
Hipótesis de Inducción: supongamos que r ∈ S, es decir,
r
Σ
k (k!) = (r + 1)! − 2!
10
k=2
Inducción Matemática
Tesis de Inducción: probemos que r + 1 ∈ S.
r+1 r
Σ Σ
k (k!) = k (k!) + (r + 1) · (r + 1)! (prop. de sumatorias)
k=2 k=2
= (r + 1)! − 2! + (r + 1) · (r + 1)! (hip. de inducción)
= (r + 1)! · (1 + r + 1) − 2! = (r + 2)! − 2!
⇒ r+1∈ S,
y así, por el principio de Inducción Matemática, concluye la demostración.
11
Inducción Matemática
TEOREMA DEL BINOMIO
Sean a, b ∈ R − {0}, y sea n ∈ IN. Entonces:
n
Σ
(a + b)n = n an−k bk
k=0 k
Algunas observaciones
El desarrollo de (a + b)n consta de n + 1 términos.
La suma de los exponentes de a y b en cada término es n.
Los coeficientes de los términos equidistantes del centro son
iguales.
El término que ocupa el lugar k + 1 está dado por
tk+1 = n
an−k
bk
k 12
Inducción Matemática
DEMOSTRACION DEL TEOREMA DEL BINOMIO
Dado n ∈ INconsideremos la proposición:
an−k bk .
Σ n
n
p(n) : (a + b)n =
k=0 k
Entonces, se define el subconjunto de INdado por:
S := { n ∈ IN : p(n) es verdadera } .
1 ∈ S. En efecto, p(1) es claramente verdadera.
HIPOTESIS DE INDUCCION
Σ
m
m
m am−k bk .
Sea m ∈ INtal que m ∈ S, es decir, (a+b) =
k=0 k
TESIS DE INDUCCION
Σ
m+1 m+1
m + 1 ∈ S, es decir, (a + b)m+1 = am+1−k bk .
k=0 k
13
Inducción Matemática
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 Hipótesis de Inducción y a propiedades del
operador sumatoria y de los coeficientes binomiales, se sigue que
Σ m+1−k k m−k k+1
m m
= m
k a m
k a
k=0 Σ
b + b
k=0
Σ
am+1−k bk +Σ
m+1 m m
=a + m m am+1−k bk + bm+1
k=1 k k=1 k −1
m
Σ m+1
= am+1 + am+1−k bk + bm+1
k=1 k
m+1 m+1
Σ
=
am+1−k bk,
k=0 k
lo cual prueba que (m + 1) ∈ S . 14
Inducción Matemática
EJEMPLO
Considere el desarrollo de:
. 2x3 y2 Σ
45
−
y x
a) Encuentrre las potencias de y en los términos centrales.
b) Encuentre, si existe, el término independiente de x.
15
Inducción Matemática
. Σ45−k . Σk
a) T 45 2x 3
−y 2
SOLUCION k+1 =
k y x
. 3 Σ45−22 . Σ22
45 2x −y 2
T23 =
22 y x
23 22
. Σ . 2Σ = y−23+44 = y21
=⇒ y −1 y
45 . Σ45−23 . Σ23
T24 = 2x 3
−y 2
23 y x
22 23
. Σ . 2Σ = y−22+46 = y24
=⇒ y −1 y
Las potencias de y en los términos centrales son 21 y 24.
16
Inducción Matemática
SOLUCION b)
. 3 Σ45−k . Σk
45 2x −y 2
T =
k+1
k y x
. Σ 45−k . −1
Σk
=⇒ x 3
x = x0
=⇒ 135 − 3k − k = 0
=⇒ 4k = 135
135
=⇒ k = ƒ∈ IN∪ {0}
4
∴ No existe el término independiente de x.
17
Inducción Matemática
PROGRESION ARITMETICA
Sean a1, d ∈ R números dados. Se llama PROGRESION
ARITMETICA (PA) con término inicial (primer término) a1 y
diferencia común d a la sucesión de números a1, a2, . . . , an, . . .,
donde
∀n≥2: an = an−1 + d
Notar que ∀ n ∈ IN : an = a1 + (n − 1) d
(demostración por inducción).
La suma de los n primeros términos de una Progresión Aritmética
con primer término a1 y diferencia común d, está dada por
n n
Σ n
ak = (2a1 + (n − 1)d) = (a1 + an) ∀ n ∈ IN
2 2
k=1
(demostración por inducción). 18
Inducción Matemática
PROGRESION GEOMETRICA
Sean a1, r ∈ R números dados. Se llama PROGRESION
GEOMETRICA (PG) con término inicial a1 y razón (cuociente)
común r a la sucesión de números a1, a2, . . . , an, . . ., donde
∀n≥2: an = r an−1
Notar que ∀ n ∈ IN : an = rn−1 a1
(demostración por inducción).
La suma de los n primeros términos de una Progresión Geométrica
con primer término a1 y razón común r, está dada por
n . Σ
Σa = a 1 − rn
k 1 ∀ n ∈ IN ∀ r ƒ= 1
1 −r
k=1
(demostración por inducción).
19
Inducción Matemática
EJEMPLO
Una persona lee un libro de tal manera que cada día aumenta en 4 el
número de páginas que leyó el día anterior, es decir, si el día k-ésimo
leyó ak páginas el día siguiente leerá ak + 4 páginas. Si después de 18
días ha leído los 21/55 del libro, y 6 días más tarde le faltaban únicamente
los 19/55 del libro, ¿cuántas páginas tiene el libro?
20
Inducción Matemática
SOLUCION Sea P el número total de páginas que tiene el libro en
cuestión. Denotando por ak la cantidad de páginas que lee el alumno en
el k-ésimo día, del enunciado se rescata que
ak+1 = ak + 4 , k = 1, 2, 3, ... ,
lo cual nos dice que {a1, a2, a3, ...} define una progresión aritmética de diferencia
común d = 4 y primer elemento a1.
Además, del enunciado se pueden extraer la siguiente información:
18
Σ 21 7
ak = P ⇒ 2 a1 + (17)(4) = P (i)
k=1
55 165
Σ
24 36
ak = P ⇒ 2 a1 + (23)(4) = P (ii)
55 3
55
k=1
De (ii) − (i) se tiene
1
(4)(23 − 17) = (9 − 7)P ⇒ P = 1980 páginas.
21
165
