Download número número demostración

1) Demuestra que todo entero positivo n mayor a 2 es primo o producto
de primos
Un número x es primo <=> x | 1 y x | x, es decir, no existe un número y tal que
x | y con x≠y.
Si x es un producto de primos =>
x | y, con y = y1*... *yn, y x=y, es decir, x = y = y1 *... * yn.
Demostración por inducción:
a. Demostrar que se cumple para n = n0 = 3
3 es un número primo por definición, pues 3 | 1, y no existe un y≠3 en Z+,
tal que 3 | y. (también se cumple para n>=2).
b. Demostrar que se cumple para n+1, suponiendo que se cumple para todos los
valores desde 3 hasta n
Asumimos que se cumple hasta n, es decir:
El n en Z+ es primo o producto de primos, es decir
n|1 y n|m, con n=m
o
x | y, con y = y1 *... *yn, y x=y, es decir, x = y = y1 *...* yn.
Para todo n en (3, ... n)
Si n+1 es primo se cumple, y no tendríamos que demostrar nada
Si n+1 no es primo => se puede expresar como el producto de dos o más números
n+1=a*b.
Como a y b deben ser menores a n+1, es decir a, b en (3, ... n). Y como
asumimos que se cumple cualesquiera números en (3, ... n). Entonces a y b
o son primos o se pueden expresar como el producto de primos. Por lo que
n+1=a*b es el producto de dos (o más) números que son el resultado de
multiplicaciones de números primos (a1,..ai, y b1, .. bj), por lo que n+1
puede expresarse como el producto de números primos, n+1= a1,..ai, * b1, ..
b j. ■
2) Demostrar que:
12 + 22 + … + n2 = n(n +1)(2n + 1) / 6, para n >= 1
Demostracion por induccion
a. Demostremos que se cumple para n=1
12 = 1(1+1)(2*1+1)/6 = 1, verdadero
b. Demostremos que se cumple para n+1, asumiendo que se cumple para n
Asumimos que se cumple para n, es decir:
12 + 22 + … + n2 = n(n +1)(2n + 1) / 6
Ahora demostremos que se cumple para n+1, queremos demostrar:
12 + 22 + … + n2 + (n+1)2 = (n+1)((n+1) +1)(2(n+1) + 1) / 6
Sabemos que
12 + 22 + … + n2 + (n+1)2 = (n(n +1)(2n + 1) / 6) + (n+1)2
=((n2+n)(2n+1)/6 ) + (n+1)2
=[(2n3+n2+2n2+n)/6 ]+ [6(n2+2n+1)/6]
=[(2n3+32+n)+(6n2+12n+6)]/6
=[2n3+9n2+13n+6]/6 (*)
Por otro lado
(n+1)((n+1) +1)(2(n+1) + 1) / 6
= [(n+1)(n+2)(2n+3)] / 6
=[(n2+2n+n+2)(2n+3)]/6
=[(n2+3n+2)(2n+3)]/6
=[2n3+3n2+6n2+9n + 4n + 6]/6
=[2n3+9n2+ 13n + 6]/6 (**)
como (*) = (**), entonces
(n(n +1)(2n + 1) / 6) + (n+1)2 = (n+1)((n+1) +1)(2(n+1) + 1) / 6
que es lo que queremos demostrar.
Por lo tanto
12 + 22 + … + n2 = n(n +1)(2n + 1) / 6, para n >= 1 ■
3) Para el problema de las Torres de Hanoi encuentra una relación de
recurrencia para el número de movimientos para mover n discos del
poste 1 al 3
El problema de las torres de Hanoi se resuelve eficientemente si movemos
todas los discos con excepción del mayor del poste 1 (2) al poste2 (1), y
luego movemos el disco mayor de la columna 1(2) a la 3. Realizando este
proceso recursivamente nos detendremos cuando en el poste 1 quede solo el
disco más pequeño. Analizando algunos valores del número de discos y el
número de movimientos se obtiene:
Para n = 1,2,3,4,5,...
m = 1,3,7,15,...
Por lo que para n discos se realizan 2n-1 movimientos. Y la relación de
recurrencia entonces es de la siguiente forma:
Condición inicial: C1=1;
Recurrencia: 2*Cn-1+1;
4) Para la siguiente secuencia encuentra la relación de recurrencia y las
condiciones iniciales:
3, 6, 9, 15, …
Esta secuencia es muy parecida a la serie Fibonacci aunque con condiciones
iniciales:
C1=3
C2=6
Cn = Cn-1+ Cn-2
5) Determina una fórmula explícita para el número de movimientos de
n discos, Cn, para el problema de las Torres de Hanoi
Sabiendo que para n = 1,2,3,4,5,... N se realizan m = 1,3,7,15,...M
movimientos, y dada la relación de recurrencia:
Condición inicial: C1=1;
Recurrencia: 2*Cn-1+1;
Tenemos que:
1) Cn
2) Cn = 2* (2*Cn-2 +1) +1
3) Cn = 2* (2*((2*Cn-3 )+1)+1) +1
4) Cn = 2* (2*((2*((2*Cn-4 )+1) )+1)+1) +1
= 2* Cn-1 +1
= 4* Cn-2 +3
= 8* Cn-3 +7
= 16* Cn-4+ 15
con k = n-1 tendríamos:
Cn = 2n-1 * C1 + 2n-1-1;
Como sabemos que C1 =1, tendriamos
Cn = 2n-1 + 2n-1-1;
= 4n-1 -1
= 2*2n-1-1
= 2n -1
Por lo que 2n -1 es la formula explicita para el número de movimientos de n
discos