Esercizio (Appello 11 Febbraio 2016)

Si dimostri per induzione su n la seguente disuguaglianza:

โˆ‘k=1nk2k=2โˆ’n+22nย ย ย โˆ€nโ‰ฅ1

Soluzione in forma compatta

Procediamo per induzione su nโ‰ฅ1
n=1 (BASE DELL'INDUZIONE)
Dobbiamo provare che

โˆ‘k=1nk2k=2โˆ’1+221

Vale:

La base dell'induzione รจ verificata, in quanto โˆ‘k=11k2k=12=2โˆ’1+22

nโ‰ฅ1,ย nโŸนn+1 (PASSO INDUTTIVO)
Assumiamo che l'uguaglianza sia vera per un certo nโ‰ฅ1, cioรจ che valga

โˆ‘k=1nk2k=2โˆ’n+22nย per qualcheย nโ‰ฅ1ย (IPOTESI INDUTTIVA)

Dobbiamo provare che vale la stessa uguaglianza con n+1 al posto di n, ovvero

โˆ‘k=1n+1k2k=2โˆ’(n+1)+22n+1ย (TESI DEL PASSO INDUTTIVO)
Metodo 1

Vale:

โˆ‘k=1n+1k2k=(โˆ‘k=1nk2k)+n+12n+1=(2โˆ’n+22n)+n+12n+1โ€•=

(...): Ipotesi induttiva

=2โˆ’(n+22nโˆ’n+12nร—21)=(raccolto il meno)=2โˆ’2(n+2)ย โˆ’ย (n+1)2nร—2=(denominatore comune)=2โˆ’2n+4โˆ’nโˆ’12n+1==2โˆ’n+32n+1==2โˆ’(n+1)+22n+1=

Dunque il passo induttivo รจ verificato.
Grazie al passo induttivo P(n) รจ vera โˆ€n>=1

Metodo 2

Vale:

โˆ‘k=1n+1k2k=2โˆ’(n+1)+22n+1(โˆ‘k=1nk2k)+n+12n+1=2โˆ’(n+1)+22n+1โ‡•ย (ipotesi induttiva)(2โˆ’n+22n)+n+12n+1=2โˆ’(n+1)+22n+1โˆ’n+22n+n+12n+1=โˆ’ย (n+1)+22n+1โ‡•ย ย Moltiplico a destra e a sinistra perย โˆ’1n+22nโˆ’n+12n+1=(n+1)+22n+1โ‡•ย ย Moltiplico a destra e a sinistra perย 2n+12(n+2)โˆ’nโˆ’1=n+3n+3=n+3

Dunque il passo induttivo รจ verificato.
Grazie al passo induttivo P(n) รจ vera โˆ€nโ‰ฅ1