Principio di induzione
Ciao a tutti.
mi serve il vostro aiuto.Qualcuno di voi potrebbe spiegarmi bene il principio di induzione??
e farmi vedere a fare questi due esercizi??
1. 2n < 2^n
2. (n+3)^2<=2^(n+3)
grazie
mi serve il vostro aiuto.Qualcuno di voi potrebbe spiegarmi bene il principio di induzione??
e farmi vedere a fare questi due esercizi??
1. 2n < 2^n
2. (n+3)^2<=2^(n+3)
grazie
Risposte
"jadugar":
Ciao a tutti.
mi serve il vostro aiuto.Qualcuno di voi potrebbe spiegarmi bene il principio di induzione??
e farmi vedere a fare questi due esercizi??
1. 2n < 2^n
2. (n+3)^2<=2^(n+3)
grazie
In pratica è molto semplice. Devi passare attraverso due "passi".
Sia $P(n) : 2n < 2^n $ un predicato sull'insieme dei numeri naturali.
1) La base dell'induzione : cioè devi verificare che la proprietà, per esempio $P(n): 2n < 2^n$, sia vera per un certo numero naturale $n_0$. Quindi devi verificare $P(n_0)$.
2) Passo induttivo : Se puoi provare che, dalla verità di $P(n)$ (dove la variabile $n$ è un non ben specificato numero naturale) discende la verità di $P(n+1)$, allora sei sicuro che la proprietà è vera $AA n , n >= n_0$.
Cosa significa? Beh, la 1) ti dice che P(n) è vera per un ben specificato $n_0$. La 2) ti dice che se la proprietà vale per un $n$ qualsiasi, allora vale automaticamente anche per il naturale successivo $n+1$ (quindi l'implicazione $P(n) Rightarrow P(n+1) $).
Quindi, se $P(n_0)$ è vera, il passo induttivo ci dice che $P(n_0 + 1)$ è vera.
Ma se $P(n_0 + 1)$ è vera, ancora per il passo induttivo so che $P((n_0 + 1) + 1) è vera.
E proseguendo è evidente che $P(n)$ è vera per ogni $n$ (da $n_0$ in poi).
Abbiamo: $2n < 2^n$
Proviamo a verificare che questa formula vale per tutti i naturali (partendo da $n_0 = 0$).
1) $P(0)$ : $2*0 < 2^0$ cioè $0 < 1$
E quindi è verificata per $0$.
1) $P(n) Rightarrow P(n+1)$ :
Valga $2n < 2^n$. Dobbiamo dimostrare $2n < 2^n Rightarrow 2(n+1) < 2^(n+1)$.
Moltiplicando per $2$ ambo i membri si ottiene $2*2 n < 2*2^n$
cioè $4 n < 2^(n+1)$.
Ma a noi serve che a primo membro compaia $2(n+1)$, cioè $2n + 2$.
Ma la minorazione $2n + 2 < 4 n$ è possibile solo per $n >= 2$ (e non per $n >= 0$ ).
In sostanza mi accorgo che non riesco a concludere.
Il "bug" qual è? Per $n in { 1 , 2 }$ non è vera $P(n)$ (intuitivamente puoi pensare di confrontare i due grafici $2^x$ e $2x$, limitando le considerazioni alle ascisse naturali ).
Prova tu a verificare che $2n < 2^n$ è vera $AA n , n >= 3$ ( e non $AA n in NN$ ).
E' semplice adesso, visto che ora, per il passo induttivo (2), è lecita la minorazione che ti ho suggerito (perché lavori con naturali "da $3$ in poi" ).
$2n + 2 < 4 n < 2^(n+1)$
Proviamo a verificare che questa formula vale per tutti i naturali (partendo da $n_0 = 0$).
1) $P(0)$ : $2*0 < 2^0$ cioè $0 < 1$
E quindi è verificata per $0$.
1) $P(n) Rightarrow P(n+1)$ :
Valga $2n < 2^n$. Dobbiamo dimostrare $2n < 2^n Rightarrow 2(n+1) < 2^(n+1)$.
Moltiplicando per $2$ ambo i membri si ottiene $2*2 n < 2*2^n$
cioè $4 n < 2^(n+1)$.
Ma a noi serve che a primo membro compaia $2(n+1)$, cioè $2n + 2$.
Ma la minorazione $2n + 2 < 4 n$ è possibile solo per $n >= 2$ (e non per $n >= 0$ ).
In sostanza mi accorgo che non riesco a concludere.
Il "bug" qual è? Per $n in { 1 , 2 }$ non è vera $P(n)$ (intuitivamente puoi pensare di confrontare i due grafici $2^x$ e $2x$, limitando le considerazioni alle ascisse naturali ).
Prova tu a verificare che $2n < 2^n$ è vera $AA n , n >= 3$ ( e non $AA n in NN$ ).
E' semplice adesso, visto che ora, per il passo induttivo (2), è lecita la minorazione che ti ho suggerito (perché lavori con naturali "da $3$ in poi" ).
$2n + 2 < 4 n < 2^(n+1)$
L'altra proprietà da dimostrare, invece, è vera $AA n , n >= 1$.
Non è difficile. Se non ci riesci: posta un tuo tentativo di risoluzione per individuare il punto in cui ti blocchi.
Non è difficile. Se non ci riesci: posta un tuo tentativo di risoluzione per individuare il punto in cui ti blocchi.
Innanzitutto grazie per le risposte.
Cambiamo il predicato dell'espressione per farla diventare:
2n<=2^n
1) La base dell'induzione : Verifico che sia vera per un "n". Per esempio : P(0) := 0<1 o P(1):=2<=2
2)Passo induttivo: supposta vera un n=k devo dimostrarla per k+1
2*2n<=2*2^n
4n<=2^n+1
A sinistra invece di 40 dovrei avere 2(n+1) o 2n+2n.Adesso quali considerazioni devo fare???
Ti ringrazio di cuore per l'attenzione.
Cambiamo il predicato dell'espressione per farla diventare:
2n<=2^n
1) La base dell'induzione : Verifico che sia vera per un "n". Per esempio : P(0) := 0<1 o P(1):=2<=2
2)Passo induttivo: supposta vera un n=k devo dimostrarla per k+1
2*2n<=2*2^n
4n<=2^n+1
A sinistra invece di 40 dovrei avere 2(n+1) o 2n+2n.Adesso quali considerazioni devo fare???
Ti ringrazio di cuore per l'attenzione.
Mi cambi le carte in gioco; ora è $<=$ e non $<$. 
Va bene, comunque. Semplicemente basta minorare $4n$ con $2n + 2$.
Quando è possibile? Per quali $n$ effettivamente $2n + 2 <= 4n$ ?
Per $n >= 1$.
Riassunto: Avendo verificato $P(1)$ come base dell'induzione, a te interessa che l'implicazione $P(n) Rightarrow P(n+1)$ (il passo induttivo) sia vera per gli $n >= 1$. Quindi a patto di considerare $n$ naturali da $1$ in poi, è vero che $2n + 2 <= 4n$.
Allora $2(n+1)<=4n<=2^(n+1)$
cioè $2(n+1) <= 2^(n+1)$ , che è proprio $P(n+1)$.
In sostanza se sai che è vera per $1$, e lo sai visto che l'hai verificato "manualmente", l'implicazione ti garantisce che è vera anche $P(1+1)$ cioè $P(2)$.
Essendo vera $P(2)$ è vera $P(2 + 1)$ cioè $P(3)$, sempre per l'implicazione $P(n) Rightarrow P(n+1)$. E così via...
(poi è una tua scelta se in $NN$ mettere lo $0$ o meno).
Va bene, comunque. Semplicemente basta minorare $4n$ con $2n + 2$.
Quando è possibile? Per quali $n$ effettivamente $2n + 2 <= 4n$ ?
Per $n >= 1$.
Riassunto: Avendo verificato $P(1)$ come base dell'induzione, a te interessa che l'implicazione $P(n) Rightarrow P(n+1)$ (il passo induttivo) sia vera per gli $n >= 1$. Quindi a patto di considerare $n$ naturali da $1$ in poi, è vero che $2n + 2 <= 4n$.
Allora $2(n+1)<=4n<=2^(n+1)$
cioè $2(n+1) <= 2^(n+1)$ , che è proprio $P(n+1)$.
In sostanza se sai che è vera per $1$, e lo sai visto che l'hai verificato "manualmente", l'implicazione ti garantisce che è vera anche $P(1+1)$ cioè $P(2)$.
Essendo vera $P(2)$ è vera $P(2 + 1)$ cioè $P(3)$, sempre per l'implicazione $P(n) Rightarrow P(n+1)$. E così via...
(poi è una tua scelta se in $NN$ mettere lo $0$ o meno).
"Seneca":
Quando è possibile? Per quali $n$ effettivamente $2n + 2 <= 4n$ ?
Per $n >= 1$.
Aggiungo un piccolo dettaglio. Se, per dimostrare il passo induttivo, devi fare (p.es.) una minorazione che è lecita solo per $n >= 5$ (non è questo il caso) , non puoi semplicemente dire: Verifico $P(0)$ e poi dimostro che $P(n) Rightarrow P(n+1)$ utilizzando quella minorazione e concludendo "allora $P(n)$ vale per tutti i naturali".
Capisci il perché?
"Seneca":
[quote="Seneca"]
Quando è possibile? Per quali $n$ effettivamente $2n + 2 <= 4n$ ?
Per $n >= 1$.
Aggiungo un piccolo dettaglio. Se, per dimostrare il passo induttivo, devi fare (p.es.) una minorazione che è lecita solo per $n >= 5$ (non è questo il caso) , non puoi semplicemente dire: Verifico $P(0)$ e poi dimostro che $P(n) Rightarrow P(n+1)$ utilizzando quella minorazione e concludendo "allora $P(n)$ vale per tutti i naturali".
Capisci il perché?[/quote]
Ah ok.Ora stò iniziando a capire.Grazie!!
Scusami se ritardo a rispondere.
In base all'ultimo esercizio che mi hai scitto(penultimo post). Ora se ho capito bene per concludere dico che la ipotesi è vera per n>1.Giusto??
Cmq dai adesso molto più chiaro di prima.
Grazie ancora
Ciao
Nel caso di prima era tutto liscio. Infatti la maggiorazione era consentita per $x >= 1$. Quindi, verifichi che vale $P(1)$ e sei tranquillo che ogni volta che è vera $P(n)$ è vera anche $P(n+1)$. Così hai dimostrato che vale per $NN$. $1$ è il minimo numero per cui è vera la proprietà.
Se in $NN$ ci vuoi mettere $0$, logicamente devi fare il magro sforzo di verificare che è vera anche $P(0)$ .
Se in $NN$ ci vuoi mettere $0$, logicamente devi fare il magro sforzo di verificare che è vera anche $P(0)$ .
Ciao
scusami per il ritardo.
Le tue risposte sono state soddisfacenti al massimo, per ciò ti devo solo ringraziare veramente di cuore per avermi aiutato.
Grazie tantissimo.
Se posso ricambiare in qlk maniera, let me know plz!!!
Ciao
Grazie ancora
scusami per il ritardo.
Le tue risposte sono state soddisfacenti al massimo, per ciò ti devo solo ringraziare veramente di cuore per avermi aiutato.
Grazie tantissimo.
Se posso ricambiare in qlk maniera, let me know plz!!!
Ciao
Grazie ancora
Ciao ho fatto il secondo esercizio, credo sia giusto.Guarda http://img714.imageshack.us/img714/5787/immagineyau.th.png
CIao
CIao
"jadugar":
Ciao ho fatto il secondo esercizio, credo sia giusto.Guarda http://img714.imageshack.us/img714/5787/immagineyau.th.png
CIao
Non si legge niente.
@Seneca: Elimina il .th dal link lasciando l'estensione .png.
"gugo82":
@Seneca: Elimina il .th dal link lasciando l'estensione .png.
Si, togliendo ".th", si vede bene
"Seneca":
[quote="jadugar"]Ciao ho fatto il secondo esercizio, credo sia giusto.Guarda http://img714.imageshack.us/img714/5787/immagineyau.th.png
CIao
Non si legge niente.[/quote]
ai guardato???
[OT]
La "h"...
[/OT]
La "h"...
[/OT]
"gugo82":
[OT]
La "h"...
[/OT]
E' vero hai ragione.
Hai guardato Seneca??
Ciao Seneca, stavo guardando la tua dimostrazione e non riesco a capire perchè hai moltiplicato per 2 entrambi i membri e perchè devo fare una minorazione per arrivare alla soluzione finale.
Quando dici :
"Semplicemente basta minorare con $2n + 2 < 4n$ . "
Puoi spiegarmi il perchè ? non riesco a capirlo.
Grazie
GC
Quando dici :
"Semplicemente basta minorare con $2n + 2 < 4n$ . "
Puoi spiegarmi il perchè ? non riesco a capirlo.
Grazie
GC
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo