Salve ragazzi, sto svolgendo un esercizio che mi chiede di calcolare la correttezza di una funzione che calcola
il numero di fibonacci utilizzando l'induzione.
Definizione di fibonacci
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2), n>=2
Funzione ricorsiva
procedure Fibonacci(n)
if(n=0) return 0;
else if (n=1) return 1;
else return Fibonacci(n-1) + Fibonacci(n-2);
Io procedo in questo modo,per induzione forte.
PASSO BASE
Se n=0 la funzione restituisce il valore corretto poichè f(0) = 0 = Fibonacci(0)
Se n=1 la funzione restituisce il valore corretto poichè f(1) = 1 = Fibonacci(1)
se n=2 la funzione restituisce Fibonacci(1)+Fibonacci(0)
se n=3 la funzione restituisce Fibonacci(2) + Fibonacci(1)
se n=4 la funzione restituisce Fibonacci(3) + Fibonacci(2)
IPOTESI INDUTTIVA
2 <= j <= k, k>=4
Affermo che la funzione calcola correttamente Fibonacci(j)
cioè restituisce f(j-1)+f(j-2)
PASSO INDUTTIVO
Voglio dimostrare che Fibonacci(k+1) restituisce f(k)+f(k-1).
Procedo dicendo che Fibonacci(k+1) restituisce Fibonacci(k)+Fibonacci(k-1),due chiamate ricorsive
Dato che per ipotesi Fibonacci(k) e Fibonacci(k-1) è vera, ho dimostrato la correttezza della funzione.
E' corretto il mio modo di procedere? Ossia penso che l'ipotesi induttiva sia sbagliata ma non ho dove poterne avere conferma
Grazie mille