Práctica 1: Inducción (Algoritmos III)

Ejercicio 01.01:

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=0..n+1} i^2 = Σ{i=0..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)

e)

f)

Ejercicio 01.02:

HI = Σ_i=0..n 2ⁱ = 2ⁿ⁺¹-1

• CB: n = 0

Σ_i=0..0 2ⁱ = 1

2⁰⁺¹-1 = 2-1 = 1 OK

• PI: P(n)=>P(n+1)

Σ_i=0..n+1 2ⁱ = Σ_i=0..n 2ⁱ + 2ⁿ⁺¹ = (HI) 2ⁿ⁺¹-1 + 2ⁿ⁺¹ = 2 * 2ⁿ⁺¹-1 = 2ⁿ⁺²-1 OK