Induzione
Salve, scusatemi se apro l'ennesimo post sull'induzione matematica, ma gli esempi che ho trovato non mi sono affatto d'aiuto.
Non ricordo proprio l'applicazione del passo induttivo, e questo mi crea davvero non pochi problemi.
Allora l'esercizio (banale) ma che mi crea dubbi.
dimostrare: $2^(2n)<=c*2^n$ per $ c >0$ costante e $n>=0$
caso base .... OK
passo induttivo:
$n>=1$
$2^(2(n+1))<=c*2^(n+1)$
$2^(2(n+1))=2^2*2^(2n) <= 2^2*(c*2^n)$
e poi, qua non capisco cosa devo applicare, spero in un'illuminazione.
Perpiacere scrivete passo passo, non usate scorciatoie magiche (negli altri esempi sono quelle che mi fanno perdere).
Ringrazio davvero, esercizio banale, ma che è cruciale.
Non ricordo proprio l'applicazione del passo induttivo, e questo mi crea davvero non pochi problemi.
Allora l'esercizio (banale) ma che mi crea dubbi.
dimostrare: $2^(2n)<=c*2^n$ per $ c >0$ costante e $n>=0$
caso base .... OK
passo induttivo:
$n>=1$
$2^(2(n+1))<=c*2^(n+1)$
$2^(2(n+1))=2^2*2^(2n) <= 2^2*(c*2^n)$
e poi, qua non capisco cosa devo applicare, spero in un'illuminazione.
Perpiacere scrivete passo passo, non usate scorciatoie magiche (negli altri esempi sono quelle che mi fanno perdere).
Ringrazio davvero, esercizio banale, ma che è cruciale.
Risposte
Allora, come hai detto tu per $n=0$ è ovvio. Supponiamo ora che la tesi sia vera fino a $n$ e proviamola per $n+1$.
Dire che vale per $n$ significa che $2^(2n)<=C*2^n$.
Consideriamo ora $2^(2(n+1))$ e operiamo nel seguente modo:
$2^(2(n+1))=2^(2n+2)=2^(2n)*4$ e utilizzando l'ipotesi induttiva, $<=C*2^(n)*4=2C*2^(n+1)=\bar C*2^(n+1)$. che è quanto avevamo da dimostrare.
Ti è tutto chiaro ? Ho provato a risolvertelo per lasciarti una traccia da seguire (sempre che non abbia sbagliato qualcosa
). Va da sè che ora devi fartene molti per conto tuo per impratichirti
Dire che vale per $n$ significa che $2^(2n)<=C*2^n$.
Consideriamo ora $2^(2(n+1))$ e operiamo nel seguente modo:
$2^(2(n+1))=2^(2n+2)=2^(2n)*4$ e utilizzando l'ipotesi induttiva, $<=C*2^(n)*4=2C*2^(n+1)=\bar C*2^(n+1)$. che è quanto avevamo da dimostrare.
Ti è tutto chiaro ? Ho provato a risolvertelo per lasciarti una traccia da seguire (sempre che non abbia sbagliato qualcosa
). Va da sè che ora devi fartene molti per conto tuo per impratichirti
sarà una momentanea regressione, ma proprio non mi ricordo sti passaggi.
proprio questo punto non capisco (come in altri esercizi che ho rivisto):
applicazione passo induttivo $<= c*(2^n)*4$ fin qua OK adesso $ = 2*c*2^(n+1)$ da dove salta fuori il 2 e n+1 viene fuori dalla scoposizione del 4? o è una sostituzione?
Capito questo son a cavallo
cmq intanto grazie
proprio questo punto non capisco (come in altri esercizi che ho rivisto):
applicazione passo induttivo $<= c*(2^n)*4$ fin qua OK adesso $ = 2*c*2^(n+1)$ da dove salta fuori il 2 e n+1 viene fuori dalla scoposizione del 4? o è una sostituzione?
Capito questo son a cavallo
cmq intanto grazie
Il passaggio è solo di algebra: scrivo $4=2^2$. a quel punto osservo che $2^n*2=2^(n+1)$. Mi resta fuori un 2 che "inglobo" nella C.
perfetto perfetto...
ora se non ci fosse stata la costante, con il 2 come ti comportavi? nasconderlo da qualche parte
scusa delle domande...ma meglio capire tutto prima che durante una dimostrazione ad un orale....
grazie
ora se non ci fosse stata la costante, con il 2 come ti comportavi? nasconderlo da qualche parte
scusa delle domande...ma meglio capire tutto prima che durante una dimostrazione ad un orale....
grazie
Se la costante non ci fosse stata cambiava l'esercizio perchè la costante compare nel testo stesso ! Quindi bisognava vedere che cosa c'era da dimostrare per decidere come comportarsi.
Di esercizi simili ce ne sono a bizzeffe, te ne scrivo un paio così ti puoi esercitare:
Si dimostri per induzione che per ogni intero $n>=1$, $2^(3n-1)+3$ è divisibile per 7.
Si dimostri per induzione che per ogni intero $n>=3$, $2+2^2+2^3+ . . . + 2^n=2^(n+1)-2$.
Prova un po' a vedere se ci riesci, se no scrivi pure quali problemi hai !
Di esercizi simili ce ne sono a bizzeffe, te ne scrivo un paio così ti puoi esercitare:
Si dimostri per induzione che per ogni intero $n>=1$, $2^(3n-1)+3$ è divisibile per 7.
Si dimostri per induzione che per ogni intero $n>=3$, $2+2^2+2^3+ . . . + 2^n=2^(n+1)-2$.
Prova un po' a vedere se ci riesci, se no scrivi pure quali problemi hai !
"Relegal":
Si dimostri per induzione che per ogni intero $n>=1$, $2^(3n-1)$ è divisibile per 7.
Penso che tu intenda $2^(3n) -1$
"Gi8":
[quote="Relegal"]Si dimostri per induzione che per ogni intero $n>=1$, $2^(3n-1)$ è divisibile per 7.
Penso che tu intenda $2^(3n) -1$[/quote]
No . . intendevo proprio $2^(3n-1)$, il problema è che ho dimenticato un $+3$ in fondo
Ora lo modifico. Grazie per l'osservazione !
Perfetto, tutto chiaro.
Alla fine era solo l'ultimo passaggio che non capivo e non ricordavo.
Ho ritrovato il senso delle dimostrazioni.
Ti ringrazio davvero.
Alla fine era solo l'ultimo passaggio che non capivo e non ricordavo.
Ho ritrovato il senso delle dimostrazioni.
Ti ringrazio davvero.
Figurati, felice di esserti stato d'aiuto. A risentirci, buon proseguimento !
Posso fare un'osservazione post res?
La proposizione, così com'è enunciata, è falsa.
Non esiste nessuna costante [tex]$C>0$[/tex] tale che per ogni [tex]$n\in \mathbb{N}$[/tex] risulti [tex]$2^{2n}\leq C\ 2^n$[/tex]; infatti dividendo per [tex]$2^n$[/tex] m.a.m. si otterrebbe [tex]$2^n\leq C$[/tex], ma sappiamo tutti che la successione di termine generale [tex]$2^n$[/tex] non è limitata superiormente.
D'altra parte, se il vero enunciato fosse "per ogni [tex]$n\in \mathbb{N}$[/tex] esiste una costante [tex]$C_n>0$[/tex] tale che [tex]$2^{2n}\leq C_n\ 2^n$[/tex]", allora la dimostrazione per induzione sarebbe inutile: invero, dato che [tex]$2^{2n}=2^n\ 2^n$[/tex], basterebbe porre per definizione [tex]$C_n:=2^n$[/tex] per avere addirittura [tex]$2^{2n}=C_n\ 2^n$[/tex].
Curiosità: dove l'hai preso l'esercizio?
La proposizione, così com'è enunciata, è falsa.
Non esiste nessuna costante [tex]$C>0$[/tex] tale che per ogni [tex]$n\in \mathbb{N}$[/tex] risulti [tex]$2^{2n}\leq C\ 2^n$[/tex]; infatti dividendo per [tex]$2^n$[/tex] m.a.m. si otterrebbe [tex]$2^n\leq C$[/tex], ma sappiamo tutti che la successione di termine generale [tex]$2^n$[/tex] non è limitata superiormente.
D'altra parte, se il vero enunciato fosse "per ogni [tex]$n\in \mathbb{N}$[/tex] esiste una costante [tex]$C_n>0$[/tex] tale che [tex]$2^{2n}\leq C_n\ 2^n$[/tex]", allora la dimostrazione per induzione sarebbe inutile: invero, dato che [tex]$2^{2n}=2^n\ 2^n$[/tex], basterebbe porre per definizione [tex]$C_n:=2^n$[/tex] per avere addirittura [tex]$2^{2n}=C_n\ 2^n$[/tex].
Curiosità: dove l'hai preso l'esercizio?
Io ho pensato che la costante $C$ fosse una costante dipendente dal valore di $n$, quindi, come hai osservato tu, sarebbe più giusto scrivere $C_n$ per evidenziarne la dipendenza. Infatti, nella dimostrazione che ho proposto per il passo $n+1 - $esimo, la costante $C$ dell'ipotesi induttiva viene moltiplicata per un fattore 2 ottenendo così una nuova costante $\bar C$
Penso che questo esercizio sia stato pensato non tanto per dimostrare una proposizione, quanto per impratichirsi con la tecnica di dimostrazione per induzione. Il discorso potrebbe essere stato qualcosa del tipo: " prendete questa affermazione di per sè ovvia e provate a dimostrarla per induzione su $n$".
Un po' come quando la professoressa di algebra I ci dimostrò con una pagina di calcoli che dato un gruppo finito di ordine $N$, ogni suo sottogruppo proprio ha ordine $<=N/2$. Il tutto avendoci detto che esiste un teorema ancora più forte, che afferma cioè che l'ordine di un sottogruppo è un divisore proprio di $N$ rendendo così ovvia la proposizione precedente.
Qui si vuole dimostrare una prop. ovvia ma non si possono usare le leggi di cancellazione
!
Penso che questo esercizio sia stato pensato non tanto per dimostrare una proposizione, quanto per impratichirsi con la tecnica di dimostrazione per induzione. Il discorso potrebbe essere stato qualcosa del tipo: " prendete questa affermazione di per sè ovvia e provate a dimostrarla per induzione su $n$".
Un po' come quando la professoressa di algebra I ci dimostrò con una pagina di calcoli che dato un gruppo finito di ordine $N$, ogni suo sottogruppo proprio ha ordine $<=N/2$. Il tutto avendoci detto che esiste un teorema ancora più forte, che afferma cioè che l'ordine di un sottogruppo è un divisore proprio di $N$ rendendo così ovvia la proposizione precedente
.Qui si vuole dimostrare una prop. ovvia ma non si possono usare le leggi di cancellazione
!
Scusate, forse ho fatto un errore ha non dare la formulazione dell'esercizio completo (ma che è equivalente informalmente).
esercizio: dimostrare che $2^(2n) in O(2^n)$ cioè se appartiene a O-grande (teoria della complessità).
Per dimostrarlo ci sono vari modi, introducendo il concetto di limite, per induzione, ecc
Io ho scelto il secondo, ma vi ho fornito la definizione formale di O-grande (forse definito male da me) messa a punto con l'esercizio,
perchè volevo capire come si risolveva l'ultimo passaggio dell'induzione matematica (quella complete con tutti i passaggi, senza "forzature"),
indipendentemente dall'esercizio che è collegato con altre definizioni come quello di O-grande.
La definzione formale di O-grande, comuque è questa:
Definizione (Notazione O). Sia $g(n)$ una funzione di costo; indichiamo con $O(g(n))$ l’insieme delle
funzioni $f(n)$ tali per cui:
$EEc > 0;m >= 0 : 0 <= f(n) <= cg(n); AAn >= m$
In altre parole:
- asintoticamente la funzione giace sotto $cg(n)$;
- $f(n)$ cresce al più come $g(n)$
- $g(n)$ è un limite asintotico superiore per $f(n)$
Se volete correggere l'esercizio in modo corretto forse sarebbe meglio, così da non avere dubbi.
Comuque io ho capito (anzi mi sono ririricordato) come funziona l'induzione matematica (con tutti i passaggi), era questo lo scopo del thread.
Se volete correggere mi fate un favore.
Grazie mille ad entrambi, davvero.
esercizio: dimostrare che $2^(2n) in O(2^n)$ cioè se appartiene a O-grande (teoria della complessità).
Per dimostrarlo ci sono vari modi, introducendo il concetto di limite, per induzione, ecc
Io ho scelto il secondo, ma vi ho fornito la definizione formale di O-grande (forse definito male da me) messa a punto con l'esercizio,
perchè volevo capire come si risolveva l'ultimo passaggio dell'induzione matematica (quella complete con tutti i passaggi, senza "forzature"),
indipendentemente dall'esercizio che è collegato con altre definizioni come quello di O-grande.
La definzione formale di O-grande, comuque è questa:
Definizione (Notazione O). Sia $g(n)$ una funzione di costo; indichiamo con $O(g(n))$ l’insieme delle
funzioni $f(n)$ tali per cui:
$EEc > 0;m >= 0 : 0 <= f(n) <= cg(n); AAn >= m$
In altre parole:
- asintoticamente la funzione giace sotto $cg(n)$;
- $f(n)$ cresce al più come $g(n)$
- $g(n)$ è un limite asintotico superiore per $f(n)$
Se volete correggere l'esercizio in modo corretto forse sarebbe meglio, così da non avere dubbi.
Comuque io ho capito (anzi mi sono ririricordato) come funziona l'induzione matematica (con tutti i passaggi), era questo lo scopo del thread.
Se volete correggere mi fate un favore.
Grazie mille ad entrambi, davvero.
Ah, ecco... Non mi ero sbagliato, vuoi proprio dimostrare una cosa falsa.
La notazione [tex]$f\in \text{O} (g)$[/tex] intorno a [tex]$x_0$[/tex], nell'ipotesi che [tex]$g$[/tex] non sia nulla intorno a [tex]$x_0$[/tex], equivale a dire che il rapporto [tex]$\frac{|f|}{|g|}$[/tex] si mantiene limitato intorno a [tex]$x_0$[/tex] ([tex]$x_0$[/tex] è un punto di accumulazione per entrambi gli insiemi di definizione di [tex]$f$[/tex] e [tex]$g$[/tex]).
E, come ben sa chi ha studiato Analisi I, il rapporto tra [tex]$f(n):=2^{2n}=4^n$[/tex] e [tex]$g(n):=2^n$[/tex] non si mantiene affatto limitato intorno a [tex]$\infty$[/tex].
La notazione [tex]$f\in \text{O} (g)$[/tex] intorno a [tex]$x_0$[/tex], nell'ipotesi che [tex]$g$[/tex] non sia nulla intorno a [tex]$x_0$[/tex], equivale a dire che il rapporto [tex]$\frac{|f|}{|g|}$[/tex] si mantiene limitato intorno a [tex]$x_0$[/tex] ([tex]$x_0$[/tex] è un punto di accumulazione per entrambi gli insiemi di definizione di [tex]$f$[/tex] e [tex]$g$[/tex]).
E, come ben sa chi ha studiato Analisi I, il rapporto tra [tex]$f(n):=2^{2n}=4^n$[/tex] e [tex]$g(n):=2^n$[/tex] non si mantiene affatto limitato intorno a [tex]$\infty$[/tex].
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo