Dimostrazione per induzione n --> 2^n

[WhiteOrphen]

Seguo il corso di informatica perciò la docente di Algebra ha assegnato questo esercizio che non so svolgere :S Mi potreste aiutare?

Dimostrazione per induzione che con n bit ci sono 2^n combinazione
Esempio:
2 bit ci sono 4 (2^2) combinazioni (00 - 01 - 10 - 11)
3 bit ci sono 8 (2^3) combinazioni (000 - 001 - 010 - 011 - 100 - 101 - 110 - 111)

Come posso fare? Vi ringrazio vi prego aiutatemi!

[vict85]

Te lo ha detto la professoressa: usa l'induzione. Insomma prendi lo schema base e verifica i vari punti.

[kobeilprofeta]

Ciao. Sai come si fa una dim per induzione?

[WhiteOrphen]

basta semplicemente dire che vale per n..poi per n+1 e basta? Non puoi farmelo vedere un secondo? Mi sembra che non si ferma lì la dimostrazione..grazie e buona domenica delle palme

[vict85]

[xdom="vict85"]Il [regolamento]1_3[/regolamento] è piuttosto chiaro sul fatto che devi mostrare tentativi da parte tua.[/xdom]

La dimostrazione per induzione è fatta di \(3\) passaggi:
1) Verifichi che per \(\displaystyle n=1 \) si hanno \(2=2^1\) casi distinti.
2) Supponi per induzione che si abbiano \(\displaystyle 2^N \) casi per \(\displaystyle n=N \).
3) Dimostri il caso \(\displaystyle n=N+1 \) condizionalmente al punto \(\displaystyle 2 \), ovvero mostri che aggiungendo un bit raddoppi il numero totale di casi.

[WhiteOrphen]

grazie mille..chiedo scusa per non aver seguito il ragionamento

[kobeilprofeta]

Dai. Allora ci sei riuscito o ti blocchi ancora?