metodos de integracion

E.I.S.C Tecnicas de demostraci

on

METODOS DE DEMOSTRACION

Definiciones basicas

Definición 1. un Teorema es una sentencia que se puede verificar que es verdadera.

(P1 ∧ P2 . . . ∧ Pn) → Q) es un teorema donde los P1, P2 . . . Pn son los postulados o premisas y Q la conclusion del teorema.Ejemplo 1. Sea el siguiente teorema si a y b son enteros positivos, a ≥ b, entonces a0 ≥ b0

premisas:P1 : a y b son enteros positivos.P2 : a ≥ by la conclusion Q es a0 ≥ b0 por lo tanto el teoremaser´ıa (P1 ∧ P2) → Q

Definición 2. Un lema es un teorema sencillo uti- lizado en la demostracion de otros teoremas.

Definición 3. Un corolario es una proposicion que se puede establecer directamente a partir de un teorema que ya ha sido demostrado.

1. REGLAS DE INFERENCIA.

Estas reglas justifican los pasos dados para demostrar que a partir de una serie de hipotesis se


onllega de forma logica a una conclusion.

Ejemplo 2. Una regla de inferencia b´asica es lamodus ponens


on

pp → q∴ q

Ejemplo 3. En que regla de inferencia se basa el siguiente argumento: Ahora estamos bajo cero. Por tanto estamos bajo cero o bien llueve ahora.

p∴ p ∨ q

Esta es la regla de inferencia de la Adici´on y su tautolog´ıa ser´ıa p → (p ∨ q)

Ejemplo 4. Cu´al es la regla de inferencia de para el siguiente argumento: Estamos bajo cero y llueve. Por tanto, estamos bajo cero.

p ∧ q∴ p

Este argumento usa la regla de la simplificacion y su tautolog´ıa ser´ıa (p ∧ q) → p.


on

Ejemplo 5. Fue X o Y quién cometió el crimen. X estaba fuera del pueblo cuando el crimen fue cometido. Si X estaba fuera del pueblo, no pudo haber estado en la escena del crimen. Si X no estaba en la escena del crimen, no pudo haber cometido el crimen. Obtenga la conclusión usando las reglas de inferencia.

P1: X cometió el crimen. P2: Y cometió el crimen.Q: X estaba fuera del pueblo cuando fue cometido el crimen.R: X no estaba en la escena del crimen.

R: la fiesta de Anõ Nuevo se can

elo.S: Alicia estaba enojada.T : Hubo que devolver el dinero.

El argumento válido: Premisas:1)(v P ∨ v Q) → (R ∧ S)


on

El argumento en LP:1) P 1 ∨ P 22) Q3) Q → R4) R →v P 15) R aplicando modus ponens a (2) y (3)6) v P 1 aplicando modus ponens a (5) y (4)7) ∴ P 2 aplicando el silogismo disyuntivo a (1) y(6)Por lo tanto se concluye que Y cometió el crimen.

También se puede demostrar la validez de un argumento derivando la conclusion desde las premisas usando las REGLAS DE INFERENCIA.

Ejemplo 6. Dado el siguiente argumento válido: Si la banda no pudiera tocar rock o las bebidas no llegasen a tiempo, entonces la fiesta de Ano Nue- vo tendr´ıa que cancelarse y Alicia se enojar´ıa. Si la fiesta se cancelara, habr´ıa que devolver el dinero. No se devolvio el dinero. Por lo tanto, la banda pudo tocar rock. Derive la consecuencia logica usando las reglas de inferencia.

P : la banda pudo tocar rock.Q: las bebidas se entregaron a tiempo.

c


on

2) R → T3) v T∴ P

Se debe inferir con las premisas 1,2 y 3 y llegar a derivar P.

1)R → T premisa2) v T premisa3) v R aplicando modus tollens a (1) y (2)4) v R∨ v S aplicando ley de adici´on con (3)5) v (R ∧ S) aplicando ley de morgan a (4)6) (v P ∨ v Q) → (R ∧ S) premisa7) v (v P ∨ v Q) aplicando modus tollens a (5) y(6)8) P ∧ Q aplicando ley de morgan y de la doble negacion a (7)9) ∴ P aplicando simplificacion conjuntiva a (8)

Ejemplo 6.1 aplique las reglas de inferencia para demostrar que q → p es una consecuencia logica de las premisas:u → r; (r ∧ s) → (p ∨ t); q → (u ∧ s); ∼ t

1) (r ∧ s) → (p ∨ t) premisa2) v r∨ v s ∨ p ∨ t aplicacion de la implicacion a 1


on3) u → r premisa

5) v u∨ v s ∨ p ∨ t resolución 2 y 46) v (u ∧ s) ∨ p ∨ t aplicacion de7) (u ∧ s) → (p ∨ t) aplicación de8) q → (u ∧ s) premisa

morgan a 5implicacion a 6

9) q → (p ∨ t) silogismo hipotético 8 y 7

t

10) (v q ∨ p) ∨ t implicacion y asociativa de 911) v t premisa12) v q ∨ p silogismo disyuntivo de 10 y 1113) ∴ q → p implicacion de 12

2. METODOS PARA DEMOSTRAR TEOREMAS.

2.1 Demostracion Directa. Se basa en la implicacion p → q se puede demostrar que si p es verdadero q tambi´en lo es.

p: es la hipotesis (lo que se supone como verdadero)q: es la Tesis (lo que se va ha demostrar)

Definici´on 1. El entero n es par si existe un entero k tal que n = 2k y es impar si existe un entero k tal que n = 2k + 1

Ejemplo 7. Demostrar que si n es un entero impar, entonces n2 es un entero impar.

p: n es impar. (hipotesis)q: n2 es impar. (tesis)Se demuestra p → q, se parte de que p verdadero y se termina demostrando que q es verdadero.

Si n es impar entonces, n = 2k + 1, donde k es un entero.Se sigue que n2 = (2k + 1)2 = 4k2 + 4k + 1 =2 (k2 + k) +1| {z

Z

}∈

Por tanto como n2 es de la forma 2t + 1 entones

q quu

n2 es impar.

Definición 2. El numero real r es racional si existen dos enteros p y q, q = 0, tales que r = p/q. Un numero real que no es racional es irracional.

Ejemplo 8. Demuestre que la suma de dos racionales es un racional.

p: Sean r y s racionales, si r es racional entonces r = p/q para q = 0 y si s es racional entonces s = t/u para u = 0. (hipótesis)

q: Hay que demostrar que r + s es racional. (tesis)

sumamos r + s = p + t = pu+qt , donde = 0qupor que q = 0 y u = 0 por tanto hemos expresador + s como la razoń de dos enteros pu + qt y quPOR TANTO r + s es racional.

2.2 Demostracion indirecta. Como la implicacionp → q es equivalente a su contrarec´ıproca v q →v pla implicacion se puede demostrar viendo que sucontrarec´ıproca es verdadera.

Ejemplo 9. Demostrar que si 3n + 2 es impar, entonces n es impar.

p: 3n + 2 es impar.

q: n es impar.Suponemos la v q es decir que n es par, entoncesn = 2k para algun entero k y demostramos v p esdecir que 3n + 2 es par.

l

ahora se sigue que 3n + 2 = 3(2k) + 2 = 2(3k) +2 = 2 (3k + 1)

y 3n + 2 es de la forma 2l

| {zZ }

∈Por tanto 3n + 2 es par, es decir v p

Ejemplo 10. Demuestre que la suma de dos impares es par.p: r y s son impares.q: r + s es par.

Suponemos que r + s es impar y se debe demostrar que r o s son pares no de manera simult´anea.

Sea r + s impar entonces r + s = 2k + 1, k ∈ Z

Vemos que pasa cuando s es par y cuando s es impar

s es PAR, suponemos que s = 2t, t ∈ Z, entoncesr = 2k + 1 − 2t = 2 (k − t) +1 por tanto r es IM- | {

Zz

}

PAR. Cuando s es par r es

impar.

s es IMPAR, s = 2t + 1, t ∈ Z, entonces r =2k + 1 − 2t − 1 = 2k − 2t = 2 (k − t) | {

Zz }

Por tanto r es PAR. Cuando s es impar r es par. De ninguna forma bajo la premisa v q, r y s son o pares o impares por tanto se garantiza v p

2.3 Contraejemplo. Se busca un ejemplo para refu- tar el cu´al la implicacion o doble implicacion sea falsa.

Ejemplo 11. Demuestre o refute la proposicion que expresa que si x y y son números reales, (x2 = y2) ↔ (x = y)

Buscamos un ejemplo que contradiga la afirma- cion, sean x = −3 y y = 3 entonces (−3)2 = (3)2, pero −3 = 3, el resultado es falso. Este es el CON- TRAEJEMPLO.

2.4 Demostracion por contradicción o reducción al absurdo. Dado p, supongamos que se puede en-contrar una contradiccion q tal que v p → q seaverdadera, esto es, v p → F es verdadera. En-tonces la preposicion v p tiene que ser FALSA.por tanto p DEBE SER VERDADERA.

Por ejemplo una contradiccion q puede ser r∧ v rentonces podemos mostrar que v p → (r∧ v r)sea VERDADERA.

Ejemplo 12. Demuestre que √

2 es irracional.Sea p: la proposicion

√2 es irracional y supong-

amos que v p es verdadera. Entonces √

2 es racional.

Mostraremos que esto conduce a una contradiccion. Sea que

√2 es racional por tanto:

Existen dos enteros a y b de tal forma que

√2 = a/b, donde a y b no tiene FACTORES COMUNES

(es decir que no hay una fraccion equivalentea a/b m´as pequena).

Como √

2 = a/b entonces 2 = a2/b2 y portanto 2b2 = a2

Esto significa que a2 es PAR, entonces a es PAR, y a es de la forma a = 2c para alg´un c ∈ Z

Bien entonces 2b2 = 4c2 por lo que b2 = 2c2

esto significa que b2 es PAR, por tanto b es PAR.

Se ha mostrado que ambos a y b son PARES y por tanto tienen factor comun 2. Esto es una CONTRADICCION a la suposicion de que en√

2 = a/b, a y b no tiene FACTORES COMUNES

Entonces se ve que v p implica tanto r comov r donde r es la sentencia a y b son enterossin FACTORES COMUNES.

Por tanto v p es falsa y p es verdadera, entonces

√2 es IRRACIONAL.

para que v p → F sea verdadera v p debe serFALSA y por tanto p es VERDADERA.

Ejemplo 13. Demuestre por el absurdo que si 3n+2 es impar, entonces n es impar.

Suponemos que n es PAR sabiendo que 3n + 2 es IMPAR y llegamos a una CONTRADICCIO´ N. Sea n par, tambi´en suponemos que 3n + 2 es impar

n = 2q−1

por tanto 3n + 2 = 2q + 1 = 3n = 2q + 1 − 2 =,

3 para q ∈ Z por tanto es una

CON- TRADICCIO´ N por que n es UN ENTERO PAR.

Esta es una aplicacion de la tautolog´ıa ((p → q) ∧(v q) → (v p)) modus tollens dado que el argu-mento es una implicacion p → q.

Ahora como ((p → q) ∧ (v q) → (v p)) es v´ali- da p → q debe ser verdadera y p y q deben serverdaderas y asu vez v q y v p son falsas entonces((p → q ) ∧ (v q) → (v p)) ≡ ((V ∧ F ) → F ) ≡ V| {

Vz

}| {

Fz

}| {

Fz }

2.5 Demostracion por casos. Se demuestra la implicacion: (p1 ∨ p2 . . . ∨ pn) → q y resolvemos

(p1 ∨ p2 . . . ∨ pn) → q =v (p1 ∨ p2 . . . ∨ pn) ∨ q(p1 ∨ p2 . . . ∨ pn) → q = (v p1∧ v p2 . . . ∧ v pn) ∨ q(p1 ∨ p2 . . . ∨ pn) → q = q ∨ (v p1∧ v p2 . . . ∧ v pn)(p1 ∨ p2 . . . ∨ pn) → q = (q∨ v p1) ∧ (q∨ v p2) . . . ∧(q∨ v pn)(p1 ∨ p2 . . . ∨ pn) → q = (v p1 ∨ q) ∧ (v p2 ∨ q) . . . ∧ (vpn ∨ q)(p1 ∨ p2 . . . ∨ pn) → q = (p1 → q) ∧ (p2 → q) . . . ∧ (pn

→q)

Por tanto podemos decir que:

[(p1 ∨ p2 . . . ∨ pn) → q] ↔ [(p1 → q) ∧ (p2 → q) . . . ∧(pn → q)]

Ejemplo 14. Demuestre por casos que| xy |=| x || y |, donde x y y son reales.

Definicion valor absoluto:

| x |=

x si x ≥ 0

−x si x ≤ 0

Por casos entonces: p: x e y son realesq: | xy |=| x || y |p es equivalente a p1 ∨ p2 ∨ p3 ∨ p4

p1 es x ≥ 0 y y ≥

0 p2 es x ≥ 0 y y <

0 p3 es x < 0 y y ≥

0

p4 es x < 0 y y < 0

Por tanto podemos demostrar: (p1 → q) ∧ (p2 →q) ∧ (p3 → q) ∧ (p4 → q)

(p1 → q) entonces xy ≥ 0 por que x ≥ 0 yy ≥ 0, y por tanto | xy |= xy =| x || y |

(p2 → q) si x ≥ 0 y y < 0, entonces xy ≤ 0, por tanto | xy |= −xy = x(−y) =| x || y | (aqu´ı como y < 0, tenemos que | y |

= −y)

(p3 → q) si x < 0 y y ≥ 0, entonces xy ≤ 0, por tanto | xy |= −xy = (−x)y =| x || y | (aqu´ı como x < 0, tenemos que | x |= −x)

(p4 → q) si x < 0 y y < 0, entonces xy > 0, por tanto | xy |= xy == (−x)(−y) =| x || y | (aqu´ı como y < 0, tenemos que | y |= −y y x < 0, tenemos que | x |= −x)

2.6 Demostracion por equivalencia Se puede demostrar un teorema que viene dado por un bicondicional,esto es:

p ↔ q ≡ (p → q) ∧ (q → p)

Ejemplo 15. Demostrar el teorema: El entero n es impar si, y s´olo si, n2 es impar.p:El entero n es impar.q:El entero n2 es impar.

1)p → q, Hay que demostrar que si n es impar, entonces n2 es impar. (m´etodo directo).sea n impar es de la forma n = 2k + 1 dondek ∈ Z ahora vemos que pasa con n2 = (2k + 1)2

=4k2 + 4k + 1 = 2 (2k2 + 2k) +1 por tanto n2

es | {Zz

}

IMPAR. (queda demostrada p → q)

2)q → p, Hay que demostrar que si n2 es impar, entonces n es impar. (Contradiccion).supongo que n es par, por tanto es de la forma

n = 2k tomando como premisa que n2 es impar y llego a una contradiccion.ahora vemos que pasa con n2 = (2k)2 = 4k2 =2 (2k2)| {

Zz

}

por tanto n2 es PAR lo cu´al es una CON-

TRADICCIO´ N por que estamos suponiendo que

n2 es IMPARpor tanto si n2 es impar, entonces n es impar (queda demostrada p → q)

2.7 Demostracion por unicidad. Mostrar que existe un unico elemento x tal que P (x) es lo mismo que demostrar la sentencia:∃x(P (x) ∧ ∀y(y = x →v P (y)))

Entonces demostramos:1) Existencia. mostramos que existe un elementox con la propiedad deseada.2) Unicidad. Mostramos que si y = x, entonces yno tiene la propiedad deseada.

Ejemplo 15.1 Demuestre que todo entero tiene un unico inverso respecto a la suma.

Esto es si p es un entero, entonces existe un u´nico entero q tal que p + q = 0

Existencia: Si p ∈ Z, encontramos que p+q =0 cuando q = −p como q tambi´e es entero,por consiguiente, existe un entero q tal quep + q = 0

Unicidad: se muestra que dado el entero p, el entero q tal que p + q = 0 es UNICO.

supongamos que existe r ∈ Z tal que r = q

y p + r = 0 entonces p + q = p + r por tanto q = r lo que contradice la suposicion de que r = q.

Por lo tanto hay un UNICO entero q tal quep + q = 0

Ejercicios Resueltos

1. Sean m y n enteros. Demuestre que n2 = m2

si y solo si m = n o m = −n

Como es un teorema de si y solo si p ↔ (q ∨r) = (p → (q ∨ r)) ∧ ((q ∨ r) → p)

1)p → (q ∨ r)Entonces p : n2 = m2 y q :m = n o r:m = −nSea n2 = m2, n2 − m2 = 0, (n − m)(n + m) = 0entonces(n − m) = 0 y (n + m) = 0 por tanto m = n om = −n.

2) (q ∨ r) → pSea m = n o m = −n, n − m = 0 y n + m = 0,(n − m)(n + m) = 0, n2 − m2 = 0, por tanton2 = m2

2. Demuestre que la suma de un irracional y un racional es un irracional.

Por contradiccion suponemos que la suma de un irracional y un racional es racional bajo la suposicio´n de que i es irracional y r es el racional y llegamos a contradiccion llegan- do a establecer que cualquiera de los dos no cumple con la condicion de ser racional o irracional.

Sea i un irracional y r un racional entonces suponemos que i + r es un racional, es decir i + r = s donde s es racional.

Si despejamos i nos queda que i = s − r es un RACIONAL lo cual es una contradiccion por que i es un irracional.

3. Demuestre que la suma de dos racionales es un numero racional (CONTRADICCIO´ N)

Sean r y s racionales, entonces suponemos que r + s es irracional, es decir r + s = i, de-spejamos r = i − s pero como se demostr

que

la suma de un irracional y un racional es unracional, entonces podemos deducir que r es un irracional Por tanto es una contradiccion por que r es racional.

4. Demuestre que el producto de dos racionales es racional.

Por el m´etodo directo es muy f´acil se suponen que r y s son racionales y se debe

demostrar que el producto es racional.sean r = p , p, q ∈ Z para q = 0 y s = k k, t ∈ Z

q t

x

q

p

q

para t = 0 y continuamos realizando el pro-ducto r · s = p · k

= pk donde qt = 0 y pk ∈ Z yq t qt

por tanto demostramos que r ·s es un racional.

5. Demuestre que si x es irracional, 1/x tambi´en lo es.(sea p : x es irracional y q : 1/x es irracional p → q

Por el m´etodo indirecto (se demuestra v q →v p) Entonces suponemos que 1/x es racional y demostramos que x es racional.

Sea 1/x un racional entonces 1 = p donde

p, q ∈ Z, q = 0 Ahora p debe ser diferente decero por que 1 = x · 0 por tanto p = 0.

Despejamos x, x = q donde ambos son en-teros y p = 0 por lo tanto x es un RACIONAL.

6. Demuestre que si x e y son numeros reales, entoncesmax(x, y) + min(x, y) = x + y

Por casos; primero se demuestra para x ≤ y y segundo para x ≥ y.

1) Sea x ≤ y entonces max(x, y) + min(x, y) = y + x como y + x = x + y por tanto max(x, y) + min(x, y) = x + y

2) Sea x ≥ y entonces max(x, y) + min(x, y) =x + y

3. SUCESIONES, SUMATORIAS Y PRODUCTORIAS.

Sucesion. Es una lista de objetos dispuestos en orden. un primer elemento, segundo elemento, un tercer elemento y as´ı sucesivamente. esta es una sucesion FINITA.

Ejemplo 16. Si la lista empieza por un primer elemento y sigue hasta n pasos, n ∈ N es una sucesion INFINITA.

Ejemplo 17. La sucesion 1,0,0,1,0,1,0,0,1,1,1 es una sucesion finita de elementos repetidos.

Ejemplo 18. La lista 3,8,13,18,23,... es una sucesion infinita.

Ejemplo 19. Otra sucesion infinita de los cuadra- dos de todos los enteros positivos. 1,4,9,16,25,....,

3.1 F´ormula recursiva o recurrente

Ejemplo 20. Sea la sucesion infinita 3,8,13,18,23,...la podemos expresar como una formula recurrente as´ı: an = an−1 + 5 para a1 = 3 para 2 ≤ n < ∞

Ejemplo 21. Sea la sucesion infinita 5,10,20,40,80,160 la podemos expresar como una formula recurrenteas´ı: tn = 2tn−1 para t1 = 5 para 2 ≤ n ≤ 6

Ejemplo 22. Encontrar una formula recursiva para la sucesion 3,7,11,15,19,23,....

3.2 Fórmula Expl´ıcita.

Ejemplo 23. Sea la sucesion 1,4,9,16,25,...., la formula expl´ıcita es bn = n2 tal que n ≥ 1

Ejemplo 24. Sea la sucesion -4,16,-64,256,....sn = −(4)n para n ≥ 1

Ejemplo 25. Encontrar una formula expl´ıcita para la sucesion finita: 87,82,77,72,67.

3.3 Progresión geometrica. Es una sucesion de la forma:

a, ar, ar2, . . . , arn

donde el término inicial a y la razon r de la progresion son reales.

Ejemplo 26. La sucesion {bn}, bn = (−1)n

para n ≥ 1 es una progresion geométrica donde el ter- mino inicial a = −1 y la razon r = −1b1, b2, b3, b4, . . . comienza por −1, 1, −1, 1, ....

Ejemplo 27. Sea cn = 2 · 5n para n ≥ 1 es una progresion geométrica con término inicial a = 10 y razon r = 5 donde c1, c2, c3, c4, . . . comienza por10, 50, 250, 1,250, . . . ,

Ejemplo 28. Dada la siguiente progresion geom´etrica dn = 6 · (1/3)n para n ≥ 1 encontrar el t´ermino inicial y la razon.

3.4 Progresión aritmetica. Una progresion aritméticaes una sucesion de la forma:

a, a + d, a + 2d, a + 3d, . . . , a + nd

donde el término inicial a y la diferencia d son numeros reales.

Ejemplo 29. La sucesion sn = −1 + 4n para n ≥ 0 es una progresion aritmética con término inicial a = −1 y diferencia d = 4, la progresion comienza c0, c1, c2, c3, . . . comienza por −1, 3, 7, 11, . . .

Ejemplo 30. La sucesion tn = 7 − 3n para n ≥ 0 es una progresion aritmética con término inicial a = 7 y diferencia d = −3, la progresion comienza t0, t1, t2, t3, . . . comienza por 7, 4, 1, −2, . . .

3.5 Sumatorias. Usamos la notacion de la sumatoria para expresar la suma de los términos.

am, am+1, · · · , an

de la sucesion {an}. Usamos la notacion

nX aj

j=m

Para representar am + am+1 + · · · + anj es el ´ındice de la sumatoria, n l´ımite superior ym l´ımite inferior.

Ejemplo 31. Exprese la suma de los cien primeros

j=1

P5

términos de la sucesion {an}, donde an = 1/n paran = 1, 2, 3, . . .

100X 1

j=1 j

Ejemplo 32. Cuál es el valor de P5 j2

j=1 j2 = 12 + 22 + 32 + 42 +

52

= 1 + 4 + 9 + 16 + 25= 55

Ejemplo 33. supongamos que tenemos la suma:

5X 2

j=1

y queremos que el ´ındice var´ıe entre 0 y 4 en lugar de 1 y 5para conseguir esto hacemos k = j − 1 por tanto el término j2 se convierte en (k + 1)2, as´ı:

4X(k + 1)2

k=0

Es fácil ver que ambas suman 55.

Ejemplo 34. Supongamos que tenemos:

4 3X X

iji=1 j=1

Pn Pni=1 can = c i=1 anPn Pn Pn

i=1(ai + bi) = i=1 ai + i=1 biPn Pni=1(a + bi) = na + i=1 biPn n(n+1)

i=1 i = 2Pn n(n+1)(2n+1)

i=1 i2 =

6Pn n2 (n+1)2

i=1 i3 =

4Pn Pn+p n−pk=i f (k) = k=i+p f (k − p) =

P f (k + p)

j=1(aj − aj−1) = an − a0 telescopicaPn k arn+1 −a

k=0 ar = r−1

, r = 1

Primero se desarrolla la sumatoria interna:

4 3 4 4X X ij =

X(i+2i+3i) =

X 6i = 6+12+18+24 =

60i=1 j=1 i=1 i=1

Pn k=i−p

Teorema 1. Si a y r son reales y r = 0, entonces:

n arn+1 −aX arj =

r−1 si r = 1

j=0(n + 1)a si r = 1

Ejemplo 35.0 Use la formula para la suma de los t´erminos de una progresion geom´etrica para eva- luar la suma de la progresion Cn = 2 · 3n, para5 ≥ n ≥ 0:La sucesion Cn tiene como elementos 2, 2 · 3, 2 ·32, 2 · 33, 2 · 34, 2 · 35 Entonces podemos calcular

lasuma de estos elementos:

5X 2 · 3j = 2 + 2 · 3 + 2 · 32 + 2 · 33 + 2 · 34 +

2 · 35

j=0

k k

k k

k=1 6

k2 =

=

Usando el teorema 1. donde a = 2 y r = 3 tenemos:

5X 2 · 3j

=

2 · 35+1 − 2 2(36 − 1)= 36 − 1 = 728

j=03 − 1 2

Ejemplo 35. Obtener

Solucion:

P100

100X k2

k=50

49 100k=1 k

2 = P

=1 k2 +

P=50 k

2 entonces despe-jamos:

P100 100 49k=50 k

2 = P

=1 k2 −

P=1 k

2

seg´un la tabla Pn

k2 = n(n+1)(2n+1)

P100k=50

100·101·2016

−49·50·996 =338.350 -40.425=297.925

Ejemplo 36. Aplique la propiedad telescopica para calcular:

nX(2k − 1)

k=1

Sea 2k − 1 = k2 − (k − 1)2 entonces obtenemos

Pn k=1(k2 − (k − 1)2) = n2

Q8

Q4

Q10

3.6 Productorias. El producto de am, am+1, · · · , anse representa por:

nY aj

j=m

Ejemplo 37. Cuál es el valor de estos productos

i=0 i = 0

i=5 i = 5 · 6 · 7 · 8 = 1680Ejemplo 38. Cuál es el valor de estos productos

i=0 j! = 1 · 2 · 6 · 24 = 288

4. INDUCCION MATEMATICA.

Es una técnica de demostracion que se utiliza para demostrar muchos teoremas que afirman que P (n) es verdadera para todos los enteros positivos n. La induccion matemática se usa para demostrar proposiciones de la forma ∀nP (n), donde el dominio es el conjunto de los enteros positivos.

Una demostracioń por induccion de que P (n) es verdadera para todo n ∈ Z+ consiste en dos pasos:

PASO BASE: Se muestra que la proposicion P(1) es verdadera.

PASO INDUCTIVO: se muestra que la implicacionP (k) → P (k + 1) es verdadera para todo enteropositivo k.

La sentencia P (k) para un entero positivo fijo kse denomina la hipotesis de inducci´on.

2

2

n(n+1)

2

La induccion matemática expresada como regla de inferencia:

[P (1) ∧ ∀k(P (k) → P (k + 1))] → ∀nP (n)

En pocas palabras solo se muestra que si se supone que P (k) es verdadera, entonces P (k + 1) es tam- bién verdadera.

Ejemplo 39. Demostrar por induccion que la suma de los n primeros enteros positivos para n ≥ 1 es

2 es decir:

1 + 2 + 3 + · · · + n = n(n+1)

Sea P (n) : el predicado 1 + 2 + 3 + · · · + n = n(n+1)

para n ≥ 1

PASO BASE: Se muestra que P (1) es verdadera. entoncesP (1): 1 = 1(1+1) lo cuál es verdadera.

PASO INDUCTIVO: Se debe demostrar que si P (k) es verdadera entonces P (k + 1) para k ≥ 1

Sea P (k) : (hipotesis de induccion)

k(k + 1)1 + 2 + 3 + · · · + k =

2

Ahora hay que demostrar la verdad de P (k + 1) : (tesis de induccion)

1 + 2 + 3 + · · · + (k + 1) =

(k + 1)(k + 2)

2

Entonces comienza la demostracion tomando la hipotesis:

1 + 2 + 3 + · · · + k =

k(k + 1)

2

se suma (k + 1) en ambos miembros:

k(k + 1)1 + 2 + 3 + · · · + k + (k + 1) =

+ (k + 1)

2

1 + 2 + 3 + · · · + k + (k + 1) =

k(k + 1) + 2(k + 1)

2factorizando (k + 1) nos queda:

1 + 2 + 3 + · · · + k + (k + 1) =

(k + 1)(k + 2)

2Por tanto como se demostr´o la tesis de induccion, entonces P (n) es verdadero para todos los valores n ≥ 1.

Ejemplo 40. Demostrar por induccion para n ≥ 1 que:

1 + 3 + 5 + · · · + (2n − 1)

= n2

PASO BASICO: sea P (1)

1 = 12

PASO INDUCTIVO: Se debe demostrar que si P (k) es verdadera entonces P (k + 1) para k ≥ 1 Sea P (k) : (hipotesis de induccion)

1 + 2 + 3 + · · · + (2k − 1)

= k2

Ahora hay que demostrar la verdad de P (k + 1) : (tesis de induccion)

1 + 2 + 3 + · · · + (2k − 1) + (2k + 1) = (k +

1)2

Entonces comienza la demostraci´on tomando la hipotesis:

1 + 2 + 3 + · · · + (2k − 1)

= k2

se suma (k + 1) en ambos miembros:

1 + 2 + 3 + · · · + (2k − 1) + (2k + 1) = k2 + (2k + 1)

1 + 2 + 3 + · · · + (2k − 1) + (2k + 1) = k2 + 2k + 1

1 + 2 + 3 + · · · + (2k − 1) + (2k + 1) = (k

+ 1)2

Entonces queda demostrada la tesis de induccion, por tanto para n ≥ 1 P (n) es verdadera.

Ejemplo 41. Demostrar por induccion la desigualdad:n < 2n para n ≥ 1

Sea P (n) : es la proposicion n < 2n

1) PASO BA´ SICO: P (1) es verdadera, dado

que1 < 21 = 2

2) PASO INDUCTIVO: Suponemos que P (k) es verdadero y demostramos que P (k + 1) tambi´en lo es.

P (k): k < 2k para k ≥ 1P (k + 1): k + 1 < 2k+1 para n ≥ 1

k < 2k

sumamos 1 a ambos lados:

k + 1 < 2k + 1

k + 1 < 2k + 1 ≤ 2k + 2k = 2 · 2k =

2k+1

Por tanto

k + 1 < 2k+1

Ejemplo 42. (Ejercicio propuesto) Demostrar por induccion que:1 + 2 + 22 + · · · + 2n = 2n+1 − 1 para n ≥ 0

4.1 Invariante de ciclo

Es una t´ecnica para demostrar que los ciclos y programas hacen lo que se afirma que hacen.

Hacen parte de la teor´ıa de la verificacion de algoritmos.

Es una relacion entre variables que persiste a trav´es de todas las iteraciones del ciclo.

Ejemplo 43. Consideremos el siguiente codigo:

FUNCTION CUAD (A)1. C ← 02. D ← 03. WHILE (D = A)a. C ← C + Ab. D ← D + 14. RETURN(C)Este ciclo calcula el cuadrado del numero A es decir C = A2

Pasos:

1. Encontramos la invariante de ciclo que rela- cione algunas de las variables, para ello se debe realizar la prueba de escritorio.

2. La invariante nada tiene que ver con la salida.

3. Demostramos por induccion matemática la invariante de ciclo encontrada. La invariante de ciclo será la proposicion P (n)

Hay so´lo tres variables de las cuales A se com- porta como constante, C y D como variables a través de la prueba de escritorio.

La invariante de ciclo es la proposicionP (n) : Cn = A × Dn para n ≥ 0

Ahora la demostramos por induccion:

PASO BA´ SICO: Sea P (0) entonces C0 = A × D0,

0 = A × 0 por tanto se cumple.

PASO INDUCTIVO:

P (k) : Ck = A × Dk (Hipotesis) (1)P (k + 1) : Ck+1 = A × Dk+1 (Tesis) (2)

Ck+1 = Ck + A= A × Dk + A usando (1) para reemplazar en Ck

= A × (Dk + 1) Factorizando= A × Dk+1 segundo miembro de P(k+1)

y por tanto queda demostrado que P (n) : Cn =A × Dn para n ≥ 0

Ejemplo 44. Para la siguiente rutina, encontrar la invariante de ciclo y demostrarla por induccion.

RUTINA exp(N,M:R)1. R ← 12. K ← 2M3. WHILE (k > 0)a. R ← R × Nb. K ← K − 14. RETURNCALCULA: R = N 2M

La invariante de ciclo es la proposicionP (n) : Rn × N kn = N 2M

PASO BA´ SICO: P (0) : R0 × N k0 = N 2M , 1 × N 2M =

N 2M

entonces N 2M = N 2M por tanto se cumple P (0)

PASO INDUCTIVO:

P (s) : Rs × N ks = N 2M (Hipotesis)P (s + 1) : Rs+1 × N ks+1 = N 2M (Tesis)

Rs+1 × Nks+1 =

=

Rs × N Rs × N

× N ks+1 reemplazando 3.a

× N ks −1 reemplazando 3.b= Rs × N × N ks × N −1 usando

álgebra= Rs × Nks × N × N −1 agrupando= Rs × Nks

= N 2M usando la hipótesis

Por tanto queda demostrado que Rs+1 × N ks+1 =N 2M

5. DEFINICIONES RECURSIVAS.

A veces es d´ıficil definir objetos de forma expl´ıcita y sin embargo, puede resultar sencillo definirlos en términos de ellos mismos, este proceso se llama recursion.

Podemos utilizar la recursion para definir sucesiones, funciones y conjuntos.

Podemos demostrar resultados sobre conjuntos definidos recursivamente empleando el méto- do de induccion estructural.

Utilizamos dos pasos para definir una funcion recursivamente bajo el dominio de los enteros

no negativos.

1. PASO BASE: Se especifica el valor de la funcion en cero.

2. PASO RECURSIVO: Se proporciona una regla para obtener su valor en un entero a partir de sus valores en enteros m´as pequenos.

Ejemplo 45. Supongamos que f se define recursi-vamente como sigue:

f (0)f (n + 1)

==

32f (n) + 3Entonces:

f (1) = 2f (0) + 3 = 2,3 + 3 = 9f (2) = 2f (1) + 3 = 2,9 + 3 = 21f (3) = 2f (2) + 3 = 2,21 + 3 = 45f (4) = 2f (3) + 3 = 2,45 + 3 = 93

Ejemplo 46. Una definicion recursiva de la funcion factorial f (n) = n!

Primero se especifica un valor para f (0) y encontramos una regla para calcular f (n + 1) en funci´on de f (n).

f (0) = 1f (n + 1) = (n + 1)f

(n)Calculemos f (4)

f (4) = 4 · f (3) = 4 · 3f (2) = 4 · 3 · 2 · f (1) =4 · 3 · 2 · 1 · f (0) = 4 · 3 · 2 · 1 · 1 = 24

podemos tami´en obtener un codigo simple para la funcion factorial:

Función factorial (n:entero positivo)If n=1 thenFactorial(n):=1ElseFactorial(n):= n*factorial(n-1)End funcion.

Factorial (3)=3*factorial(2)=3*2*factorial(1)=3*2*1=6

Ejemplo 47. Una definicion recursiva de:

nX ak

k=0

0X ak = a0

k=0

n+1 nX ak = (

X ak ) + an+1

k=0 k=0

Definición 1. Los números de Fibonnacci, f0, f1, . . . ,se definen a partir de las ecuaciones f0 = 0, f1 = 1y

fn = fn−1 + fn−2

para n = 2, 3, 4, . . .

Ejemplo 48. Los numeros de fibonacci, f0,f1,f2

son definidos para n=2,3,4 son:f2=f1+f0=1+0=1

f3=f2+f1=1+1=2, f4=f3+f2=2+1=3, f5=f4+f3=3+2=5, f6=f5+f4=5+3=8,

función fibonacci (n:entero positivo)if n=0 thenfibonacci(0):=0elseif n=1 thenfibonnaci(1):=1elsefibonacci(n):=fibonacci(n-1)+ fibonacci (n-2)end fibonacci

Ejemplo 49. Un algoritmo recursivo para calcular el máximo comun divisor de dos enteros no negativos a y b, donde a < b.

procedure mcd (a,b)si a=0 entonces mcd (a,b)=b elsemcd(a,b):=mcd (b mod a,a)end mcd

Ejemplo 50. (Función de Ackermann)

A(m, n) =

2n si m = 00 si m ≥ 1 y n = 02 si m ≥ 1 y n = 1A(m − 1, A(m, n − 1)) si m ≥ 1 y n ≥ 2

1. Obtener A(1, 0), como m = 1 y n = 0 entonces A(1, 0) = 0 se aplica el segundo criterio de la funcio´n.

2. Obtener A(1, 1), como m = 1 y n = 1 entonces A(1, 1) = 2 se aplica el tercer criterio de la funcion.

3. Obtener A(0, 1), como m = 0 y n = 1 entonces A(0, 1) = 2(1) = 2 se aplica el primer criterio de la funcion.

4. Obtener A(2, 2). Aplicando el cuarto criterio nos queda otra recursividad A(1, A(2, 1)), ahora A(2, 1) = 2 por tercer criterio, por tan- to tenemos que calcular A(1, 2). Por el cuar- to criterio A(0, A(1, 1)), donde A(1, 1) = 2 reemplazando nos queda A(0, 2) por el primer criterio A(0, 2) = 4 por tanto A(2, 2) = 4

5. Obtener A(2, 3). Usamos el cuarto criterio A(2, 3) = A(1, A(2, 2)) ahora A(2, 2) = 4 es decir que tenemos que calcular A(1, 4) por que A(2, 3) = A(1, 4) lo podemos hacer de dos formas:

a) Aplicando la siguiente formula A(1, n) =2n si n ≥ 1, entonces A(1, 4) = 24 = 16 por tanto A(2, 3) = 16

b) Ahora sin usar formulas, solo con recursividad. A(1, 4) aplicamos el cuarto crite-

rio A(1, 4) = A(0, A(1, 3))ahora calculamos A(1, 3) = A(0, A(1, 2))

ahora calculamos A(1, 2) = A(0, A(1, 1)) como A(1, 1) = 2 aplicando el tercer criterio.A(1, 2) = A(0, 2) = 4 por el primer criterio, entonces A(1, 2) = 4ahora reemplazamos A(1, 3) = A(0, A(1, 2)) = A(0, 4) = 8 aplicando el primer criterio, entonces A(1, 3) = 8retomamos A(1, 4) = A(0, A(1, 3)) = A(0, 8) =16 por el primer criterio. POR TANTOA(2, 3) = 16

5.1 Conjuntos y estructuras bien definidas.Las definiciones recursivas de un conjunto tienendos partes:

1. Paso base. Coleccion inicial de elementos.

2. Paso recursivo. Reglas para la formacion de nuevos elementos del conjunto a partir de los que ya se conocen.

Definici´on 2. El conjunto Σ∗ de cadenas sobre el alfabeto Σ se puede definir recursivamente por:

Paso base. λ ∈ Σ∗, donde λ es la cadena vac´ıa, aquella que no tiene s´ımbolos.

Paso recursivo. Si w ∈ Σ∗ y x ∈ Σ∗, entonceswx ∈ Σ∗

Ejemplo 51. Sea Σ = {0, 1} las cadenas del conjunto Σ∗, el conjunto de todas las cadenas de bits.

Paso base. lo constituye la cadena vac´ıa λPaso recursivo. 0 y 1 cadenas que se forman re-cursivamente por primera vez, 00, 01, 10 y 11cadenas que se forman al aplicar el paso recursivo por segunda vez.

Definici´on 3. Dos cadenas se pueden combinar mediante la operacion de la concatenacion. Sea Σ un conjunto de s´ımbolos y Σ∗ el conjunto de las cadenas formadas a partir de s´ımbolos de Σ. Podemos definir recursivamente la concatenacion de dos cadenas, denotada con el s´ımbolo · como sigue:

Paso base. Si w ∈ Σ∗, entonces w · λ = w, donde λes la cadena vac´ıa.Paso recursivo. Si w1 ∈ Σ∗, w2 ∈ Σ∗ y x ∈ Σ, en-tonces w1 · (w2x) = (w1 · w2)x

Ejemplo 52. Formulas bien formadas en logica proposi- cional. Podemos definir el onjunto de formulas bi-en formadas con variables proposicionales y oper-

adores lo´gicos, adem´as de los valores V y F.

Paso base.{V, F} y p, donde p es una variable proposi- cional.Paso recursivo. Si E y F son formulas bien formadas, entonces (v E), (E ∧ F ), (E ∨ F ), (E →F ), (E ↔ F ) son formulas bien formadas.

metodos de integracion

Documents