Bloque de Colores

Equivalencias Básicas de Sumatorias

Icono de Post May 7 2009 :: Algebra, Apuntes ::

Sumatoria de una constante    

Sea k constante se cumple que:

n = 1 m k = mk

Sumatoria de un polinomio

n = 1 m 2 a + b 2 c = n = 1 m 2 a + n = 1 m b 2 n = 1 m c

Sumatoria de un producto

Sea c constante, se cumple que:

n = 0 m ck = c . n = 0 m k

Sumatoria de una potencia ( Progresión geometrica )

Sea | r | > 1:
n = 1 m r n = r n + 1 1 r 1

Equivalencias

n = 0 m n = n ( n + 1 ) 2

n = 0 m n 2 = n ( n + 1 ) ( 2 n + 1 ) 6

n = 0 m n 3 = n 2 ( n + 1 ) 2 4

Estas equivalencias pueden demostrarse facilmente por inducción, hay más para diversos grados de n en esta pagína: PlanetMath: Summation.

Cambio de Limites

n = a b f ( k ) = n = a + r b + r f ( k r )

Autor: Emiliano Martínez Luque.

Comments Off on Equivalencias Básicas de Sumatorias

Ejercicio 3.42 de THRTLMP

Icono de Post August 4 2008 :: Algebra, Lógica ::

Se nos pide demostrar si hay o no hay triplos de primos de la forma ( p , p+2, p+4 ) que no sean ( 3, 5, 7 ). Este ejercicio me gusto porque estuve unos 15 minutos pensando antes de poder resolverlo. Bueno, despues de mirar un poco la Criba de Eratosthenes y pensar en la aritmetica mod( 3 ) finalmente encontre la forma:

Demostración

Sabemos que p es primo por lo tanto no es multiplo de 3, o sea que es o de la forma 3k + 1 o 3k + 2 con k ∈ Z. Supongamos que es de la forma 3k + 1, entonces p + 2 = 3k + 1 + 2 = 3 ( k + 1 ) entonces p + 2 es multiplo de 3 y no es primo. Ahora si es de la forma 3k + 2 entonces p + 4 = 3k + 2 + 4 = 3 ( k + 2) por lo que p + 4 es multiplo de 3 y no es primo. De lo que sigue que no existen triplos de primos de la forma ( p, p+2, p+4 ) salvo ( 3, 5, 7 ).

De manera similar puede resolverse el ejercicio 3.43, que es demostrar que siendo p primo, no existen primos de la forma ( p2 + 2 ) ≠ 11 o lo que es lo mismo con p ≠ 3 .

Demostración

Si p es primo ≠ 3 , entonces necesariamente no es multiplo de 3, o sea que es de la forma 3k + 1 o 3k + 2 con k ∈ Z. Supongamos que es de la forma 3k + 1, entonces p2 + 2 = ( 9k2 + 6k + 1) + 2 = 3 ( 3k2 + 2k + 1 ) , porque lo que es multiplo de 3 y no es primo. Supongamos entonces que es de la forma 3k + 2, entonces p2 + 2 = ( 9k2 + 12k + 4) + 2 = 3 ( 3k2 + 4k + 2 ), multiplo de 3 y no primo. Por exhaustación de casos, la proposición queda demostarda.

Bueno termine con el cápitulo 3, si alguién tiene la solución del ejercicio 3.34 me haría un favor enorme si me lo mandan porque estuve un buen rato y no lo pude resolver. Mierda, me gustaría poder dedicarle más tiempo, pero si me cuelgo no avanzo más y quiero seguir aprendiendo Haskell.

Autor: Emiliano Martínez Luque.

Comments Off on Ejercicio 3.42 de THRTLMP

La inducción completa es un arma poderosa

Icono de Post August 4 2008 :: Algebra, Lógica ::

Resolución del ejercicio 3.41 de The Haskell Road To Logic, Math and Programming. Demostrar que 2n – 1

( 2n– 1 ) es un numéro perfecto ( la suma de todos sus divisores propios es igual al mismo número ) si ( 2n– 1 ) es primo ( un primo de mersenne en realidad ). Como es primo se puede descomponer en los siguientes divisores propios:

2n – 1

( 2n– 1 ) = 1 + 2 + 22 + …. + 2n – 1 + ( 2n– 1 ) + 2.( 2n-1 ) + 22.( 2n-1 ) + …. + 2n – 2.( 2n-1 )

= 1 + 2 + 22 + …. + 2n – 1 + ( 2n– 1 ) + ( 2n + 1 -2 ) + ( 2n + 2

– 22 ) + …. + ( 22n – 2

– 2n – 2)
Realizando las multiplicaciones de los terminos del final.

= 2n – 1
+ 2n + 2n + 1 +  2n + 2

+ …. + 22n – 2

Simplificando terminos equivalentes pero negativos.

= 2n – 1

( 1 + 2 + 22 + …. + 2n – 1 )
Por propiedades de la exponenciación.

= 2n – 1( 2  – 1 + 2 + 22 + …. + 2n – 1 )
Porque 2 – 1 = 1

Y es exactamente acá donde la cosa se pone interesante.  Ya logre 2n – 1 y el – 1 en el segundo termino. Pero me queda demostrar que ( 2 +2 + 22 + …. + 2n – 1 ) = 2n .

En principio no parece demasiado complicado.. digamos:

2 + 2 = 4 = 22

22 + 22 = 8 = 23

23 + 23 = 16 = 24

…….

2n – 1

+ 2n – 1 = 2n

Que se puede probar fácilmente por inducción completa.

2n = 2n – 1

+ 2n – 1

1) Demostrarlo para n = 1, es trivial: 2 = 1 +1.

2) 2n = 2n – 1
+ 2n – 1

=> 2n + 1
= 2n + 2n
2n + 2n = 2.(2n – 1

+ 2n – 1) = 2.2n (Por hipotesis) =  2n + 1

Ahora, en el texto todavía no vimos inducción y hay un capitulo entero dedicado al tema. El tema es como probar esto sin usar inducción completa. Ni la más puta idea.

DUH! Agregado ( 1 mes después releyendo mi post y sorprendiéndome por mi absoluta falta de lucidez al momento de escribirlo )

2n – 1 + 2n – 1 = 2. (2n – 1) = 2n

Autor: Emiliano Martínez Luque.

Comments Off on La inducción completa es un arma poderosa

Lazy Evaluation ( Evaluación perezosa ) en Haskell

Icono de Post August 4 2008 :: Algebra, Haskell, Programación Funcional ::

Del capitulo 3 de The Haskell Road To Logic, Math and Programming:



sieve :: [Integer] -> [Integer]

sieve (0:xs) = sieve xs

sieve (n : xs) = n : sieve ( mark xs 1 n )

	where

	mark :: [Integer] -> Integer -> Integer -> [Integer]

	mark (y:ys) k m | k == m 	= 0 : (mark ys 1 m)

					| otherwise = y : (mark ys (k+1) m)

LLamando a la función con sieve [2..] , nos retorna los números primos por el método de Criba de Eratosthenes.

Lo interesante es pensar en como la lista infinita que se le paso como parámetro es evaluada por Haskell. Si pensamos desde una perspectiva de programación imperativa, es imposible que una función sea procesada por otra función hasta que no haya terminado su procesamiento, entonces como es posible que sieve devuelva resultados si en este caso mark devuelve una lista infinita. Este es un ejemplo de Lazy Evaluation y una muy buena explicación se puede encontrar acá y con más profundidad acá.

Ejercicio 3.39 de THRTLMP

Agrego este ejercicio porque me gusto y es otro ejemplo de Lazy Evaluation. Se nos pide refutar la afirmación de que si p1, p2, … , pk son todos los números primos menores a n, entonces ( p1 . p2 . … . pk ) + 1 es también primo, para todo n perteneciente a los naturales.



filterMinor :: [Integer] -> Integer -> [Integer]

filterMinor [] _ = []

filterMinor (x:xs) n 	| x >= n	= []

			| otherwise = x : filterMinor(xs) n



proveSTforN :: Integer -> Bool

proveSTforN n = prime (product( filterMinor (sieve [2..]) n ) + 1)



proveST :: Bool

proveST = all (==True) (map proveSTforN [1..])

Y para ver los resultados:



proveSTforNShow :: Integer -> (Integer, Integer, Bool)

proveSTforNShow n = (n, a, prime(a)) 

		where

		a = product( filterMinor (sieve [2..]) n ) + 1



proveSTShow :: [(Integer, Integer, Bool)]

proveSTShow = map proveSTforNShow [2..]

Generalizando demostraciones

Icono de Post July 25 2008 :: Algebra, Lógica ::

En el ejercicio 3.21.12 del libro Algebra I de Armando Rojo, se nos pide demostrar por inducción completa que:

3 / 8n – 5n o lo que es lo mismo 8n – 5n = 3k; k ∈ Z .

Lo interesante es que cuando curse Algebra y Matematica Discreta había un ejercicio bastante similar ( Demostrar que 5 / 7n – 2n).  Se me ocurrio entonces que la demostración podía generalizarse.

Demostración Inicial: 3 / 8n – 5n

1) Primer paso demostrar para n=1

3 / 8 -5 => 3 / 3
Lo cual es evidentemente cierto.

2) Paso Inductivo:
8n – 5n = 3k; k ∈ Z => 8n+1

– 5n+1
= 3w; w ∈ Z

Demostración:

3 / 8n+1

– 5n+1
=> 8n+1

– 5n+1
= 3k; k ∈ Z

8n+1

– 5n+1
= 8 . 8n – 5 . 5n
Por Propiedades de la exponenciación.

= ( 3 + 5 ). 8n – 5 . 5n    
Porque 8 = 3 + 5.

= 3 .8n + 5. 8n + – 5 . 5n
Por distributividad.

= 3 .8n + 5. ( 8n – 5n )
Por dirtributividad.

= 3 .8n + 5. ( 3.k )
Por hipotesis.

= 3 ( 8n + 5k )    
Por Distributividad:

Como ( 8n + 5k ) ∈ Z ; queda demostrada la proposición inicial.

Demostración generalizada: Sean a,b,c ∈ Z; a = b -c se cumple que a / bn – cn

1) Primer paso demostrar para n=1

b1 – c1

= a         (Por Definicion de a,b,c)

2) Paso Inductivo:
bn – cn = ak; k ∈ Z => bn+1

– cn+1
= aw; w ∈ Z

Demostración:

a / bn+1

– cn+1
=> bn+1
– cn+1

= ak; k ∈ Z

bn+1
– cn+1
= b . bn – c . cn
Por Propiedades de la exponenciación.

= ( a + c ). bn – c . cn
Porque a = b – c => b = a + c

=  a. bn + c .bn – c . cn
Por distributividad.

= a .bn + c. ( bn – cn )
Por dirtributividad

= a .bn + c. ( a.k )
Por hipotesis.

= a ( bn + ck )
Por Distributividad.

Como ( bn + ck ) ∈ Z queda demostrada la proposición.

Referencias

Algebra I; Rojo, Armando; 21ª ed, Magister Eos; 2006

Autor: Emiliano Martínez Luque.

Comments Off on Generalizando demostraciones

Algunas demostraciones simples cuya estructura me llamo la atención

Icono de Post May 23 2008 :: Algebra, Lógica ::

Demostrar que si a es par <=> a2 es par

Como es doble implicación tengo que demostrar: 1) a es par => a2 es par ∧  2) a2 es par => a es par

1) a es par => a2 es par

a es par => a = 2k; k ∈ Z => a2 = ( 2k )2 => a2 = 4k2 => a2 = 2( 2k2 )
Como ( 2k2 ) ∈ Z => a2 es par.

2) a2 es par => a es par

Para esta parte de la demostración se usa el contrareciproco. ( p => q ≡ ¬q => ¬p )

a2 es par => a es par ≡ a es impar => a2 es impar

a es impar => a = 2k +1; k ∈ Z => a2 = ( 2k+ 1 )2 => a2 = 4k2 + 4k + 1 => a2 = 2( 2k2 + 2k ) + 1
Como ( 2k2 + 2k ) ∈ Z => a2 es impar y la proposición queda demostrada.

Demostrar que el producto de 2 números consecutivos es par.

El producto de dos números consecutivos puede escribirse como a.( a+1 ). La demostración es por exhaustación de casos.

1) Supongamos que a es par

a es par => a = 2k; k ∈ Z => a. ( a + 1) = 2k . ( 2k + 1)
Como k . ( 2k  + 1 ) ∈ Z => a. ( a + 1)  es par.

2) Supongamos que a es impar

a es impar => a = 2k + 1; k ∈ Z => a. ( a + 1) => 2k + 1. ( 2k + 1 + 1) = 2k +1 . ( 2k + 2 ) = ( 2k + 1) . 2 (k + 1) = 2 ( 2k + 1) . (k + 1)
Como ( 2k + 1) . (k + 1) ∈ Z => a. ( a + 1)  es par.

Demostrar que si p es primo y p / a.b => p/a ∨ p/b

Es una implicación que tiene una disyunción en la conclusión.

Supongamos que p/a, entonces listo no queda nada que demostrar.

Ahora si ¬(p/a) => p y a son coprimos o sea que ( p ; a ) = 1 => ∃ n; s ∈ Z / p.n + a.s = 1

Como p/a.b => a.b = pk; k ∈ Z
Tomamos:
p.n + a.s = 1

Multiplicamos ambos terminos por b:
b.p.n + a.b.s = b

Sustituimos a.b por p.k:
b.p.n + p.k.b.s = b

Despejamos p:
p (bn + kbs) = b

Como (bn + kbs) ∈ Z, queda demostrado que p/b y por exhaustación de casos queda demostrado que si p es primo y p / a.b => p/a ∨ p/b .

Referencias

Apuntes de Clase de Algebra y Matemática Discreta cursada con Marcela Wilder en ella Universidad de Palermo, el segundo cuatrimestre de 2007

Autor: Emiliano Martínez Luque.

Comments Off on Algunas demostraciones simples cuya estructura me llamo la atención