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à valore vale anche per ogni n>=m

Esempio

n

∑ 2∗n−3)

(2x−3)=(2∗2−3)+(2∗3−3)+(2∗4−3)...(

1

Voglio dimostrare che per ogni n>2

vale la seguente proprietà

n

∑ 2

n−1)

(2k−3)=(

k = 2

Base di induzione

2

∑

P(2) (2k−3)=2∗2−3=1

k = 2

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

Passo di induzione

Supponiamo che valga P(n)

n

∑ 2

m−1)

(2k−3)=(

k = 2

Dimostriamo che vale P(m+1)

m+1 2

∑ da dimostrare

m+1−1)

(2k−3)=(

k = 2

n+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>=1

k =n 2

k=1

Base P(1)

1

∑ k =1

k=1

1 (1+1) / 2 = 1

Passo

Sia vera P(m)

m m∗(m+1)

∑ k = 2

m+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

n

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

k∗2 =(n−1)∗2

k=2 Voglio dimostrare che questa somma è uguale a

1)

(n+

(n−1)∗2

2

∑ k 2

P(2) = k∗2 =2∗2 =8

k=2

n = 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 = 2

m+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∗2

k=2 k=2

Abbiamo dimostrato che

m+1

∑ k (m +2)

k∗2 che è P

=m∗2 (m+1)

k = 2

Esempio

P(n) =

n 1 1 per n≥2

Π=(1− )=

k n

k = 2

n 1 1 1 1 1

Π(1− )=(1− )(1− )(1− )...(1− )

k 2 3 4 n

k = 2

Base P(2)

Passo di induzione

Ipotesi

m 1 1

Π(1− )=

k m

k=2

Voglio dimostrare P(m+1)

m+1 m

1 1 1

1−

Π(1− )=(Π(1− ))∗( )=

k k (m+1)

k = 2 k=2

1 m 1

m+1− = = +1

m

m(m+1)) m+ 1))

( (m∗(