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, ...
