Algebra e geometria - principio d'induzione

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∗(