Diferencia entre revisiones de «Práctica 1: Inducción (Algoritmos III)»
| (No se muestran 18 ediciones intermedias de 2 usuarios) | |||
| Línea 1: | Línea 1: | ||
==Ejercicio 01:== | {{Back|Algoritmos y Estructuras de Datos III}} | ||
==Ejercicio 01.01:== | |||
<br>a) | <br>a) | ||
P(n) = Σ{i=1..n} i = n(n+1)/2 | |||
* CB: n = 1 | |||
Σ{i=1..1} i = 1 | |||
1(1+1)/2 = 1 OK | |||
* PI: P(n)=>P(n+1) | |||
Σ{i=1..n+1} i = Σ{i=1..n} i + n+1 = (HI) n(n+1)/2 + 2(n+1)/2 = (n+2)(n+1)/2 OK | |||
<br>b) | <br>b) | ||
P(n) = Σ{i=0..n} (2*i+1) = (n+1)^2 | |||
* CB: n = 0 | |||
Σ{i=0..0} (2*i+1) = 1 | |||
(0+1)^2 = 1 OK | |||
* PI: P(n)=>P(n+1) | |||
Σ{i=0..n+1} (2*i+1) = Σ{i=0..n} 2*i+1 + 2*(n+1)+1 = (HI) (n+1)^2 + 2n + 3 = n^2 + 2*n + 1 + 2n + 3 = n^2 + 4*n + 4 = (n+2)^2 OK | |||
<br>c) | <br>c) | ||
P(n) = Σ{i=1..n} i^2 = n(n+1)(2n+1)/6 | |||
* CB: n = 1 | |||
Σ{i=1..1} i^2 = 1 | |||
1(1+1)(2*1+1)/6 = 1 OK | |||
* PI: P(n)=>P(n+1) | |||
Σ{i=1..n+1} i^2 = Σ{i=1..n} i^2 + (n+1)^2 = (HI) n(n+1)(2n+1)/6 + (n+1)^2 = [ n(n+1)(2n+1)/6 + 6*(n+1)^2 ]/6 = (n+1)[ n(2n+1)/6 + 6*(n+1) ]/6 = (n+1)[ 2*n^2 + n + 6*n + 6 ]/6 = (n+1)(n+2)(2n+3)/6 OK | |||
<br>d) | <br>d) | ||
P(n) = Σ{i=1..n} (-1)^i*i^2 = (-1)^n*n(n+1)/2 | |||
* CB: n = 1 | |||
Σ{i=1..1} (-1)^i*i^2 = -1 | |||
(-1)^1*1(1+1)/2 = -1 OK | |||
* PI: P(n)=>P(n+1) | |||
Σ{i=1..n+1} (-1)^i*i^2 = Σ{i=1..n} (-1)^i*i^2 + (-1)^(n+1)*(n+1)^2 = (HI) (-1)^n*n(n+1)/2 + (-1)^(n+1)*(n+1)^2 = [ (-1)^n*n(n+1) + 2(-1)^(n+1)*(n+1)^2 ]/2 = (-1)^(n+1) [ -n(n+1) + 2*(n+1)^2 ]/2 = (-1)^(n+1)*(n+1) [ 2*(n+1)-n ]/2 = (-1)^(n+1)*(n+1) [ 2n-2-n ]/2 = (-1)^(n+1)*(n+1)(n+2)/2 OK | |||
<br>e) | <br>e) | ||
P(n) = ( Σ{i=1..n} i )^2 = Σ{i=1..n} i^3 | |||
* CB: n = 1 | |||
( Σ{i=1..1} i )^2 = 1 | |||
Σ{i=1..1} i^3 = 1 OK | |||
* PI: P(n)=>P(n+1) | |||
( Σ{i=1..n+1} i )^2 = ( Σ{i=1..n} i + n+1 )^2 = ( Σ{i=1..n} i )^2 + 2*( Σ{i=1..n} i )*(n+1) + (n+1)^2 = (HI) = Σ{i=1..n} i^3 + 2*(n(n+1)/2)*(n+1) + (n+1)^2 = Σ{i=1..n} i^3 + n*(n+1)^2 + (n+1)^2 = Σ{i=1..n} i^3 + (n+1)^2 * (n+1) = Σ{i=1..n} i^3 + (n+1)^3 = Σ{i=1..n+1} i^3 OK | |||
<br>f) | <br>f) | ||
==Ejercicio 02:== | P(n) = Σ{i=1..n} i*i! = (n+1)!-1 | ||
* CB: n = 1 | |||
Σ{i=1..1} i*i! = 1 | |||
(1+1)!-1 = 1 OK | |||
* PI: P(n)=>P(n+1) | |||
Σ{i=1..n+1} i*i! = Σ{i=1..n} i*i! + (n+1)(n+1)! = (HI) (n+1)!-1 + (n+1)(n+1)! = (n+1)!(n+1 + 1) - 1 = (n+1)!*(n+2) - 1 = (n+2)!-1 OK | |||
==Ejercicio 01.02:== | |||
HI = Σ<sub>i=0..n</sub> 2<sup>i</sup> = 2<sup>n+1</sup>-1 | HI = Σ<sub>i=0..n</sub> 2<sup>i</sup> = 2<sup>n+1</sup>-1 | ||
| Línea 18: | Línea 80: | ||
Σ<sub>i=0..n+1</sub> 2<sup>i</sup> = Σ<sub>i=0..n</sub> 2<sup>i</sup> + 2<sup>n+1</sup> = (HI) 2<sup>n+1</sup>-1 + 2<sup>n+1</sup> = 2 * 2<sup>n+1</sup>-1 = 2<sup>n+2</sup>-1 OK | Σ<sub>i=0..n+1</sub> 2<sup>i</sup> = Σ<sub>i=0..n</sub> 2<sup>i</sup> + 2<sup>n+1</sup> = (HI) 2<sup>n+1</sup>-1 + 2<sup>n+1</sup> = 2 * 2<sup>n+1</sup>-1 = 2<sup>n+2</sup>-1 OK | ||
==Ejercicio 03:== | ==Ejercicio 01.03:== | ||
==Ejercicio 04:== | k+2k+4k+..+ Σ{i=0..n} 2^i*k = k*Σ{i=0..n} 2^i = k*[2^(n+1)-1] | ||
==Ejercicio 05:== | |||
==Ejercicio 06:== | ==Ejercicio 01.04:== | ||
==Ejercicio 07:== | P(n) = 2^n > n^2 | ||
* CB: n = 5 | |||
2^5 > 5^2 = 32 > 25 OK | |||
* PI: P(n)=>P(n+1) | |||
2^(n+1) = 2*2^n > 2n^2 >? (n+1)^2 | |||
2n^2 > n^2+2n+1 <=> n^2-2n-1 > 0 => n > 1 + sqrt(2) => n >= 3 => Cumple para n >= 5 OK | |||
==Ejercicio 01.05:== | |||
Sean q^n = [ (1+√5)/2 ]^n, qx^n = [ (1+√5)/2 ]^n | |||
P(n) = Fn = [ q^(n+1)-qx^(n+1) ]/√5 | |||
* CB: n = 2 | |||
F2 = F1+F0 = [ q^3-qx^3 ]/√5 <=> 2 = 2 OK | |||
* PI: P(n)=>P(n+1) | |||
F(n+1) = Fn + F(n-1) = (HI) [ q^(n+1)-qx^(n+1) ]/√5 + [ q^(n)-qx^(n) ]/√5 = [ q^n*(q+1)-qx^n*(qx+1) ]/√5 = [ q^(n+2)-qx^(n+2) ]/√5 OK | |||
==Ejercicio 01.06:== | |||
Suponer x2 con CB x1 | |||
==Ejercicio 01.07:== | |||
Suponer a^(n-2) con CB 1 | |||
[[Category: Prácticas]] | |||
Revisión actual - 02:15 28 mar 2011
Ejercicio 01.01:[editar]
a)
P(n) = Σ{i=1..n} i = n(n+1)/2
- CB: n = 1
Σ{i=1..1} i = 1
1(1+1)/2 = 1 OK
- PI: P(n)=>P(n+1)
Σ{i=1..n+1} i = Σ{i=1..n} i + n+1 = (HI) n(n+1)/2 + 2(n+1)/2 = (n+2)(n+1)/2 OK
b)
P(n) = Σ{i=0..n} (2*i+1) = (n+1)^2
- CB: n = 0
Σ{i=0..0} (2*i+1) = 1
(0+1)^2 = 1 OK
- PI: P(n)=>P(n+1)
Σ{i=0..n+1} (2*i+1) = Σ{i=0..n} 2*i+1 + 2*(n+1)+1 = (HI) (n+1)^2 + 2n + 3 = n^2 + 2*n + 1 + 2n + 3 = n^2 + 4*n + 4 = (n+2)^2 OK
c)
P(n) = Σ{i=1..n} i^2 = n(n+1)(2n+1)/6
- CB: n = 1
Σ{i=1..1} i^2 = 1
1(1+1)(2*1+1)/6 = 1 OK
- PI: P(n)=>P(n+1)
Σ{i=1..n+1} i^2 = Σ{i=1..n} i^2 + (n+1)^2 = (HI) n(n+1)(2n+1)/6 + (n+1)^2 = [ n(n+1)(2n+1)/6 + 6*(n+1)^2 ]/6 = (n+1)[ n(2n+1)/6 + 6*(n+1) ]/6 = (n+1)[ 2*n^2 + n + 6*n + 6 ]/6 = (n+1)(n+2)(2n+3)/6 OK
d)
P(n) = Σ{i=1..n} (-1)^i*i^2 = (-1)^n*n(n+1)/2
- CB: n = 1
Σ{i=1..1} (-1)^i*i^2 = -1
(-1)^1*1(1+1)/2 = -1 OK
- PI: P(n)=>P(n+1)
Σ{i=1..n+1} (-1)^i*i^2 = Σ{i=1..n} (-1)^i*i^2 + (-1)^(n+1)*(n+1)^2 = (HI) (-1)^n*n(n+1)/2 + (-1)^(n+1)*(n+1)^2 = [ (-1)^n*n(n+1) + 2(-1)^(n+1)*(n+1)^2 ]/2 = (-1)^(n+1) [ -n(n+1) + 2*(n+1)^2 ]/2 = (-1)^(n+1)*(n+1) [ 2*(n+1)-n ]/2 = (-1)^(n+1)*(n+1) [ 2n-2-n ]/2 = (-1)^(n+1)*(n+1)(n+2)/2 OK
e)
P(n) = ( Σ{i=1..n} i )^2 = Σ{i=1..n} i^3
- CB: n = 1
( Σ{i=1..1} i )^2 = 1
Σ{i=1..1} i^3 = 1 OK
- PI: P(n)=>P(n+1)
( Σ{i=1..n+1} i )^2 = ( Σ{i=1..n} i + n+1 )^2 = ( Σ{i=1..n} i )^2 + 2*( Σ{i=1..n} i )*(n+1) + (n+1)^2 = (HI) = Σ{i=1..n} i^3 + 2*(n(n+1)/2)*(n+1) + (n+1)^2 = Σ{i=1..n} i^3 + n*(n+1)^2 + (n+1)^2 = Σ{i=1..n} i^3 + (n+1)^2 * (n+1) = Σ{i=1..n} i^3 + (n+1)^3 = Σ{i=1..n+1} i^3 OK
f)
P(n) = Σ{i=1..n} i*i! = (n+1)!-1
- CB: n = 1
Σ{i=1..1} i*i! = 1
(1+1)!-1 = 1 OK
- PI: P(n)=>P(n+1)
Σ{i=1..n+1} i*i! = Σ{i=1..n} i*i! + (n+1)(n+1)! = (HI) (n+1)!-1 + (n+1)(n+1)! = (n+1)!(n+1 + 1) - 1 = (n+1)!*(n+2) - 1 = (n+2)!-1 OK
Ejercicio 01.02:[editar]
HI = Σi=0..n 2i = 2n+1-1
- CB: n = 0
Σi=0..0 2i = 1
20+1-1 = 2-1 = 1 OK
- PI: P(n)=>P(n+1)
Σi=0..n+1 2i = Σi=0..n 2i + 2n+1 = (HI) 2n+1-1 + 2n+1 = 2 * 2n+1-1 = 2n+2-1 OK
Ejercicio 01.03:[editar]
k+2k+4k+..+ Σ{i=0..n} 2^i*k = k*Σ{i=0..n} 2^i = k*[2^(n+1)-1]
Ejercicio 01.04:[editar]
P(n) = 2^n > n^2
- CB: n = 5
2^5 > 5^2 = 32 > 25 OK
- PI: P(n)=>P(n+1)
2^(n+1) = 2*2^n > 2n^2 >? (n+1)^2
2n^2 > n^2+2n+1 <=> n^2-2n-1 > 0 => n > 1 + sqrt(2) => n >= 3 => Cumple para n >= 5 OK
Ejercicio 01.05:[editar]
Sean q^n = [ (1+√5)/2 ]^n, qx^n = [ (1+√5)/2 ]^n
P(n) = Fn = [ q^(n+1)-qx^(n+1) ]/√5
- CB: n = 2
F2 = F1+F0 = [ q^3-qx^3 ]/√5 <=> 2 = 2 OK
- PI: P(n)=>P(n+1)
F(n+1) = Fn + F(n-1) = (HI) [ q^(n+1)-qx^(n+1) ]/√5 + [ q^(n)-qx^(n) ]/√5 = [ q^n*(q+1)-qx^n*(qx+1) ]/√5 = [ q^(n+2)-qx^(n+2) ]/√5 OK
Ejercicio 01.06:[editar]
Suponer x2 con CB x1
Ejercicio 01.07:[editar]
Suponer a^(n-2) con CB 1
