Disuguaglianza e principio di induzione
Buon pomeriggio,mi sto scervellando su un esercizio molto semplice ma che non riesco proprio a capire.
In pratica riesco a risolvere esercizi sul principio di induzione che riguardano uguaglianze,ma non riesco a capire
il ragionamento nel caso di disuguaglianze.Mi basta anche un solo esempio.L'esercizio è il seguente:
Dimostrare per ogni n maggiore di 4 che $ 2^n > n^2 $
Innanzittuo verifico la Base d'induzione: $2^5 >5^2 -> 32 > 25 $ che è verificata.
Procedo con il Passo induttivo: $2^(n+1) > (n+1)^2 $
La mia idea è questa $ 2*2^n > n^2 +2*n +1 $ ma non so come andare avanti
In pratica riesco a risolvere esercizi sul principio di induzione che riguardano uguaglianze,ma non riesco a capire
il ragionamento nel caso di disuguaglianze.Mi basta anche un solo esempio.L'esercizio è il seguente:
Dimostrare per ogni n maggiore di 4 che $ 2^n > n^2 $
Innanzittuo verifico la Base d'induzione: $2^5 >5^2 -> 32 > 25 $ che è verificata.
Procedo con il Passo induttivo: $2^(n+1) > (n+1)^2 $
La mia idea è questa $ 2*2^n > n^2 +2*n +1 $ ma non so come andare avanti
Risposte
Non so se tu conosci il teorema "$n^2 > 2n+1 , forall n geq 3$", ma puoi dimostrarlo sempre per induzione.
Riprendo da dove hai lasciato:
$(n+1)^2=n^2+ 2n+1<2n^2<2*2^n=2^(n+1)$.
Riprendo da dove hai lasciato:
$(n+1)^2=n^2+ 2n+1<2n^2<2*2^n=2^(n+1)$.
No,non lo conosco ne il professore ne ha mai parlato 
Comunque scusami,non riesco proprio a capire quel $ 2n^2 $,hai fatto una sostituzione,cosa?
Comunque scusami,non riesco proprio a capire quel $ 2n^2 $,hai fatto una sostituzione,cosa?
Adesso che rileggo meglio quello che hai scritto prima: "$mathcal P(n) => mathcal P(n+1)$" è il passaggio induttivo, o in parole spicce prendi per vero la premessa e trai la conseguenza.
Scusami, cosa non hai capito? Come lo ottengo? Ho usato il teorema che ho introdotto.
Scusami, cosa non hai capito? Come lo ottengo? Ho usato il teorema che ho introdotto.
Si scusami,non riesco a capire come applichi il teorema
"python34":
Si scusami,non riesco a capire come applichi il teorema
A questo punto, scusami, ti faccio una domanda: che scuola fai?
Cosa centra?
Non volevo insinuare nulla! Era solo una domanda perché quello che è ho fatto è un passaggio elementare...
Scusami,sono io che non ci arrivo...
Il passo induttivo consiste nell'assumere come ipotesi (detta ipotesi induttiva) che la proprietà da verificare valga per un generico \( n \in \mathbb{N} \) (nella fattispecie con l'ipotesi aggiuntiva che sia \( n > 4 \)) e mostrare che allora vale per \( n + 1 \) (detta tesi induttiva).
In questo caso l'ipotesi induttiva è che sia \( 2^{n} > n^{2} \) e la tesi induttiva è che sia \( 2^{ n + 1 } > ( n + 1 )^{2} \). Partendo da \( 2^{n} > n^{2} \), si moltiplica a sinistra ed a destra per \( 2 \), ottenendo \( 2 \cdot 2^{2} > 2n^{2} \). E ci fermiamo un attimo.
Come suggerito da Indrjo Dedej, vale anche (per ogni \( n \geq 3 \)) che \( n^{2} > 2n + 1 \): se sommiamo a sinistra ed a destra la quantità \( n^{2} \) otteniamo \( n^{2} + n^{2} > n^{2} + 2n + 1 \) ed inoltre \( n^{2} + n^{2} = 2n^{2} \), quindi otteniamo \( 2n^{2} > n^{2} + 2n + 1 \); ma non è finita perché essendo \( n^{2} + 2n + 1 = ( n + 1 )^{2} \), si ottiene \( 2n^{2} > ( n + 1 )^{2} \).
Riprendiamo adesso \( 2 \cdot 2^{2} > 2n^{2} \): abbiamo appena detto che \( 2n^{2} > ( n + 1 )^{2} \), quindi per transitività \( 2 \cdot 2^{n} > 2n^{2} > ( n + 1 )^{2} \), cioè \( 2 \cdot 2^{n} > ( n + 1 )^{2} \). E poiché \( 2 \cdot 2^{n} = 2^{ n + 1 } \), si conclude \( 2^{ n + 1 } > ( n + 1 )^{2} \), che è la tesi induttiva.
In questo caso l'ipotesi induttiva è che sia \( 2^{n} > n^{2} \) e la tesi induttiva è che sia \( 2^{ n + 1 } > ( n + 1 )^{2} \). Partendo da \( 2^{n} > n^{2} \), si moltiplica a sinistra ed a destra per \( 2 \), ottenendo \( 2 \cdot 2^{2} > 2n^{2} \). E ci fermiamo un attimo.
Come suggerito da Indrjo Dedej, vale anche (per ogni \( n \geq 3 \)) che \( n^{2} > 2n + 1 \): se sommiamo a sinistra ed a destra la quantità \( n^{2} \) otteniamo \( n^{2} + n^{2} > n^{2} + 2n + 1 \) ed inoltre \( n^{2} + n^{2} = 2n^{2} \), quindi otteniamo \( 2n^{2} > n^{2} + 2n + 1 \); ma non è finita perché essendo \( n^{2} + 2n + 1 = ( n + 1 )^{2} \), si ottiene \( 2n^{2} > ( n + 1 )^{2} \).
Riprendiamo adesso \( 2 \cdot 2^{2} > 2n^{2} \): abbiamo appena detto che \( 2n^{2} > ( n + 1 )^{2} \), quindi per transitività \( 2 \cdot 2^{n} > 2n^{2} > ( n + 1 )^{2} \), cioè \( 2 \cdot 2^{n} > ( n + 1 )^{2} \). E poiché \( 2 \cdot 2^{n} = 2^{ n + 1 } \), si conclude \( 2^{ n + 1 } > ( n + 1 )^{2} \), che è la tesi induttiva.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo