Fibonacci e induzione

[python1134]

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

[kobeilprofeta]

PensO vada in informatica.

[apatriarca]

Non mi è chiaro il senso della dimostrazione.. La funzione è in pratica identica alla definizione della successione di Fibonacci! Ma la dimostrazione mi sembra comunque corretta per quanto ovvia..