Esercizio con metodo di induzione
Buonasera, ho provato a fare questo esercizio ma rimango bloccato ad un certo punto e non so come andare avanti. L'esercizio è questo:
$2^n>=n+1$ con $n>=0$
Allora, intanto è vera perché $2^0>=0+1$ quindi $1>=1$
quindi poniamo poi $n=k+1$ e allora:
$2^(k+1)>=k+2=2^k*2>=k+2$ mi sono bloccato qui e non so come continuare.
$2^n>=n+1$ con $n>=0$
Allora, intanto è vera perché $2^0>=0+1$ quindi $1>=1$
quindi poniamo poi $n=k+1$ e allora:
$2^(k+1)>=k+2=2^k*2>=k+2$ mi sono bloccato qui e non so come continuare.
Risposte
"arnett":
Il consiglio "di metodo" che ti do è di non scrivere subito la tesi $2^{k+1}\ge k+2$, ma solo il membro sinistro e arrivare al membro destro per catene di uguaglianze/disuguaglianze: prova a scrivere $2^{k+1}=2*2^{k}>=...$ e usa dove ho messo i puntini l'ipotesi induttiva.
Ok, ma non continuo a capire come come andare avanti poi.
"arnett":
Hai guardato il link di gugo? È piuttosto utile. Comunque per ipotesi induttiva $2^k\gek+1$. Allora per banali regole algebriche $2*2^k\ge2(k+1)$.
Quindi alla fine hai $2^{k+1}=2*2^k\ge2(k+1)=2k+2\gek+2$ e hai concluso, se guardi il primo e l'ultimo membro di questa relazione hai la tesi.
Non capisco come fai ad ottenere $2*(k+1)$, non dovrebbe essere $(k+2)$ dato che devo sostituire a $k$ il $(k+1)$ ?
"arnett":
Confondi la tesi con le ipotesi.
Nel passaggio incriminato
$2*2^k\ge2(k+1)=$
hai per ipotesi che $ 2^k\gek+1 $ e vuoi ottenere come tesi che $2^{k+1}\ge k+2$.
Chiaramente siccome lo stai dimostrando devi usare l'ipotesi, non la tesi, nella dimostrazione.
Scusa ma non riesco ancora a capire da dove viene fuori questo $2(k+1)$
"tizyo96":
Scusa ma non riesco ancora a capire da dove viene fuori questo $2(k+1)$
Forse non ti è ancora chiaro come funziona l'induzione: una volta verificato il passo base, si suppone che valga la proposizione per il passo $n$-esimo e si cerca di dimostrare il passo $(n+1)$-esimo; quest'ultima condizione si chiama ipotesi induttiva, quindi tu devi dimostrare che valga il passo $(n+1)$-esimo sfruttando il fatto che l'$n$-esimo vale per ipotesi.
Perciò, se l'$n$-esimo per ipotesi vale, vale $2^n\geq n+1$; quindi moltiplicando ambo i membri per $2$ vale che $2*2^n\geq 2(n+1)$.
(Ho usato la lettera $n$ al posto della $k$, ma è uguale).
Scusa ma $2^(n+1)$ non è uguale a $2*2^n$ ? E perché va moltiplicato per 2?
Cerco di spiegarmi meglio: tu devi dimostrare che $2^{n+1}\geq n+2$.
Cosa si fa allora? Cerchiamo di ricondurci a ciò che sappiamo: ovvero sappiamo per ipotesi induttiva che $2^n \geq n+1$.
Quindi facciamo in modo di usare questa ipotesi, come facciamo?
Scriviamo $2^{n+1}=2*2^n$; ecco qua, è comparso un $2^n$ che sappiamo per ipotesi induttiva essere maggiore/uguale di $n+1$.
Perciò possiamo usare quest'ultima proprietà per scrivere che $2*2^n \geq 2(n+1)$, ma $2(n+1)=2n+2$.
Ricapitolando quindi, abbiamo la catena di uguaglianze/disuguaglianze $2^{n+1}=2*2^n\geq 2(n+1)=2n+2$.
Cosa dovevamo dimostrare noi? Che $2^{n+1} \geq n+2$, perciò usando la catena appena scritta sopra risulta
$$2^{n+1}=2\cdot2^n\geq 2(n+1)=\color{red} 2n+2 \geq n+2$$
Dove la disuguaglianza scritta in rosso non è ancora vera, ma è ciò che dobbiamo controllare che sia vero affinché la dimostrazione sia conclusa (ricorda, dovevamo dimostrare che $2^{n+1} \geq n+2$).
Ma quella disuguaglianza in rosso è molto semplice da verificare, in quanto deve risultare $2n+2\geq n+2$, che porta a dover verificare che $n\geq0$; ciò è valido perché $n\in\mathbb{N}$.
Cosa si fa allora? Cerchiamo di ricondurci a ciò che sappiamo: ovvero sappiamo per ipotesi induttiva che $2^n \geq n+1$.
Quindi facciamo in modo di usare questa ipotesi, come facciamo?
Scriviamo $2^{n+1}=2*2^n$; ecco qua, è comparso un $2^n$ che sappiamo per ipotesi induttiva essere maggiore/uguale di $n+1$.
Perciò possiamo usare quest'ultima proprietà per scrivere che $2*2^n \geq 2(n+1)$, ma $2(n+1)=2n+2$.
Ricapitolando quindi, abbiamo la catena di uguaglianze/disuguaglianze $2^{n+1}=2*2^n\geq 2(n+1)=2n+2$.
Cosa dovevamo dimostrare noi? Che $2^{n+1} \geq n+2$, perciò usando la catena appena scritta sopra risulta
$$2^{n+1}=2\cdot2^n\geq 2(n+1)=\color{red} 2n+2 \geq n+2$$
Dove la disuguaglianza scritta in rosso non è ancora vera, ma è ciò che dobbiamo controllare che sia vero affinché la dimostrazione sia conclusa (ricorda, dovevamo dimostrare che $2^{n+1} \geq n+2$).
Ma quella disuguaglianza in rosso è molto semplice da verificare, in quanto deve risultare $2n+2\geq n+2$, che porta a dover verificare che $n\geq0$; ciò è valido perché $n\in\mathbb{N}$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo