Esercizio principio induzione
ho trovato quest'esercizio risolto sul principio di induzione in un libro ma non riesco a capirlo:
Dimostrare per induzione che $2^n < o = (n+1)!$
non so come scrivere le formule: 2 alla n è minore o uguale a (n+1) fattoriale.
Per n = 0 la diseguaglianza è verificata
Posto $P(n) : 2^n < o = (n+1)!$, dimostriamo che $P(n) \Rightarrow P(n+1)$
utilizzando 'ipotesi induttiva otteniamo
$2^n+1 = 2 x 2^n < o = 2 x (n+1)!$/i]
Intanto non capisco questo passaggio, capisco che $2^(n+1) = 2 x 2^n$ per la proprietà delle potenze ma non capisco perchè questo debba essere minore o uguale a $2(n+1)!$.
Per ottenere la tesi basta provare che :
$2 x (n+1)! < o = (n+2)! $ (e perchè??)
sviluppando il fattoriale e semplificando si ottiene
$2 x (n+1)! < o = (n+1)! x (n+2)$
$2 < o = n + 2$ il chè è sempre vero
Dimostrare per induzione che $2^n < o = (n+1)!$
non so come scrivere le formule: 2 alla n è minore o uguale a (n+1) fattoriale.
Per n = 0 la diseguaglianza è verificata
Posto $P(n) : 2^n < o = (n+1)!$, dimostriamo che $P(n) \Rightarrow P(n+1)$
utilizzando 'ipotesi induttiva otteniamo
$2^n+1 = 2 x 2^n < o = 2 x (n+1)!$/i]
Intanto non capisco questo passaggio, capisco che $2^(n+1) = 2 x 2^n$ per la proprietà delle potenze ma non capisco perchè questo debba essere minore o uguale a $2(n+1)!$.
Per ottenere la tesi basta provare che :
$2 x (n+1)! < o = (n+2)! $ (e perchè??)
sviluppando il fattoriale e semplificando si ottiene
$2 x (n+1)! < o = (n+1)! x (n+2)$
$2 < o = n + 2$ il chè è sempre vero
Risposte
Innanzitutto, abbiamo ben presente cosa dice il principio d'induzione?
Principio d'Induzione. Sia $S\subseteq NN$. Se accade che
Principio d'Induzione. Sia $S\subseteq NN$. Se accade che
[*:m12m76qj]$0\in S$;[/*:m:m12m76qj]
[*:m12m76qj] $\forall n\in NN$ è vera l'implicazione $[n\in S\implies n+1\in S]$,[/*:m:m12m76qj][/list:u:m12m76qj]
allora $S=NN$.
Chiaro questo, è evidente che se $\mathcal{P}(n)$ è un predicato sui numeri naturali, e se poniamo $S:=\{n\in NN\ |\ \mathcal{P}(n) \}$ (ovvero l'insieme degli $n$ per cui risulta vero $\mathcal{P}(n)$), possiamo dire quanto segue.
Principio d'Induzione 2.0. Se accade che
[*:m12m76qj]$\mathcal{P}(0)$ è vero;[/*:m:m12m76qj]
[*:m12m76qj] $\forall n\in NN$ è vera l'implicazione $[\mathcal{P}(n)\implies \mathcal{P}(n+1)]$, ovvero se, comunque si scelga un numero naturale $n$, supponendo vera $\mathcal{P}(n)$ si riesce a dimostrare che è vera $\mathcal{P}(n+1)$,[/*:m:m12m76qj][/list:u:m12m76qj]
allora $\mathcal{P}(n)$ è vera per ogni $n\in NN$.
Vediamo ora di applicare tutto questo alla tua situazione. Ti viene chiesto di provare che
\[\forall n\in\mathbb{N},\quad 2^n\le (n+1)!\]
utilizzando il principio d'induzione.
Bene, innanzitutto poni, $\forall n\in NN$, $\mathcal{P}(n):$ " $2^n\le (n+1)!$ ''; dimostra quindi che è vera $\mathcal{P}(0)$, ovvero che $2^0\le (0+1)!$ (c'è poco da dimostrare...ottieni immediatamente $1\le 1$, che è vero). In una dimostrazione in cui si utilizza il principio d'induzione, questo passo è generalmente detto il "passo base", o "base dell'induzione".
Ora vai avanti con quello che è noto come "passo induttivo": supponi che sia vera $\mathcal{P}(n)$ per un generico $n$. Se, sfruttando questo fatto, riesci a dimostrare che è vera $\mathcal{P}(n+1)$, allora hai dimostrato che $\mathcal{P}(n)$ è vera qualunque sia $n$.
Fissiamo quindi $n\in NN$ e supponiamo che sia $2^n\le (n+1)!$; sapendo questo, ci proponiamo di far vedere che
\[2^{n+1}\le \big((n+1)+1\big)!=(n+2)!\]
ovvero che è vera $\mathcal{P}(n+1)$.
Di fatti abbiamo
\[2^{n+1}=2\cdot 2^n\le [\text{avendo supposto che }2^n\le (n+1)!]\le 2\cdot (n+1)!\le (n+2)(n+1)!\stackrel{\text{def}}{=}(n+2)!\]
Hai dimostrato quindi che, qualunque sia $n$, se supponi vero $\mathcal{P}(n)$, allora hai che è vero anche $\mathcal{P}(n+1)$: il principio d'induzione ti dice che, se ciò accade, allora $\mathcal{P}(n)$ è vero per ogni $n\in NN$.
Spero sia tutto chiaro
ti ringrazio per avermi chiarito come funzione il principio di induzione perchè mi sono accorto che non l'avevo capito perfettamente.
Ma non riesco ancora a capire bene l'esercizio, mi torna tutto eccetto il punto che ho chiesto prima, da dove viene 2 x (n+1)! ?
da dove salta fuori?
Ma non riesco ancora a capire bene l'esercizio, mi torna tutto eccetto il punto che ho chiesto prima, da dove viene 2 x (n+1)! ?
da dove salta fuori?
Mi fa piacere
Siamo d'accordo sul fatto che se $c>0$ e $a\le b$, allora $ac\le bc$ e viceversa?
Sai che $2^{n+1}=2\cdot 2^n$ (proprietà delle potenze), e che $2^n\le (n+1)!$, perché hai supposto TU che questo è vero. Disponendo di queste informazioni, puoi concludere che
\[2^{n+1}=2\cdot 2^n \stackrel{\text{poiché } 2^n\le (n+1)!}{\le } 2\cdot (n+1)!\]
Ma non riesco ancora a capire bene l'esercizio, mi torna tutto eccetto il punto che ho chiesto prima, da dove viene 2 x (n+1)! ?
Siamo d'accordo sul fatto che se $c>0$ e $a\le b$, allora $ac\le bc$ e viceversa?
Sai che $2^{n+1}=2\cdot 2^n$ (proprietà delle potenze), e che $2^n\le (n+1)!$, perché hai supposto TU che questo è vero. Disponendo di queste informazioni, puoi concludere che
\[2^{n+1}=2\cdot 2^n \stackrel{\text{poiché } 2^n\le (n+1)!}{\le } 2\cdot (n+1)!\]
Ma questo è il secondo principio delle disequazioni che dice che moltiplicando o dividendo ambo i membri per uno stesso numero diverso da zero no altero la verità della disequazione
quindi se io ho 2 < 4 posso dire 2 x 2 < 2 x 4 ed è ancora vera
ma qui io ho che 2^(n+1) = 2 x 2^n per la proprietà delle potenze non perchè applico il criterio di equivalenza.
inoltre se è vera P(n) io dovrei mettere al secondo membro (n+2)! che non è affatto uguale a 2(n+1)!
Sono cosciente che il mio ragionamento è sbagliato e che è giusto il tuo e quello del libro però continuo a non capire.
quindi se io ho 2 < 4 posso dire 2 x 2 < 2 x 4 ed è ancora vera
ma qui io ho che 2^(n+1) = 2 x 2^n per la proprietà delle potenze non perchè applico il criterio di equivalenza.
inoltre se è vera P(n) io dovrei mettere al secondo membro (n+2)! che non è affatto uguale a 2(n+1)!
Sono cosciente che il mio ragionamento è sbagliato e che è giusto il tuo e quello del libro però continuo a non capire.
"whoarang":
inoltre se è vera P(n) io dovrei mettere al secondo membro (n+2)! che non è affatto uguale a 2(n+1)!
No. Lì tu sei arrivato a dire che $2^n+1\le 2(n+1)!$, ma non hai finito, perché come dici dovresti dimostrare che $2^n+1\le (n+2)!$. Ora, sapendo che $2^n+1\le 2(n+1)!$, ti basta dimostrare che $2(n+1)!\le (n+2)!$ per poi applicare la proprietà transitiva di $\le$.
ok quindi 2(n+1)! è preso a caso? cioè non viene dedotto da niente di verificato e tantomeno dall'ipotesi, da dove lo tiro fuori?
mettendo che io avevo un esercizio così all'esame cosa dovevo fare? mettermi a tirare polinomi a caso? è quello che non riesco a capire. ok uso la proprietà transitiva, ma da dove prendo il termine di mezzo?
scusa ci vuole tanta pazienza con me ho il cervello un po' arruginito
mettendo che io avevo un esercizio così all'esame cosa dovevo fare? mettermi a tirare polinomi a caso? è quello che non riesco a capire. ok uso la proprietà transitiva, ma da dove prendo il termine di mezzo?
scusa ci vuole tanta pazienza con me ho il cervello un po' arruginito
Come sarebbe dire "preso a caso"?! Il fatto che $2\cdot 2^{n}\le 2 \cdot (n+1)!$ è vero per l'ipotesi induttiva, cioè è vero perché si è supposto vero che $2^n\le (n+1)!$.
Una domanda - leggermente... - più legittima sarebbe: "chi mi dice che devo procedere così, ovvero che devo passare per quella disuguaglianza prima di arrivare a dimostrare la disuguaglianza che m'interessa?"
Risposta: nessuno, anche se, con la pratica, ti sembrerà la cosa più ovvia del mondo. In questo caso particolare, però, quel passaggio è abbastanza scontato, perché solo in quel modo riesci ad utilizzare nel tuo ragionamento l'ipotesi induttiva (i.e. $2^n\le (n+1)!$), che è quello che devi fare per dimostrare la tesi.
Una domanda - leggermente... - più legittima sarebbe: "chi mi dice che devo procedere così, ovvero che devo passare per quella disuguaglianza prima di arrivare a dimostrare la disuguaglianza che m'interessa?"
Risposta: nessuno, anche se, con la pratica, ti sembrerà la cosa più ovvia del mondo. In questo caso particolare, però, quel passaggio è abbastanza scontato, perché solo in quel modo riesci ad utilizzare nel tuo ragionamento l'ipotesi induttiva (i.e. $2^n\le (n+1)!$), che è quello che devi fare per dimostrare la tesi.
ohhhhhhhh ho capito:) ti ringrazio infinitamente per la pazienza! confido nella pratica allora!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo