Esercizio principio induzione

lucadellapina
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

Risposte
Plepp
Innanzitutto, abbiamo ben presente cosa dice il principio d'induzione?

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 ;)

lucadellapina
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?

Plepp
Mi fa piacere ;)
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? :-D

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)!\]

lucadellapina
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.

Plepp
"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$.

lucadellapina
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

Plepp
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.

lucadellapina
ohhhhhhhh ho capito:) ti ringrazio infinitamente per la pazienza! confido nella pratica allora!

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.