Induzione

[gugo82]

Posso fare un'osservazione post res?

La proposizione, così com'è enunciata, è falsa.
Non esiste nessuna costante \( \displaystyle C>0 \) tale che per ogni \( \displaystyle n\in \mathbb{N} \) risulti \( \displaystyle 2^{2n}\leq C\ 2^n \) ; infatti dividendo per \( \displaystyle 2^n \) m.a.m. si otterrebbe \( \displaystyle 2^n\leq C \) , ma sappiamo tutti che la successione di termine generale \( \displaystyle 2^n \) non è limitata superiormente.

D'altra parte, se il vero enunciato fosse "per ogni \( \displaystyle n\in \mathbb{N} \) esiste una costante \( \displaystyle C_n>0 \) tale che \( \displaystyle 2^{2n}\leq C_n\ 2^n \) ", allora la dimostrazione per induzione sarebbe inutile: invero, dato che \( \displaystyle 2^{2n}=2^n\ 2^n \) , basterebbe porre per definizione \( \displaystyle C_n:=2^n \) per avere addirittura \( \displaystyle 2^{2n}=C_n\ 2^n \) .

Curiosità: dove l'hai preso l'esercizio?

[Relegal]

Io ho pensato che la costante \( \displaystyle {C} \) fosse una costante dipendente dal valore di \( \displaystyle {n} \), quindi, come hai osservato tu, sarebbe più giusto scrivere \( \displaystyle {C}_{{n}} \) per evidenziarne la dipendenza. Infatti, nella dimostrazione che ho proposto per il passo \( \displaystyle {n}+{1}- \)esimo, la costante \( \displaystyle {C} \) dell'ipotesi induttiva viene moltiplicata per un fattore 2 ottenendo così una nuova costante \( \displaystyle {\overline{{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 \( \displaystyle {n} \)".
Un po' come quando la professoressa di algebra I ci dimostrò con una pagina di calcoli che dato un gruppo finito di ordine \( \displaystyle {N} \), ogni suo sottogruppo proprio ha ordine \( \displaystyle \le\frac{{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 \( \displaystyle {N} \) rendendo così ovvia la proposizione precedente .
Qui si vuole dimostrare una prop. ovvia ma non si possono usare le leggi di cancellazione !

[hamming_burst]

Scusate, forse ho fatto un errore ha non dare la formulazione dell'esercizio completo (ma che è equivalente informalmente).

esercizio: dimostrare che \( \displaystyle {{2}}^{{{2}{n}}}\in{O}{\left({{2}}^{{n}}\right)} \) 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 \( \displaystyle {g{{\left({n}\right)}}} \) una funzione di costo; indichiamo con \( \displaystyle {O}{\left({g{{\left({n}\right)}}}\right)} \) l’insieme delle
funzioni \( \displaystyle {f{{\left({n}\right)}}} \) tali per cui:

\( \displaystyle \exists{c}\gt{0};{m}\ge{0}:{0}\le{f{{\left({n}\right)}}}\le{c}{g{{\left({n}\right)}}};\forall{n}\ge{m} \)

In altre parole:

- asintoticamente la funzione giace sotto \( \displaystyle {c}{g{{\left({n}\right)}}} \);
- \( \displaystyle {f{{\left({n}\right)}}} \) cresce al più come \( \displaystyle {g{{\left({n}\right)}}} \)
- \( \displaystyle {g{{\left({n}\right)}}} \) è un limite asintotico superiore per \( \displaystyle {f{{\left({n}\right)}}} \)

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.

[gugo82]

Ah, ecco... Non mi ero sbagliato, vuoi proprio dimostrare una cosa falsa.

La notazione \( \displaystyle f\in \text{O} (g) \) intorno a \( \displaystyle x_0 \) , nell'ipotesi che \( \displaystyle g \) non sia nulla intorno a \( \displaystyle x_0 \) , equivale a dire che il rapporto \( \displaystyle \frac{|f|}{|g|} \) si mantiene limitato intorno a \( \displaystyle x_0 \) ( \( \displaystyle x_0 \) è un punto di accumulazione per entrambi gli insiemi di definizione di \( \displaystyle f \) e \( \displaystyle g \) ).

E, come ben sa chi ha studiato Analisi I, il rapporto tra \( \displaystyle f(n):=2^{2n}=4^n \) e \( \displaystyle g(n):=2^n \) non si mantiene affatto limitato intorno a \( \displaystyle \infty \) .