Induzione: Esercizi con Fattoriali
Salve a tutti volevo chiedere alcuni cosigli riguardo alla dimostrazione tramite induzione del seguente esercizio:
Posto prima di tutto un esempio di esercizio con fattoriale semplice con la soluzione:
1)Dimostrare tramite induzione (non quella forte) che $ AAn in N $, $ 2^n>= n $
a) passo base con $n = 0$ :
$ 2^0 >= 0 $ vero!
b) passo induttivo con $n=(n+1)$ :
ipotesi: $2^n>=n$
Tesi: $2^(n+1)>= n+1$
dimostrazione:
$2^(n+1)= 2^n*2 >= 2n >= n+1$
Evidenziando gli ultimi due membri della catena $2n >= n+1$ si nota che sono verificati solo per $n >=1$,per completare la dimostrazione dobbiamo quindi collegare il passo base con la verifica che funzioni anche con il valore 1 in modo da accertare che valga davvero con ogni valore,quindi:
$2^1 >= 1$
Inanziutto volevo chiedere come mai è stato necessario fare l'ultima parte,cioè verificare anche con $n=1$ quando la condizione prevede il $>=$ che comprende già l'uguale a 1 ??
Posto un secondo esercizio per capire come mai applicando l'ultima parte dell'esercizio precedente,la dimostrazione non mi riesce:
2)Dimostrare tramite induzione che $AAn >= 1, n! >= 2^(n-1)$
a) passo base con $n=1$ :
$1! >= 2^0 => 1 = 1$ vero!
b) passo induttivo con $n=(n+1)$ :
ipotesi: $n! >= 2^(n-1)$
tesi: $(n+1)! >= 2^n$
dimostrazione:
$(n+1)! = (n+1)*n!>=(n+1)*2^(n-1)>=(n+1)*2^n*1/2>=(n*2^n+2^n)/2>=2(n*2^n+2^n)>=2^n$
Secondo voi è giusto ques'ulimo passaggio a livello di calcoli?. Oltretutto,anche qui dopo bisogna dimostrare il caso di n = 1 ? Forse ci sono anche degli errori nel testo,per questo chiedo anche qui.
E' la prima volta che scrivo,spero di non avere commesso errori con il codice per le formule.Grazie
Posto prima di tutto un esempio di esercizio con fattoriale semplice con la soluzione:
1)Dimostrare tramite induzione (non quella forte) che $ AAn in N $, $ 2^n>= n $
a) passo base con $n = 0$ :
$ 2^0 >= 0 $ vero!
b) passo induttivo con $n=(n+1)$ :
ipotesi: $2^n>=n$
Tesi: $2^(n+1)>= n+1$
dimostrazione:
$2^(n+1)= 2^n*2 >= 2n >= n+1$
Evidenziando gli ultimi due membri della catena $2n >= n+1$ si nota che sono verificati solo per $n >=1$,per completare la dimostrazione dobbiamo quindi collegare il passo base con la verifica che funzioni anche con il valore 1 in modo da accertare che valga davvero con ogni valore,quindi:
$2^1 >= 1$
Inanziutto volevo chiedere come mai è stato necessario fare l'ultima parte,cioè verificare anche con $n=1$ quando la condizione prevede il $>=$ che comprende già l'uguale a 1 ??
Posto un secondo esercizio per capire come mai applicando l'ultima parte dell'esercizio precedente,la dimostrazione non mi riesce:
2)Dimostrare tramite induzione che $AAn >= 1, n! >= 2^(n-1)$
a) passo base con $n=1$ :
$1! >= 2^0 => 1 = 1$ vero!
b) passo induttivo con $n=(n+1)$ :
ipotesi: $n! >= 2^(n-1)$
tesi: $(n+1)! >= 2^n$
dimostrazione:
$(n+1)! = (n+1)*n!>=(n+1)*2^(n-1)>=(n+1)*2^n*1/2>=(n*2^n+2^n)/2>=2(n*2^n+2^n)>=2^n$
Secondo voi è giusto ques'ulimo passaggio a livello di calcoli?. Oltretutto,anche qui dopo bisogna dimostrare il caso di n = 1 ? Forse ci sono anche degli errori nel testo,per questo chiedo anche qui.
E' la prima volta che scrivo,spero di non avere commesso errori con il codice per le formule.Grazie
Risposte
non è affatto vero che $n2^n=2n^n$
devi lasciare scritto semplicemente $(n+1)/2 2^n $che è maggiore o uguale a $2^n$
devi lasciare scritto semplicemente $(n+1)/2 2^n $che è maggiore o uguale a $2^n$
Ho modificato chiedendo se sono giusti i calcoli dell'ultimo passagio e aggiungendo ..$>=n^(n)>=2^n$. ora leggo bene quello che hai scritto
"stormy":
non è affatto vero che $n2^n=2n^n$
devi lasciare scritto semplicemente $(n+1)/2 2^n $che è maggiore o uguale a $2^n$
Ma quindi se la sviluppo è errato o va bene lo stesso dire che $n^(n)>=2^n$?
fermati a $(n+1)/2 2^n geq 2^n$ perchè dopo hai commesso gravi errori algebrici 
eh appunto, me li puoi dire,mi interessano sopratutto quelli 
.Sarebbe che $n^n *1^n$ non fa $n^(2n)$ perchè la base differisce?
.Sarebbe che $n^n *1^n$ non fa $n^(2n)$ perchè la base differisce?
ad esempio,da dove spunta quell' $n^n$,poi anche quello che hai scritto nell'ultimo post,come tu stesso hai detto ,non è vero
ma poi ,ripeto,non si vede il motivo per il quale bisogna continuare se già si è dimostrata la tesi
ma poi ,ripeto,non si vede il motivo per il quale bisogna continuare se già si è dimostrata la tesi
"stormy":
ad esempio,da dove spunta quell' $n^n$,poi anche quello che hai scritto nell'ultimo post,come tu stesso hai detto ,non è vero
ma poi ,ripeto,non si vede il motivo per il quale bisogna continuare se già si è dimostrata la tesi
Raccolgo il 2 al numeratore.No ma infatti io chiedevo per capire fino a che punto dovevo fermarmi. Magari potevo fermarmi anche prima ossia a $(n+1)*2^(n-1)>= 2^n$
fino a quando sei arrivato a $(n+1)/2 2^n$ sei stato impeccabile e lì ti devi fermare ( ) perchè questa quantità è maggiore o uguale a $2^n$
quindi hai dimostrato quello che volevi
) perchè questa quantità è maggiore o uguale a $2^n$quindi hai dimostrato quello che volevi
Comunque grazie , sapresti dirmi se l'esercizio finisce cosi oppure devo fare altro?. Il primo es ha verificato il caso $n=1$ poiche era $AAn in N$ ? quindi nel secondo non dovrei fare altro,esatto?
, sapresti dirmi se l'esercizio finisce cosi oppure devo fare altro?. Il primo es ha verificato il caso $n=1$ poiche era $AAn in N$ ? quindi nel secondo non dovrei fare altro,esatto?
hai finito perchè hai dimostrato che la disuguaglianza è vera per $n=1$ e che l'essere vera per $n$ implica che è vera per $n+1$
,ho corretto alcuni errori algebrici riguardo $ n^n * 1^n$ che ovviamente fa $n^n$ e non $n^(2n)$ piu altri errori.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo