Matematica Para Informatica

1
Facultad de Ciencias Exactas y Naturales Escuela de Matem´tica a MAY230 - Matem´tica para Inform´tica I a a 1er Semestre 2012

Lista de ejercicios #4 Inducci´n matem´tica o a
Los siguientes ejercicios son tomados del libro de texto Introducci´n a la Matem´tica o a Discreta, 4a edici´n, de Manuel Murillo Tsijli y la Editorial Tecnol´gica de Costa Rica. o o Secci´n 5.1 (Notaci´n Σ y Π) o o 1.Utilice la notaci´n Σ o Π para representar: o
1 (a) 1 + 1 + 3 + · · · + 2 1 56

+ +

1 57

(b) 5 + 7 + 9 + · · · + 41 + 43 (c) (d) − 2 + 3 − ··· + − ( 3 1 ) (4 )( ) ( (e) 3 − 2 4 − 1 5 − 1 · · · 101 − 3 4
1 2 1 2

+ 2 + 3 + ··· + 3 4

33 34 33 34

34 35 34 35

1 100

)

(f) (2 − 8) + (3 − 27) + (4 − 64) + · · · + (10 − 1000) (g) (1 + 4)(1 + 4 + 9)(1 + 4 + 9 + 16) · · · (1 + 4+ 9 + 16 · · · + 121) 2. Determine el valor exacto de: (a)
6 ∑ i=1 5 ∑ i=3 n j 5 ∑ ∏ ( 2k ) (e) k+1 j=3 k=2 i k 5 ∑∑∑ k=3 i=1 j=1

(2i − 3i + 2)
2

5 ∏ (3i2 − 4i) (c) i=1 4 ∑ (1 + k 3 ) (d) k=1

(b)

(3 − 2 )
i i

(f)

(j 2 + 3j)

1∑ 3. Si se define x = xi , pruebe que n i=1
n ∑ i=1

(xi − x)

2

=

n ∑ i=1

x2 − nx2 . i

4. Para n un n´mero natural, considere lasproposiciones P y Q dadas por P (n) : n divide u a 54, Q(n) : n divide a 24. Calcule los valores exactos de: ∏ ∑ (n + 2) (a) (2n − 3) (b)
P (n) n>10 P (n) Q(n)

Ejercicios de Introducci´n a la Matem´tica Discreta, M.Murillo o a

2

Secci´n 5.2 (Inducci´n matem´tica) o o a 1. Utilice el m´todo de inducci´n matem´tica para probar la validez de las siguientes iguale o a dades para todo n ≥ 0 o n≥ 1, seg´n corresponda: u (a) 1 + 2 + 3 + · · · + n = (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (o) (p) (q) (r) (s) (t) n(n + 1) 2 n(3n + 1) 2 + 5 + 8 + · · · + (3n − 1) = 2 2 3 + 11 + · · · + (8n − 5) = 4n − n 1 · 2 + 2 · 4 + 3 · 8 + · · · + n · 2n = 2 + (n − 1)2n+1 n(2n − 1)(2n + 1) 1 + 9 + 25 + · · · + (2n − 1)2 = 3 n(n + 1)(2n + 1) 12 + 22 + 32 + · · · + n2 = 6 n2 (n + 1)2 13 + 23 + 33+ · · · + n3 = 4 3 3 3 3 1 + 3 + 5 + · · · + (2n − 1) = n2 (2n2 − 1) 1 3 5 2n − 1 2n + 3 + + + ··· + =3− n 2 4 8 2 2n 2 n n+1 1 + 2 + 2 + ··· + 2 = 2 −1 an+1 − 1 1 + a + · · · + an−1 + an = , si a ̸= 1 a−1 2 2 2 1 + + ··· + n = 1 − n 3 9 3 3 1 1 1 n + + ··· + = 1·3 3·5 (2n − 1)(2n + 1) 2n + 1 3 3 3 3 1 + 2 + 3 + · · · + n = (1 + 2 + 3 + · · · + n)2 12 22 n2 n(n + 1) + + ··· + = 1·3 3·5 (2n −1)(2n + 1) 2(2n + 1) 3 4 n+2 1 + + ··· + =1− 1 · 2 · 2 2 · 3 · 22 n(n + 1)2n (n + 1)2n n ∑ n(n2 − 1) (i2 − i) = 3 i=2
n ∑ i=2 n ∑ i=1 n ∑

√ 1 √ = n−1 √ i−1+ i i(i!) = (n + 1)! − 1

n 1 = (4i − 3)(4i + 1) 4n + 1 i=1 ) n ∏( 1 n+1 (u) 1− 2 = i 2n i=2

Ejercicios de Introducci´n a la Matem´tica Discreta, M.Murillo o a

3

2. Utilice el m´todo de inducci´n matem´tica para demostrar que lassiguientes proposiciones e o a son verdaderas para todo n ≥ 1: (a) n4 + 2n3 + n2 es divisible por 4 (b) n(n + 1)(n + 2) es divisible por 6 (c) n3 + 11n es divisible por 6 (d) n7 − n es divisible por 7 (e) 32n+1 + 2n+2 es divisible por 7 (f) 32n − 1 es divisible por 8 (g) 3n + 7n − 2 es divisible por 8 (h) 4n + 15n − 1 es divisible por 9 (i) 10n + 3 · 4n+2 + 5 es divisible por 9 (j) 32n + 26n−5 esdivisible por 11 (k) 102n+1 + 1 es divisible por 11 (l) 42n+1 + 3n+2 es divisible por 13 (m) 72n + 16n − 1 es divisible por 64 3. Utilice el m´todo de inducci´n matem´tica para demostrar la validez de las siguientes e o a desigualdades: (a) 2n < n!, para n ≥ 4 (b) 1 + 2 + 3 + · · · + n ≤ (c) (d) (e) (f) (g) (h) (2n + 1)2 , para n ≥ 1 8

1 1 1 1 + + + · · · + n < n · ln(2), para n ≥ 1 2 4 8 2 n3 2 22 1 + 2 + · · · + (n − 1) < < 12 + 22 + · · · + n2 , para n ≥ 2 3 n4 13 + 23 + · · · + (n − 1)3 < < 13 + 23 + · · · + n3 , para n ≥ 2 4 1 1 1 13 + + ··· + > , para n ≥ 2 n+1 n+2 2n 24 n ∑ 2i − 1 7 2n + 3 ≤ − , para n ≥ 1 i 2 2 2n i=1

√ √ 1 1 1 1 n ≤ √ + √ + √ + · · · + √ ≤ n n, para n ≥ 1 n 1 2 3 n2 (n + 1) (i) 1 · 2 + 2 · 3 + 3 · 4 + · · · + (n − 1)n < , para n ≤ 2 3 (2n)! 4n (j) ≤ , para...