Esercizio pricipio di induzione
Salve a tutti, negli esercizi in preparazione alla prova intermedia di Matematica discreta c'è un esercizio che chiede di dimostrare per induzione per quali valori di $n in NN $ si ha che $n^3<=2^n$.
Ora il valore cercato è 10 e quindi prendo $P(10)$ vera.
L'ipotesi induttiva$P(n)$ è $n^3<=2^n$ e la tesi $P(n+1)$ è $(n+1)^3<=2^(n+1)$.
Io procedo in questo modo:
$n^3+3n^2+3n+1<=2^2*2=2^2+2^2$
ora siccome $n^3<=2^n$ è la mia ipotesi induttiva noto che deve essere verificata questa disequazione $3n^2+3n+1<=2^2$ per far si che $(n+1)^3<=2^(n+1)$ sia vera.
A questo punto però basta che $3n^2+3n+1<=n^3$ poichè $n^3<=2^n$
Dimostro questa disequazione per induzione e vedo che per $n=4$ è verificata quindi $P(4)$ vera.
la mia tesi è $P(n+1)$= $3(n+1)^2+3(n+1)+1<=(n+1)^3$ e svolgendo i calcoli trovo che $n^3>=6n+6$.
Posso asserire che questo è vero senza doverlo dimostrare così da concludere la mia dimostrazione???
Il procedimento è quello corretto o c'è una strada più veloce?
Ora il valore cercato è 10 e quindi prendo $P(10)$ vera.
L'ipotesi induttiva$P(n)$ è $n^3<=2^n$ e la tesi $P(n+1)$ è $(n+1)^3<=2^(n+1)$.
Io procedo in questo modo:
$n^3+3n^2+3n+1<=2^2*2=2^2+2^2$
ora siccome $n^3<=2^n$ è la mia ipotesi induttiva noto che deve essere verificata questa disequazione $3n^2+3n+1<=2^2$ per far si che $(n+1)^3<=2^(n+1)$ sia vera.
A questo punto però basta che $3n^2+3n+1<=n^3$ poichè $n^3<=2^n$
Dimostro questa disequazione per induzione e vedo che per $n=4$ è verificata quindi $P(4)$ vera.
la mia tesi è $P(n+1)$= $3(n+1)^2+3(n+1)+1<=(n+1)^3$ e svolgendo i calcoli trovo che $n^3>=6n+6$.
Posso asserire che questo è vero senza doverlo dimostrare così da concludere la mia dimostrazione???
Il procedimento è quello corretto o c'è una strada più veloce?
Risposte
In toeria dovresti dimostrare anche l'ultima disuguaglianza. Non puoi dire che una disuguaglianza è vera se non la dimostri rigorosamente. (this is matematica)
Suggerisco una scappatoia che permette di fare molti meno conti:
La base ($P(10)$) è vera.
Passo induttivo: $AA n>=10$,
Ipotesi: $P(n): n^3<=2^n$
Tesi: $P(n+1): (n+1)^3<=2^(n+1)$
Dim: $(n+1)^3=n^3+3n^2+3n+1<=2^n+3n^2+3n+1$ (fin qui ci sei arrivato anche tu)
Ora, poichè $n>=10$, posso fare 3 affermazioni:
1)$1/3*n^3>=1/3*10n^2=(10/3)*n^2>=3n^2 => 3n^2<=n^3/3
2)$1/3*n^3>=1/3*100n=(100/3)*n>=3n => 3n<=n^3/3
3)$1/3*n^3>=1000/3>=1 =>1<=n^3/3$
pertanto, continuando la catena di disuguaglianze, $2^n+3n^2+3n+1<=2^n+n^3/3+n^3/3+n^3/3=2^n+n^3<=2^n+2^n=2^(n+1)$
Suggerisco una scappatoia che permette di fare molti meno conti:
La base ($P(10)$) è vera.
Passo induttivo: $AA n>=10$,
Ipotesi: $P(n): n^3<=2^n$
Tesi: $P(n+1): (n+1)^3<=2^(n+1)$
Dim: $(n+1)^3=n^3+3n^2+3n+1<=2^n+3n^2+3n+1$ (fin qui ci sei arrivato anche tu)
Ora, poichè $n>=10$, posso fare 3 affermazioni:
1)$1/3*n^3>=1/3*10n^2=(10/3)*n^2>=3n^2 => 3n^2<=n^3/3
2)$1/3*n^3>=1/3*100n=(100/3)*n>=3n => 3n<=n^3/3
3)$1/3*n^3>=1000/3>=1 =>1<=n^3/3$
pertanto, continuando la catena di disuguaglianze, $2^n+3n^2+3n+1<=2^n+n^3/3+n^3/3+n^3/3=2^n+n^3<=2^n+2^n=2^(n+1)$