Principio di induzione applicato a una disuguaglianza
Salve, sto riscontrando dei problemi su un esercizio.
Devo dimostrare per induzione che $n*(2^n)<3^n$ per ogni n maggiore o uguale a 0.
Ho verificato che la disuguaglianza è vera per $n=1$ , infatti $2<3$ .
Lo scopo è quello di dimostrare che $(n+1)*2^(n+1)<3^(n+1)$.
Attraverso l'ipotesi sono giunto alla conclusione che $(3/2)*n*2^(n+1)<3^(n+1)$.
Per arrivare allo scopo devo quindi dimostrare che $(3/2)*n>n+1$.
Facendo così mi risulta che la disuguaglianza è vera per $n>2$ , mentre l'ipotesi è vera per ogni n maggiore o uguale a 0.
Mi aiutate a capire dove sbaglio?
Devo dimostrare per induzione che $n*(2^n)<3^n$ per ogni n maggiore o uguale a 0.
Ho verificato che la disuguaglianza è vera per $n=1$ , infatti $2<3$ .
Lo scopo è quello di dimostrare che $(n+1)*2^(n+1)<3^(n+1)$.
Attraverso l'ipotesi sono giunto alla conclusione che $(3/2)*n*2^(n+1)<3^(n+1)$.
Per arrivare allo scopo devo quindi dimostrare che $(3/2)*n>n+1$.
Facendo così mi risulta che la disuguaglianza è vera per $n>2$ , mentre l'ipotesi è vera per ogni n maggiore o uguale a 0.
Mi aiutate a capire dove sbaglio?
Risposte
In realtà sarebbe interessante capire come dall’ipotesi induttiva sei arrivato a $ (3/2)*n*2^(n+1)<3^(n+1) $…
Per ipotesi sappiamo che $n*2^n<3^n$.
Possiamo scrivere che $n*(2/2)*2^n<(3/3)3^n$ perché $3/3$ e $2/2$ sono uguali a 1.
Per le proprietà delle potenze possiamo scrivere la disequazione come $(n/2)*2^(n+1)<(1/3)*3^(n+1)$.
Portando $1/3$ al primo membro la disequazione diventa $3/2*n*2^(n+1)<3^(n+1)$.
Possiamo scrivere che $n*(2/2)*2^n<(3/3)3^n$ perché $3/3$ e $2/2$ sono uguali a 1.
Per le proprietà delle potenze possiamo scrivere la disequazione come $(n/2)*2^(n+1)<(1/3)*3^(n+1)$.
Portando $1/3$ al primo membro la disequazione diventa $3/2*n*2^(n+1)<3^(n+1)$.
Sì, va bene… Ma come ti è venuto in mente di usarla così l’ipotesi induttiva? 
A me non viene mai di ragionare in maniera diretta, perché di solito i conti vengono meno immediati.
Dato che $2^n < 3^n/n$, hai $(n+1) 2^(n+1) < (n +1)/n *2*3^n = (2(n+1))/(3n)* 3^(n+1)$ con l’ultimo membro $<3^(n+1)$ non appena risulti $(2(n+1))/(3n) <1$ cioè per $n>=3$.
Ne viene che il passo induttivo è vero per $n>=3$ e, quindi, basta verificare il caso base per $n=0,1,2,3$ per concludere.
A me non viene mai di ragionare in maniera diretta, perché di solito i conti vengono meno immediati.
Dato che $2^n < 3^n/n$, hai $(n+1) 2^(n+1) < (n +1)/n *2*3^n = (2(n+1))/(3n)* 3^(n+1)$ con l’ultimo membro $<3^(n+1)$ non appena risulti $(2(n+1))/(3n) <1$ cioè per $n>=3$.
Ne viene che il passo induttivo è vero per $n>=3$ e, quindi, basta verificare il caso base per $n=0,1,2,3$ per concludere.
Perdonami, ma perché devo verificare il caso base per n=0,1,2?
Per ipotesi io so già che $n*2^n<3^n$ è vera per ogni n maggiore o uguale a 0.
Per ipotesi io so già che $n*2^n<3^n$ è vera per ogni n maggiore o uguale a 0.
Come funziona il PIM?
A cosa serve il caso base? Ed il passo induttivo?
A cosa serve il caso base? Ed il passo induttivo?
Ciao PinkFloyd55,
Benvenuto sul forum!
No, attenzione, questo è ciò che devi dimostrare. Hai già verificato che la disuguaglianza è vera per $n = 1 $ e non è certo un problema verificare che essa vale anche per $n = 0 $. Ciò detto, supponendo che sia vero che $n \cdot 2^n < 3^n$ (ipotesi induttiva) si deve dimostrare (tesi) che si ha $(n + 1) \cdot 2^{n + 1} < 3^{n + 1} $
Qui ti sei complicato parecchio la vita, perché semplicemente si ha:
$(n + 1) \cdot 2^{n + 1} = 2n \cdot 2^n + 2^{n + 1} \stackrel [Hp]{<} 2 \cdot 3^n + 2^{n + 1} \stackrel [n \ge 2]{<} 2 \cdot 3^n + 3^n = 3^n(2 + 1) = 3^{n + 1} $
Benvenuto sul forum!
"PinkFloyd55":
Per ipotesi io so già che $n \cdot 2^n < 3^n$ è vera per ogni n maggiore o uguale a 0.
No, attenzione, questo è ciò che devi dimostrare. Hai già verificato che la disuguaglianza è vera per $n = 1 $ e non è certo un problema verificare che essa vale anche per $n = 0 $. Ciò detto, supponendo che sia vero che $n \cdot 2^n < 3^n$ (ipotesi induttiva) si deve dimostrare (tesi) che si ha $(n + 1) \cdot 2^{n + 1} < 3^{n + 1} $
Qui ti sei complicato parecchio la vita, perché semplicemente si ha:
$(n + 1) \cdot 2^{n + 1} = 2n \cdot 2^n + 2^{n + 1} \stackrel [Hp]{<} 2 \cdot 3^n + 2^{n + 1} \stackrel [n \ge 2]{<} 2 \cdot 3^n + 3^n = 3^n(2 + 1) = 3^{n + 1} $
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo