DIMOSTRAZIONE per induzione fattoriale
Ciao a tutti,
volevo sapere se questa dimostrazione è corretta; l'ho risolta in due modalità diverse.
Dimostrare per induzione che $ n! ≥ 2^(n-1) $ per ogni $ n ≥ 1 $.
Suppongo che $ n! ≥ 2^(n-1) $ e dimostro che $ (n+1)! ≥ 2^((n+1)-1) $
Metodo 1
$ (n+1) n! ≥ 2^((n-1)+1) $ --> $ (n+1) (2^(n-1)) ≥ (2^(n-1)) 2$
Basta dimostrare che $ n+1 ≥ 2 $ che è vera per ogni $ n ≥ 1 $.
Metodo 2
$ (n+1) n! ≥ 2^n $ , che, sostituendo n = 1, è vera per ogni $ n ≥ 1 $.
Quale dei due metodi è quello "più corretto"?
Grazie!
volevo sapere se questa dimostrazione è corretta; l'ho risolta in due modalità diverse.
Dimostrare per induzione che $ n! ≥ 2^(n-1) $ per ogni $ n ≥ 1 $.
Suppongo che $ n! ≥ 2^(n-1) $ e dimostro che $ (n+1)! ≥ 2^((n+1)-1) $
Metodo 1
$ (n+1) n! ≥ 2^((n-1)+1) $ --> $ (n+1) (2^(n-1)) ≥ (2^(n-1)) 2$
Basta dimostrare che $ n+1 ≥ 2 $ che è vera per ogni $ n ≥ 1 $.
Metodo 2
$ (n+1) n! ≥ 2^n $ , che, sostituendo n = 1, è vera per ogni $ n ≥ 1 $.
Quale dei due metodi è quello "più corretto"?
Grazie!
Risposte
"abaco90":
$ (n+1) n! ≥ 2^n $ , che, sostituendo n = 1, è vera per ogni $ n ≥ 1 $.
Prova rileggere quello che hai scritto: $n$ è quantificata universalmente!
Per quanto riguarda il primo metodo, io farei
$(n+1)! =n!(n+1)>=2*2^(n-1)=2^n$.
"Indrjo Dedej":
[quote="abaco90"]
$ (n+1) n! ≥ 2^n $ , che, sostituendo n = 1, è vera per ogni $ n ≥ 1 $.
Prova rileggere quello che hai scritto: $n$ è quantificata universalmente!
Per quanto riguarda il primo metodo, io farei
$(n+1)! =n!(n+1)>=2*2^(n-1)=2^n$.[/quote]
Ciao, ho riletto ma non capisco cosa intendi dire.
Per quanto riguarda il 1 metodo si può considerare corretto?
Provo a spiegarmi in altri termini: per $n=1$ ho 2=2 che è vero. E qui ci siamo.
Tu hai però affermato di punto in bianco "per ogni $n>=1$" tu avresti dimostrato, preso un caso solo, infiniti altri casi.
Con espressioni del tipo "$forall n>=1, ...$" tu affermi che una certa proprietà vale per tutti i casi n=1, n=2, ..., mentre con "n=1" tu prendi un solo caso. È vero che se "per ogni $n>=1$, ..." allora n=1, ma non il viceversa!
Per quanto riguarda il metodo 1, tu hai supposto vero il teorema per n+1 e poi hai proseguito dicendo che bisogna dimostrare che $n+1>=2$.
Secondo me non hai ancora ben compreso il principio di induzione (chiunque ha avuto dei problemi nel capirlo, non ti preoccupare). Si prova la base dell'induzione. Il passo induttivo consiste nel dire "$P(n)=>P(n+1)$", ovvero prendo per ipotesi $P(n)$ e con questa dimostro $P(n+1)$ !
Tu hai però affermato di punto in bianco "per ogni $n>=1$" tu avresti dimostrato, preso un caso solo, infiniti altri casi.
Con espressioni del tipo "$forall n>=1, ...$" tu affermi che una certa proprietà vale per tutti i casi n=1, n=2, ..., mentre con "n=1" tu prendi un solo caso. È vero che se "per ogni $n>=1$, ..." allora n=1, ma non il viceversa!
Per quanto riguarda il metodo 1, tu hai supposto vero il teorema per n+1 e poi hai proseguito dicendo che bisogna dimostrare che $n+1>=2$.
Secondo me non hai ancora ben compreso il principio di induzione (chiunque ha avuto dei problemi nel capirlo, non ti preoccupare). Si prova la base dell'induzione. Il passo induttivo consiste nel dire "$P(n)=>P(n+1)$", ovvero prendo per ipotesi $P(n)$ e con questa dimostro $P(n+1)$ !
Ho visto anche un altro tuo post su una dimostrazione per induzione. E anche lì tu prendi per vero $P(n+1)$...
Ma nel primo metodo non sto dimostrando che $P(n+1) $ è vera? Infatti nell'ultimo passaggio arrivo a dire $ n+1≥2 $ che è vera per ogni n≥1.
Forse avrei dovuto affermare che se $ (n+1)n!≥2(n−1)+1 -> (n+1)(2n−1)≥(2n−1)2 $ è vera allora dimostro quest'ultima, quindi
$ n+1≥2 $ che è vera per ogni $n≥1.$
$ n+1≥2 $ che è vera per ogni $n≥1.$
Si vuole provare per induzione che \( n! \geq 2^{n-1} \) per ogni \( n \geq 1 \).
Innanzitutto, volendo essere rigorosi, manca il passo base, i.e. manca il far vedere che quella disuguaglianza è valida per \( n = 1 \).
Per quanto riguarda invece il passo induttivo, questo consiste, nella fattispecie, nell'assumere (ipotesi induttiva) che sia vera la disuguaglianza \( n! \geq 2^{n-1} \) e mostrare (tesi induttiva) che è vera la disuguaglianza \( ( n + 1 ) ! \geq 2^{ n } \).
Tu scrivi:
Io penso di avere anche capito quale sia/fosse la tua idea, correggimi pure se ho sbagliato ad intendere: la disuguaglianza che si vuole provare è \( ( n + 1 ) ! \geq 2^{ n } \); poiché \( ( n + 1 ) ! = n ! \cdot ( n + 1 ) \) e \( 2^{ n } = 2^{ n - 1 + 1 } \), allora la disuguaglianza da provare equivale (per una semplice riscrittura) a \( n ! \cdot ( n + 1 ) \geq 2^{ ( n - 1 ) + 1 } \) e quest'ultima disuguaglianza dovrebbe essere equivalente alla disuguaglianza \( ( n + 1 ) ( 2^{ n - 1 } ) \geq ( 2^{ n - 1} ) \cdot 2 \), la cui validità dipende (ovviamente) dal fatto che sia vero che \( n + 1 \geq 2 \) per ogni \( n \geq 1 \), sicché, andando a ritroso, provare la disuguaglianza \( ( n + 1 ) ! \geq 2^{ n } \) equivale a provare che sia \( n + 1 \geq 2 \), per ogni \( n \geq 1 \).
Come linea di ragionamento in sé e per sé ci può anche stare: mi rendo conto che quello che voglio provare equivale ad un altro fatto che è più semplice da provare, ed allora provo questo secondo fatto e concludo che anche il primo fatto è vero. Tuttavia:
• innanzitutto c'è un errore tecnico/formale: non puoi andartene per equivalenze e servirti di implicazioni in un solo verso, i.e. non puoi (nella fattispecie) passare da una disuguaglianza ad un'altra, che si suppone si equivalgano, per dimostrare la più semplice di queste disuguaglianze e poi fare la strada a ritroso per concludere che valga anche la disuguaglianza iniziale, collegando queste disuguaglianze con dei condizionali, i.e. con \( \rightarrow \), ma devi collegare queste disuguaglianze con dei bicondizionali, i.e. con \( \leftrightarrow \), sempre assicurandoti che la doppia implicazione valga;
• scritto ciò che hai scritto nel modo in cui lo hai scritto, non si capisce perché debbano valere queste equivalenze e non lo si capisce nemmeno nel tuo ultimo intervento o per lo meno non riesco a capirlo io, anche perché nel tuo ultimo intervento hai fatto scomparire le moltiplicazioni.
Innanzitutto, volendo essere rigorosi, manca il passo base, i.e. manca il far vedere che quella disuguaglianza è valida per \( n = 1 \).
Per quanto riguarda invece il passo induttivo, questo consiste, nella fattispecie, nell'assumere (ipotesi induttiva) che sia vera la disuguaglianza \( n! \geq 2^{n-1} \) e mostrare (tesi induttiva) che è vera la disuguaglianza \( ( n + 1 ) ! \geq 2^{ n } \).
Tu scrivi:
"abaco90":
Metodo 1
$ (n+1) n! ≥ 2^((n-1)+1) $ --> $ (n+1) (2^(n-1)) ≥ (2^(n-1)) 2$
Basta dimostrare che $ n+1 ≥ 2 $ che è vera per ogni $ n ≥ 1 $.
Io penso di avere anche capito quale sia/fosse la tua idea, correggimi pure se ho sbagliato ad intendere: la disuguaglianza che si vuole provare è \( ( n + 1 ) ! \geq 2^{ n } \); poiché \( ( n + 1 ) ! = n ! \cdot ( n + 1 ) \) e \( 2^{ n } = 2^{ n - 1 + 1 } \), allora la disuguaglianza da provare equivale (per una semplice riscrittura) a \( n ! \cdot ( n + 1 ) \geq 2^{ ( n - 1 ) + 1 } \) e quest'ultima disuguaglianza dovrebbe essere equivalente alla disuguaglianza \( ( n + 1 ) ( 2^{ n - 1 } ) \geq ( 2^{ n - 1} ) \cdot 2 \), la cui validità dipende (ovviamente) dal fatto che sia vero che \( n + 1 \geq 2 \) per ogni \( n \geq 1 \), sicché, andando a ritroso, provare la disuguaglianza \( ( n + 1 ) ! \geq 2^{ n } \) equivale a provare che sia \( n + 1 \geq 2 \), per ogni \( n \geq 1 \).
Come linea di ragionamento in sé e per sé ci può anche stare: mi rendo conto che quello che voglio provare equivale ad un altro fatto che è più semplice da provare, ed allora provo questo secondo fatto e concludo che anche il primo fatto è vero. Tuttavia:
• innanzitutto c'è un errore tecnico/formale: non puoi andartene per equivalenze e servirti di implicazioni in un solo verso, i.e. non puoi (nella fattispecie) passare da una disuguaglianza ad un'altra, che si suppone si equivalgano, per dimostrare la più semplice di queste disuguaglianze e poi fare la strada a ritroso per concludere che valga anche la disuguaglianza iniziale, collegando queste disuguaglianze con dei condizionali, i.e. con \( \rightarrow \), ma devi collegare queste disuguaglianze con dei bicondizionali, i.e. con \( \leftrightarrow \), sempre assicurandoti che la doppia implicazione valga;
• scritto ciò che hai scritto nel modo in cui lo hai scritto, non si capisce perché debbano valere queste equivalenze e non lo si capisce nemmeno nel tuo ultimo intervento o per lo meno non riesco a capirlo io, anche perché nel tuo ultimo intervento hai fatto scomparire le moltiplicazioni.
Ciao, grazie della risposta!
Si in effetti ho dimenticato il caso base, l'ho scritta un pò velocemente. Cmq hai capito perfettamente il mio ragionamento!
Provo a riscriverla come hai detto tu.
Caso base $n = 1$: $ 1! ≥ 2^0 ↔ 1 ≥ 1 $ quindi va bene.
Supponiamo per ipotesi d'induzione che $ n!≥2^(n−1) $ sia vera e dimostriamo che sia vera anche $ (n+1)!≥2^((n+1)-1) $.
Abbiamo che $ (n+1)! = (n+1)n! $ e $ 2^((n+1)-1) = (2^(n-1))2 $, quindi $ (n+1)n! ≥ 2^(n-1)2 $.
$ (n+1) (2^(n-1)) ≥ (2^(n-1))2 $ (Ipotesi induttiva).
Supponendo che $ (n+1) (2^(n-1)) ≥ (2^(n-1))2 $ sia vera, dal momento che ho entrambi i membri moltiplicati per $ (2^(n-1)) $, allora basta dimostrare che $ (n+1) ≥ 2 ↔ n ≥ 1 $ che vale per ogni $ n ≥ 1 $.
Può andare?
Si in effetti ho dimenticato il caso base, l'ho scritta un pò velocemente. Cmq hai capito perfettamente il mio ragionamento!
Provo a riscriverla come hai detto tu.
Caso base $n = 1$: $ 1! ≥ 2^0 ↔ 1 ≥ 1 $ quindi va bene.
Supponiamo per ipotesi d'induzione che $ n!≥2^(n−1) $ sia vera e dimostriamo che sia vera anche $ (n+1)!≥2^((n+1)-1) $.
Abbiamo che $ (n+1)! = (n+1)n! $ e $ 2^((n+1)-1) = (2^(n-1))2 $, quindi $ (n+1)n! ≥ 2^(n-1)2 $.
$ (n+1) (2^(n-1)) ≥ (2^(n-1))2 $ (Ipotesi induttiva).
Supponendo che $ (n+1) (2^(n-1)) ≥ (2^(n-1))2 $ sia vera, dal momento che ho entrambi i membri moltiplicati per $ (2^(n-1)) $, allora basta dimostrare che $ (n+1) ≥ 2 ↔ n ≥ 1 $ che vale per ogni $ n ≥ 1 $.
Può andare?
Io avrei fatto così, molto linearmente.
Base dell'induzione: per $n=1$ ho $1>=1$.
Passo induttivo: suppongo vero
$n! >= 2^(n-1)$.
Moltiplico entrambi i membri per $(n+1)$ e ho
$n! (n+1) >= (n+1)*2^(n-1)$.
Sapendo che $n>= 1$, posso concludere che
$(n+1)! >=2^n$.
Per esperienza personale, io ti consiglio quando hai a che fare con esercizi del genere di provare a sommare/moltiplicare entrambi i membri dell'ipotesi induttiva per numeri opportunamemte scelti e poi con rimaneggiamenti dedurre la tesi induttiva. (Poi certo ci sono casi in cui bisogna usare dei teoremi...)
In merito alla tua ultima domanda, devo dire che mi è difficile capire il perché delle ultime righe. L'" ipotesi induttiva" che hai messo non serve, avevi già finito.
Base dell'induzione: per $n=1$ ho $1>=1$.
Passo induttivo: suppongo vero
$n! >= 2^(n-1)$.
Moltiplico entrambi i membri per $(n+1)$ e ho
$n! (n+1) >= (n+1)*2^(n-1)$.
Sapendo che $n>= 1$, posso concludere che
$(n+1)! >=2^n$.
Per esperienza personale, io ti consiglio quando hai a che fare con esercizi del genere di provare a sommare/moltiplicare entrambi i membri dell'ipotesi induttiva per numeri opportunamemte scelti e poi con rimaneggiamenti dedurre la tesi induttiva. (Poi certo ci sono casi in cui bisogna usare dei teoremi...)
In merito alla tua ultima domanda, devo dire che mi è difficile capire il perché delle ultime righe. L'" ipotesi induttiva" che hai messo non serve, avevi già finito.
"abaco90":
$ (n+1) (2^(n-1)) ≥ (2^(n-1))2 $ (Ipotesi induttiva).
No.
L'ipotesi induttiva è che sia \( n! \geq 2^{n-1} \).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo