Algebra e geometria - principio d'induzione

Principio di induzione

Se una proprietà (fatto) vale per n (base di induzione) e se tutte le volte che vale per m (passo di induzione) allora vale anche per n+1, allora la proprietà vale anche per ogni n >= m.

Esempio

∑ 2ⁿ - 3(2x - 3) = (2 * 2 - 3) + (2 * 3 - 3) + (2 * 4 - 3)... (1)

Dimostrazione

Voglio dimostrare che per ogni n > 2 vale la seguente proprietà:

∑ 2ⁿ - 1(2k - 3) = (k = 2)

Base di induzione

∑ P(2) (2k - 3) = 2 * 2 - 3 = 1

k = 2 (2-1)^2 = 1^2 = 1

Passo di induzione

Supponiamo che valga P(n)

∑ 2^m - 1(2k - 3) = (k = 2)

Dimostriamo che vale P(m+1)

m+1 ∑ da dimostrare

m+1 - 1)(2k - 3) = (k = 2n+1 m ∑ ∑ n+1) - 3)(2k - 3) (2k - 3) + (2(k=2 k=2(m-1)^2 + 2(m+1) – 3 = m^2 + 1 - 2m + 2m + 2 -3 = m^2

Esempio

n n+1)(∑ P(n) = n >= 1k = n 2k=1

Base P(1)

1 ∑ k = 1k=11 (1+1) / 2 = 1

Passo

Sia vera P(m)

m m*(m+1) ∑ k = 2m+1

m+1 ∑ k m+(m+1)=1+2+....+k = 1

m ∑ k +(m+1)=k = 1

m*(m+1) m+ 2)(= m+1)=(m+1)+(2 2

Esempio

∑ k (n +1) = 2*2^2 + 3 * 2^3 + 4 * 2^4 + … + n * 2^n n>=2k*2 =(n-1)*2k=2

Voglio dimostrare che questa somma è uguale a 1)(n+(n - 1)*22∑ k 2

P(2) = k*2 = 2*2 = 8k=2n = 3 k 2 3 3 3 3 5∑ k*2 = 2*2 + 3*2 = 2 + 3*2 = 2 (1+3)*2(3-1) * 2^4 = 2*2^4 = 2^5

Passo di induzione

m∑ k (m+1)

Vera P(m) = k*2 2=(m-1)k = 2m+1 m ∑ ∑k l 1)(m +1) (m+1) (m+1 ) (m+ (m +2)k*2 k*2= +(m+1)*2 =(m-1)*2 *2 =2 (2m)=m*2k=2 k=2

Abbiamo dimostrato che m+1∑ k (m +2)k*2 è P=m*2 (m+1)k = 2

Esempio

P(n) = n 1 1 per n≥2Π=(1- )=k nk = 2n 1 1 1 1 1Π(1- )=(1- )(1- )(1- )...(1- )k 2 3 4 nk = 2

Base P(2)

Passo di induzione

Ipotesi m 1 1Π(1- )=k mk=2

Voglio dimostrare P(m+1)

m+1 m1 1 11- Π(1- )=(Π(1- ))*( )=k k (m+1)k = 2 k=21 m 1m+1- = = +1mm(m+1)) m+ 1))

(m*(1 1 1 1&l