per ogni n≥1 vale l’uguaglianza: 2 3 n n 2 2 2 n 2

Matematica Discreta a.a. 2006 - 2007 Foglio 1

Esercizi sull’ induzione

Usando il principio di induzione provare i seguenti asserti:

1. per ogni n≥1 il numero n³+2n è divisibile per 3.

2. per ogni n≥1 vale l’uguaglianza: _{2 3 n n} 2

2 2 n

2 ... n 2

3 2

2 2

1 + + + + = − +

3. per ogni n n≥2 vale l’uguaglianza:

2n n ) 1

n (1 1 16)

)(1 1 9 )(1 1 4

(1−1 − − ⋅⋅⋅ − ₂ = +

4. per ogni n≥1 vale l’uguaglianza: 1+2²+3²+…+n² =

6

1) 1)(2n

n(n+ +

5. per ogni n≥1 vale l’uguaglianza:

1 n

n 1) n(n ... 1 4 3

1 3 2

1 2 1

1

= + + +

⋅ +

⋅ +

⋅ +

6. per ogni n≥1 vale l’uguaglianza: 2+2²+2³+…2ⁿ =2(2ⁿ-1) 7. per ogni n≥1 vale l’uguaglianza: 1⋅2+2⋅3+3⋅4 +…+n(n+1)=

3

2) 1)(n

n(n+ +

8. per ogni n≥1 vale l’uguaglianza: 1(1!)+2(2!)+3(3!)+…+n(n!)= [(n+1)!] -1

RISPOSTE

1. Per n=1 …è vero. Poi: (n+1)³+2(n+1) = (n³+2n)+3n(n+1)+3. Ora si usa l'ipotesi induttiva per cui n³+2n=3h con h∈ù…e si conclude:(n+1)³+2(n+1) multiplo di 3.

2. Per n=1 è vero. Poi per l'ipotesi induttiva si ha:

_{2 3 n n 1}

2 1 n 2 ... n 2

3 2

2 2 1

+

+ + +

+

+ = _{n n 1}

2 1 n 2

2

2 n +₊

+ +

− = …… = ⎟

⎠

⎜ ⎞

⎝

−⎛ +_n+1 2

3

2 n . c.v.d.

3. Si riscrive così

2n n ) 1

n (1 1 4 )

)(1 1 3 )(1 1 2

(1 1_{2 2 2 2} +

=

−

⋅

⋅

⋅

−

−

− . Per n=2 si ha

4

2 1 4

1− 1 = + : vero. Poi usando l’ipotesi induttiva si ha:

)

1) (n )( 1 2n

n (1 1) ) (n - 1 n )(1 (1 1 4 )

)(1 1 3 )(1 1 2

(1 1_{2 2 2 2 2 2}

− +

= +

− +

⋅

⋅

⋅

−

−

− 1

=

1) 2(n

2 ... n

+

= + .

4. Base induzione:…vera. Passo:per l’ipotesi induttiva si ha:

...

1) 6 (n

1) 1)(2n 1) n(n

(n n ...

3 2

1 ^{2 2 2 2} + + + + ² =

= + + + + + +

6

6) 1)(2n

(n+ ² + +

= 7n che coincide con

6

3) 2)(2n 1)(n

(n+ + + c.v.d.

5. Per n=1 … ok ! Poi si usa l’ipotesi induttiva:

(n 1)(n 2)

1 1

n n 2) 1)(n (n

1 1)

n(n ... 1 4 3

1 3 2

1 2 1

1

+ + +

= + + + +

+ +

⋅ +

⋅ +

⋅ + =

= … = … 2 n

1 n

+

+ c.v.d.

6. Per n=1 si ha : 2¹=2(2¹-1) ok ! Poi usando l’ipotesi induttiva

2¹+2²+2³+…+2ⁿ+2ⁿ⁺¹ = 2(2ⁿ-1) +2ⁿ⁺¹ , che grazie alle proprietà delle potenze risulta = 2(2ⁿ-1) +2⋅2ⁿ = 2(……… ) = … = 2(2ⁿ⁺¹-1) c.v.d.

7. Analogo ai precedenti: la tesi è 1⋅2+2⋅3+3⋅4+…+n(n+1)+ (n+1)(n+2) =

3

3) 2)(n 1)(n

(n+ + + .

8. Base induzione:…vera. Passo:Si parte da 1(1!)+2(2!)+3(3!)+…+n(n!)+(n+1)[(n+1)!]

che,per l’ipotesi induttiva è uguale a [(n+1)!] -1+(n+1)[(n+1)!]. Si raccoglie e si ricava [(n+1)!] (1+n+1) -1 ossia [(n+2)!]-1 . c.v.d.