Ingenieria Matematica

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 I tiene un elemento menor que los N restantes. Es decir, si S ⊆ I , S = φ, entonces existe p ∈ S tal que N ∀r∈S: p ≤ r.TEOREMA: Principio de inducción matemática Sean S ⊆ I y p ∈ I tales que N N p∈S k∈S ⇒ (k + 1) ∈ S

Entonces S contiene a todos los naturales mayores o iguales que p, N, es decir: ∀ k ∈ I 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 ∈ I , k > p, tal que k ∈ S, y definamos: N G := {m ∈ I : N m > p ∧ m ∈ S}

Esclaro que G = φ ya que k ∈ G. Luego, por el principio de la buena ordenación, existe r ∈ G tal que r ≤ m ∀m ∈ G. Notar que r > p y r ∈ S. Así, como r es el menor elemento de G, se deduce que r − 1 ∈ 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 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 ∈ I 8n−1 + 6 N, Solución Sea S = n ∈ I : 8n−1 + 6 es divisible por 7 N 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. es divisible por 7.

4

Inducción Matemática
Tesis de Inducción: Probemos que k + 1 ∈ S, es decir, 8k+1−1 + 6
8k +6

es divisible por 7.

8k + 6 = 8k−1 · 8 + 6 = 8k−1 · 8 + 6 · 8 − 6 · 8 + 6 = 8 (8k−1 + 6)
es divisible por 7,
por Hip. de Inducción

+ 6 (−8 + 1)
es divisible por 7

−7

∴ k + 1 ∈ S. Luego S = I N
5

Inducción Matemática
Factorial yCoeficiente Binomial Dado k ∈ I , se define el factorial de k, denotado por k!, como N sigue 1! = 1 y ∀k ≥ 2 : k! = k · (k − 1)!

Además, se define 0! = 1. Sean k, n ∈ I ∪ {0} tales que ≤ n. Se define el coeficiente N k  binomial de n y k, y se denota    n k  n k , al número:

 =

n! k! (n − k)!

6

Inducción Matemática
Propiedades de los Coeficientes Binomiales Sean k, n ∈ I ∪ {0}tales que k < n. Entonces, se tiene: N     n n   =   = 1 0 n   n  = n  1     n n   =   n−k k       n+1 n 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
n k=1

ak , a:

ak = a1 + a2 + · · · + an−1 + an
k=1

EJEMPLOS
n

k 2 =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 =
i=1 n j=1

aj

y
i=0

ai =
i=1

ai−1 =
i=2

ai−2 =
i=k

ai−k

a = a + a + · · · + a + a = na
i=1 n n

c ai = c
i=1 n i=1

ain

(c
n

constante)

(ai + bi ) =
i=1 n i=1

ai +
i=1 m n

bi

i=1 n

 

m

j=1

bj  ai =



ai
j=1 i=1

bj

(ai+1 − ai ) = an+1 − a1
i=1

(propiedad telescópica)
9

Inducción Matemática
EJEMPLO Demuestre que
n

∀n∈I ,n≥2 : N
k=2

k (k!) = (n + 1)! − 2!

SOLUCION
n

Sea S :=

n∈I :n≥2 ∧ N
k=2

k (k!) = (n + 1)! − 2!

¿2 ∈ S?
2

Envista que
k=2

k (k!) = 2(2!) = 4 y (2 + 1)! − 2! = 4, se concluye

que 2 ∈ S. Hipótesis de Inducción: supongamos que r ∈ S, es decir,
r

k (k!) = (r + 1)! − 2!
k=2
10

Inducción Matemática
Tesis de Inducción: probemos que r + 1 ∈ S.
r+1 r

k (k!) =
k=2 k=2

k (k!) + (r + 1) · (r + 1)! (prop. de sumatorias) (hip. de inducción)

= (r + 1)! − 2! + (r + 1) · (r + 1)! ⇒r+1∈S,...