Originally Posted by
o_O $\displaystyle P(n) : \sum_{j = 1}^{n} 2^{j-1} = 2^{n} - 1$
Prove that P(1) is true:
$\displaystyle \sum_{j = 1}^{1} 2^{0} = 1$
$\displaystyle 2^{1} - 1 = 1$
Now assume P(k) is true. We must show that this implies
$\displaystyle P(k+1): \sum_{j = 1}^{k+1} 2^{j-1} = 2^{k+1} - 1$
So, we have that:
$\displaystyle P(k+1): \sum_{j = 1}^{{\color{red}k+1}}2^{j-1} = \underbrace{\sum_{j=1}^{k}2^{j-1}}_{P(k)} + {\color{red} \: 2^{(k+1)-1}} = \underbrace{\left(2^{k} - 1\right)}_{P(k)} + 2^{k}$
Can you go on from that?