1

Esercizi sull’induzione

Dimostrare per induzione

i 3i =1

n

∑ =n 2 (n +1)2

4

1i(i+1)i=1

n

∑ =nn+1

i=0

n

∑ (2i+1)2 = (n+1)(2n+1)(2n+3)3

Soluzione Eeercizio

Dimostrare per induzione:

∀n: (n∈N) ∧ (n ≥ 1) ⇒ (n + n2) è pari

2

Soluzione

Caso base: se n=1, n + n2 = 2, quindi l'affermazione è vera. Caso induttivo (n=k+1): (k+1)+ (k+1) 2 = k + 1 + k2+ 2k + 1 =

= (k + k2) + 2(k+1)   (k + k2) è pari per ipotesi induttiva

Ricorsione

Che cosa è la ricorsione in generale?

n  L’annidarsi di cose entro le cose e le sue variazioni. n  Qualche esempio: la scatole cinesi, matrioska, la stampa

di Escher

Specificare una sequenza n Enumerazione: 2, 4, 6, 8, ... n  Formula esplicita: f(n) = 2⋅n, n = 1, 2, 3, ... n  Formula ricorsiva:

¨  f(1) = 2 ¨  f(n) = f(n-1) + 2

f(2)=f(1)+2=2+2=4 f(3)=f(2)+2=4+2=6 f(4)=f(3)+2=6+2=8

3

Definizioni ricorsive n Una funzione matematica è definita ricorsivamente

quando nella sua definizione compare un riferimento a stessa

n  La ricorsione consiste nella possibilità di definire una funzione in termini di se stessa

È basata sul principio di induzione matematica: n  se una proprietà p vale per n=n0 (caso base); e n  si può provare che, assumendola valida per n, allora

vale per n+1, allora p vale per ogni n≥n0

Come fare … Operativamente, risolvere un problema, con un approccio ricorsivo comporta: n  identificare un “caso base” la cui soluzione sia nota

n  riuscire a esprimere la soluzione al caso generico n in termini dello stesso problema in uno o più casi più semplici (n-1, n-2, etc)

Esempio

n  f(0) =3 n  f(n+1) = 2⋅f(n) +3

Trovare f(1), f(2), f(3) e f(4)

Soluzione

n  f(1) = f(0+1) =2⋅f(0) +3 = 2⋅3 +3 =9 n  f(2) = f(1+1) =2⋅f(1) +3 = 2⋅9 +3 =21 n  f(3) = f(2+1) =2⋅f(2) +3 = 2⋅21+3 = 45 n  f(4) = f(3+1) =2⋅f(3) +3 = 2⋅45 +3 = 93

f(0) =3 f(n+1) = 2⋅f(n) +3

4

Fattoriale n! = n⋅(n-1)⋅(n-2) ⋅ ⋅ ⋅ 1 definizione di fattoriale fatt(0) = 1 fatt(n+1) = (n+1) ⋅ fatt(n) Esempio fatt(5) = 5⋅fatt(4)

= 5⋅(4⋅fatt(3)) = 5⋅4⋅(3⋅fatt(2)) = 5⋅4⋅3⋅(2⋅fatt(1)) = 5⋅4⋅3⋅ 2⋅ (1⋅fatt(0) ) = 5⋅4⋅3⋅ 2⋅1⋅1 = 120

Esercizio

Dare una definizione ricorsiva di

∑=

n

kka

0

naaa +++ !10

Soluzione

0

0

00 aa

k=∑

=

10

1

0

)( +=

+

=

+= ∑∑ n

n

kk

n

kk aaa

f(0) = a0 f(n+1) = f(n) + an+1

Fibonacci

Il problema di Fibonacci, o problema dei conigli, consiste nel determinare quante coppie di conigli ci saranno dopo n mesi, nelle seguenti ipotesi:

1.  al mese 1 c'è una coppia di conigli neonati, 2.  un coniglio diventa fertile dopo un mese dalla nascita, 3.  ogni coppia di conigli fertile genera ogni mese una nuova

coppia di conigli 4.  non c'è mortalità di conigli

5

Fibonacci

2 +

+

Coppie

1

1

5

3

2

Mese 1

Mese 2

Mese 3

Mese 4

Mese 5 3 + 2

8 Mese 6 5 + 3

Soluzione Sequenza 1, 1, 2, 3 ,5, 8, 13, 21, 34, 55, 89, 144,… Ogni nuovo numero rappresenta la somma dei due numeri che lo precedono Chiamando fib(n) la successione di Fibonacci, si assume convenzionalmente fib(0) = 0 La successione di Fibonacci, dunque, è: 0, 1, 1, 2, 3 ,5, 8, 13, 21, 34, 55, 89, 144,… Definizione ricorsiva: n  fib(0) = 0 n  fib(1) = 1 n  fib(n) = fib(n-1) + fib(n-2) per n = 2, 3, 4, 5, ...