matematica discreta

Matemática Discreta - FISI

Daniel A. Quinto Pazce

INDUCCIÓN

1

SUMATORIA:
n

n(n 1)
2

i 1 2 3 ... n
i 1
n

i 12

22 32 ... n 2

i 1
n

ai

a1 a2

ai

n(n 1)(2n 1)
6

a3 .... an 1 an

a1.a2 .a3....an 1.an

i 1
n
i 1

PROPIEDADES:
n

1.

n

k

k

i 1
n

2.

n

1 kn

tambien

i 1

1 n
i 1

n

kai
i 1
n

3.

k

ai
i 1n

( ai
i 1
n

4.

n

bi )

ai
i 1

( Fi

Fi 1 )

Fn

bi
i 1

Fm 1 (P. Telescópica )

i m

Calcular por propiedad Telescópica

n

5k
k 1

n

(5k

5k 1 ) 5n 1

k 1
n

5k

k 1
n
k 1

Inducción

n

5k 1

5n 1

k 1

5k

1 n k
5 =
5k 1

Semestre 2014-1

Matemática Discreta - FISI
4 n k
5
5k 1

Daniel A. Quinto Pazce

n

5n

2

5
1 => 5 = (5n 1)
4
k 1
k

Ejercicios:
n

1. Calcular

n

kk! asuma que

(kk! (k 1)( k 1)!)

n

2. Calcular
3. Calcular

nn!

k 1

k 1

(2k 1 2k ), n

k 1
n

k 2 , asuma k 3 (k 1)3

k 1
n

n

(k 3

k 2 asuma

1. Hallar

( k 1) 3 ) conjunto de partida , luego demuestre :

k 1

k 1

INDUCCIÓN MATEMATICA
Inducción es una técnica que seutiliza para demostrar predicados, y no es una herramienta para
descubrir formulas.
En todo Inducción va de lo particular a lo General:

P(n) ---> P(n+1)

En toda Deducción va de lo General a lo Particular:

P(n+1) ----> P(n).

El proceso de inducción, sirve para elaborar HIPOTESIS a partir de un Objetivo.
PRINCIPIO DE INDUCCION
Sea el conjunto de definición S

S

n

N / elpredicado P(n) es válido, n

0

Para demostrar la validez: se tiene el siguiente principio:
i. Para n = 1 S ,
ii. Supongamos que n = h
iii. Para n = h +1 S ,

Inducción

S,

P(1) es válido
P(h) . Hipótesis Inductivo
P(h+1) .es válido

Semestre 2014-1

Matemática Discreta - FISI

Daniel A. Quinto Pazce

Ejemplo de Sumatorias:

3
n

 Demostrar por inducción :

n(n 1)
2k
k 1

Solución:
1

i.

1(1 1)
1
2

k

Para n= 1, k 1
1 1, P (1) : Es válido
h

ii. Suponiendo _ n

h
h

iii. Para : n

h 1
k

h 1

h

k
k 1

h(h 1)
2
k 1
1
(h 1)(( h 1) 1)
k
, por _ demostrar
2
1

h 1

k
k 1

k

k
k h 1

h(h 1)
(h 1)
2
h(h 1) 2(h 1)
2
(h 1)((h 1) 1)
cumple; P(n) es valido
2

1 Demostrar por Inducción
1
=1
1+3
=41+3+5
=9
1+3+5+7
=16
.
.
Encontramos que la serie , se puede expresar mediante la siguiente sumatoria:
n

(2k 1)

n2

k 1

Lo cual demostraremos por inducción:

Inducción

Semestre 2014-1

Matemática Discreta - FISI

Daniel A. Quinto Pazce

2(1) 1 12

Para n = 1:

4

1 1
h

II) Suponiendo_ n

h

(2k 1)

h 2 hipótesis inductiva

k 1

h 1

Para n =h+1

: Para : n

h 1

(2k 1)

(h 1) 2 , por _ demostrar

k 1

h 1

h

(2k 1)
k 1

h 1

(2k 1)
k 1

(2k 1)
k h 1

h2

2(h 1) - 1

h2

2h 1

(h 1) 2 , que es valido la demostraci
on
2. , Demostrar por inducción que el número total de subconjuntos generados a partir de
n
n
A ={ a , b , c , d } sea
2n
k 0 k
i)

Para n=1
1

1

k
k 0
1
1
0
1

21
21 1 2; cumple, P(n) es valido
2

ii)

Supongamos que n=h

h
k 0

iii)

Inducción

2

h
k

2 h ......
Hipótesis Inductiva

Para n=h+1

Semestre 2014-1

Matemática Discreta - FISI
h 1 h 1

2h 1.....Por

k

k 0
h 1 h 1

h

k

k 0

h 1
1

h
0

h
1

h

h

0

h
0

1

.......

h

h 1

h 1
k

k h 1

h 1
2

h 1
3

h
2

h1

h

h

h

h

0

h 1
h

..............

1

h 1
h 1

h
h

.......................

.....................

h
h

h

h
k
k 0

h
......................... para
k
k 0

h

2

k

5

probar

h 1

k 0

h 1
0

Daniel A. Quinto Pazce

h
k
k 0

2.2h

n

h 1

2h 1; cumple

3)Demostrar por Inducción :
n

(3k 2)

i.
k 1

1
(3n...