Ciao a tutti, di recente mi sono trovato di fronte al seguente esercizio:
Dimostrare per induzione su un opportuno parametro che, per ogni n >=
e' vero il predicato P(n) = "exTre(2^n) == n",
dove il metodo ricorsivo exTre e' definito da:
static int exTre(int n){
if (n > 1)
return 1 + exTre(n/2); // la divisione e' intera
else
return 0;
}
Io ho provato a risolverlo come segue e, dato che, penso sia quasi sicuramente sbagliato chiedo gentilmente a qualcuno di farmi notare gli errori:
Caso base: P(0)==exTre(2^0)==n''
// ==1+(0/2)==1==n''
Ipotesi induttiva: P(n+1)==exTre(2^(n+1))==n''
Dimostrazione: P(n+1)==1+(n+1)/2==1+(n/2)
// ==((n+2)/2)+(1/2)==(n+2)/2==P(n)
Mille grazie in anticipo per la risposta,
saluti.