Induzione

[hamming_burst]

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: \( \displaystyle {{2}}^{{{2}{n}}}\le{c}\cdot{{2}}^{{n}} \) per \( \displaystyle {c}\gt{0} \) costante e \( \displaystyle {n}\ge{0} \)

caso base .... OK

passo induttivo:

\( \displaystyle {n}\ge{1} \)

\( \displaystyle {{2}}^{{{2}{\left({n}+{1}\right)}}}\le{c}\cdot{{2}}^{{{n}+{1}}} \)

\( \displaystyle {{2}}^{{{2}{\left({n}+{1}\right)}}}={{2}}^{{2}}\cdot{{2}}^{{{2}{n}}}\le{{2}}^{{2}}\cdot{\left({c}\cdot{{2}}^{{n}}\right)} \)

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.

[Relegal]

Allora, come hai detto tu per \( \displaystyle {n}={0} \) è ovvio. Supponiamo ora che la tesi sia vera fino a \( \displaystyle {n} \) e proviamola per \( \displaystyle {n}+{1} \).
Dire che vale per \( \displaystyle {n} \) significa che \( \displaystyle {{2}}^{{{2}{n}}}\le{C}\cdot{{2}}^{{n}} \).
Consideriamo ora \( \displaystyle {{2}}^{{{2}{\left({n}+{1}\right)}}} \) e operiamo nel seguente modo:
\( \displaystyle {{2}}^{{{2}{\left({n}+{1}\right)}}}={{2}}^{{{2}{n}+{2}}}={{2}}^{{{2}{n}}}\cdot{4} \) e utilizzando l'ipotesi induttiva, \( \displaystyle \le{C}\cdot{{2}}^{{{n}}}\cdot{4}={2}{C}\cdot{{2}}^{{{n}+{1}}}={\overline{{C}}}\cdot{{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

[hamming_burst]

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 \( \displaystyle \le{c}\cdot{\left({{2}}^{{n}}\right)}\cdot{4} \) fin qua OK adesso \( \displaystyle ={2}\cdot{c}\cdot{{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

[Relegal]

Il passaggio è solo di algebra: scrivo \( \displaystyle {4}={{2}}^{{2}} \). a quel punto osservo che \( \displaystyle {{2}}^{{n}}\cdot{2}={{2}}^{{{n}+{1}}} \). Mi resta fuori un 2 che "inglobo" nella C.

[hamming_burst]

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

[Relegal]

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 \( \displaystyle {n}\ge{1} \), \( \displaystyle {{2}}^{{{3}{n}-{1}}}+{3} \) è divisibile per 7.
Si dimostri per induzione che per ogni intero \( \displaystyle {n}\ge{3} \), \( \displaystyle {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 !

[Gi8]

Si dimostri per induzione che per ogni intero \( \displaystyle {n}\ge{1} \), \( \displaystyle {{2}}^{{{3}{n}-{1}}} \) è divisibile per 7.

Penso che tu intenda \( \displaystyle {{2}}^{{{3}{n}}}-{1} \)

[Relegal]

Si dimostri per induzione che per ogni intero \( \displaystyle {n}\ge{1} \), \( \displaystyle {{2}}^{{{3}{n}-{1}}} \) è divisibile per 7.

Penso che tu intenda \( \displaystyle {{2}}^{{{3}{n}}}-{1} \)

No . . intendevo proprio \( \displaystyle {{2}}^{{{3}{n}-{1}}} \), il problema è che ho dimenticato un \( \displaystyle +{3} \) in fondo
Ora lo modifico. Grazie per l'osservazione !

[hamming_burst]

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.

[Relegal]

Figurati, felice di esserti stato d'aiuto. A risentirci, buon proseguimento !