Pareri su un esercizio sull'induzione...
Salve a tutti, vorrei chiedervi dei pareri sul seguente esercizio (il numero 1.02 del "Aritmetica superiore" di Davenport):
Definiamo i numeri di Fibonacci, $F_n$ con $F_1=F_2=1$ e $F_n=F_(n-1) + F_(n-2)$ per $n>2$ dimostrare per induzione o altrimenti che:
(a) $F_n < tau^n$ dove $tau$ è la sezione aurea $((1+sqrt(5)))/2$
(b)$F_n=(tau^n-sigma^n)/sqrt(5)$ dove $sigma =-1/tau=((1-sqrt(5)))/2$
Allora...
(a) Supposta vera $F_n < tau^n$ per i numeri naturali non superiori ad $n$ dobbiamo dimostrare $F_(n+1) < tau^(n+1)$.
Sappiamo per ipotesi che sono vere sia $F_(n-1) < tau^(n-1)$ che $F_n < tau^n$, quindi, poichè $F_n=F_(n-1) + F_(n-2)$ , sommando membro a membro otteniamo
$F_(n+1) < tau^n + tau^(n-1)$. Confrontando $tau^n + tau^(n-1)$ con $tau^(n+1)$ vediamo che sono uguali e quindi abbiamo dimostrato
che $F_n < tau^n rArr F_(n+1) < tau^(n+1)$. Per $n=3$ la diseguaglianza è banalmente vera.
(b)La dimostrazione è molto simile...
Supposta vera l'equazione da dimostrare per i numeri naturali che non superino $n$ dobbiamo dimostrare $F_(n+1)=(tau^(n+1)-sigma^(n+1))/sqrt(5)$
Con un ragionamento analogo al precedente sommiamo membro a membro le equazioni per $n-1$ e $n$ che sono vere per ipotesi induttiva,
otteniamo $F_(n+1)=(tau^n-sigma^n+tau^(n-1)-sigma^(n-1))/sqrt(5)$. Siccome $(tau^n-sigma^n+tau^(n-1)-sigma^(n-1))/sqrt(5)=(tau^(n+1)-sigma^(n+1))/sqrt(5)$ (l'ho risolta brevemente riferendomi a quella dell'esercizio (a) sostituendo $sigma$ con $-1/tau$) ed essendo l'equazione da dimostrare vera
per $n=3$, la dimostrazione dovrebbe essere conclusa.
Che ne pensate? C'é una dimostrazione più corta e elegante?
Definiamo i numeri di Fibonacci, $F_n$ con $F_1=F_2=1$ e $F_n=F_(n-1) + F_(n-2)$ per $n>2$ dimostrare per induzione o altrimenti che:
(a) $F_n < tau^n$ dove $tau$ è la sezione aurea $((1+sqrt(5)))/2$
(b)$F_n=(tau^n-sigma^n)/sqrt(5)$ dove $sigma =-1/tau=((1-sqrt(5)))/2$
Allora...
(a) Supposta vera $F_n < tau^n$ per i numeri naturali non superiori ad $n$ dobbiamo dimostrare $F_(n+1) < tau^(n+1)$.
Sappiamo per ipotesi che sono vere sia $F_(n-1) < tau^(n-1)$ che $F_n < tau^n$, quindi, poichè $F_n=F_(n-1) + F_(n-2)$ , sommando membro a membro otteniamo
$F_(n+1) < tau^n + tau^(n-1)$. Confrontando $tau^n + tau^(n-1)$ con $tau^(n+1)$ vediamo che sono uguali e quindi abbiamo dimostrato
che $F_n < tau^n rArr F_(n+1) < tau^(n+1)$. Per $n=3$ la diseguaglianza è banalmente vera.
(b)La dimostrazione è molto simile...
Supposta vera l'equazione da dimostrare per i numeri naturali che non superino $n$ dobbiamo dimostrare $F_(n+1)=(tau^(n+1)-sigma^(n+1))/sqrt(5)$
Con un ragionamento analogo al precedente sommiamo membro a membro le equazioni per $n-1$ e $n$ che sono vere per ipotesi induttiva,
otteniamo $F_(n+1)=(tau^n-sigma^n+tau^(n-1)-sigma^(n-1))/sqrt(5)$. Siccome $(tau^n-sigma^n+tau^(n-1)-sigma^(n-1))/sqrt(5)=(tau^(n+1)-sigma^(n+1))/sqrt(5)$ (l'ho risolta brevemente riferendomi a quella dell'esercizio (a) sostituendo $sigma$ con $-1/tau$) ed essendo l'equazione da dimostrare vera
per $n=3$, la dimostrazione dovrebbe essere conclusa.
Che ne pensate? C'é una dimostrazione più corta e elegante?
Risposte
La dimostrazione per induzione richiede 2 passaggi:
1. Dimostrazione diretta del caso base, in questo caso per $F_1$ e $F_2$.
2. Supporre che la proposizione sia vera per tutti i valori fino ad un certo $k$ e provare che è vera per $k+1$.
Hai dimenticato di fare il primo passaggio in entrambe le dimostrazioni. Senza di esso la tua dimostrazione è incompleta.
1. Dimostrazione diretta del caso base, in questo caso per $F_1$ e $F_2$.
2. Supporre che la proposizione sia vera per tutti i valori fino ad un certo $k$ e provare che è vera per $k+1$.
Hai dimenticato di fare il primo passaggio in entrambe le dimostrazioni. Senza di esso la tua dimostrazione è incompleta.
"apatriarca":
La dimostrazione per induzione richiede 2 passaggi:
1. Dimostrazione diretta del caso base, in questo caso per $F_1$ e $F_2$.
2. Supporre che la proposizione sia vera per tutti i valori fino ad un certo $k$ e provare che è vera per $k+1$.
Hai dimenticato di fare il primo passaggio in entrambe le dimostrazioni. Senza di esso la tua dimostrazione è incompleta.
Ahh, ho capito, avevo letto male il testo "Definiamo i numeri di Fibonacci, $F_n$ con $F_1=F_2=1 e F_n=F_(n-1)+F_(n-2)$ per $n>2$ dimostrare per induzione o altrimenti che. Pensavo che bisognasse dimostrare la diseguaglianza e l'equazione per $n>2$...che tonto!
(E infatti ho dimostrato il caso base per $n=3$, anzi più che dimostrato ho detto che era dimostrato, ma la dimostrazione è banale)Un piccolo chiarimento teorico, dobbiamo dimostrare $F_1$ e $F_2$ e non solo $F_1$ perchè senno si uscirebbe dai numeri naturali considerando $F_(n-1)$?
I numeri di Fibonacci sono definiti $\forall n \in NN^{+}$ (*), quindi (a) e (b) vanno provate $\forall n \in NN^{+}$.
____________________
$NN^{+}:=NN\\{0}$
____________________
$NN^{+}:=NN\\{0}$
"pippo93":
Un piccolo chiarimento teorico, dobbiamo dimostrare $F_1$ e $F_2$ e non solo $F_1$ perchè senno si uscirebbe dai numeri naturali considerando $F_(n-1)$?
Esatto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo