Respuesta :

LammettHash
First show the statement holds for the base case (presumably [tex]n=1[/tex]):

[tex]\displaystyle\sum_{i=1}^1 2^{i-1}=2^{1-1}=2^0=1[/tex]

Meanwhile, the right hand side evaluates to [tex]2^1-1=2-1=1[/tex], so the base case holds.

Now assume the formula holds for [tex]n=k[/tex]; that is,

[tex]\displaystyle\sum_{i=1}^k 2^{i-1}=2^0+2^1+\cdots+2^{k-1}=2^k-1[/tex]

and use this hypothesis to show that the formula holds for [tex]n=k+1[/tex]. You have

[tex]\displaystyle\sum_{i=1}^{k+1}2^{i-1}=2^k+\sum_{i=1}^k 2^{i-1}=2^k+2^k-1=2\times2^k-1=2^{k+1}-1[/tex]

so the formula holds and the proof is complete.

Otras preguntas