Proving by induction $2^k - 1 = 1+\cdots +2^{k-1}$

Question

How can I show:

$$2^k - 1 + 2^{(k+1)-1} = 2^{k+1} - 1$$

I am trying to prove this by induction:

$$2^k - 1 = 1+\cdots +2^{k-1}$$

and proved the base case:

$2^2-1 = 1+2^1$ as $2^2-1=3$ and $1+2^1=3$

Then I've got this far and gotten stuck . . .

Assume true for $k$

$$2^k -1=1+\cdots+2^{k-1}$$

let $n=k+1$

$$2^{k+1} -1=1+\cdots+2^{(k+1)-1}$$

Therefore

$$2^{k+1} -1=[1+\cdots+2^{k-1}]+2^{(k+1)-1}$$

$$2^{k+1} -1=[2^{k-1}-1]+2^{(k+1)-1}$$

Then I have to get to the last step:

$$2^{k+1} -1=2^{k+1} -1$$

but I don't know how to turn:

$[2^{k-1}-1]+2^{(k+1)-1}$ into $2^{k+1} -1$ though I do know it's true.

Please comment below for any further clarification.

Answer 1

You assumed that: $$1+2+\cdots+2^{k-1}=2^k-1\tag{IH}$$ and you want to prove that $$\underbrace{1+2+\cdots+2^{k-1}}_{=2^k-1 \text{ (HI) }}+2^{k}=2^{k+1}-1$$

so what you actually need to prove is : $$2^k-1+2^k=2^{k+1}-1$$ which follows from the identity $2^k+2^k=2\cdot 2^k=2^{k+1}$

Answer 2

Now that Elaqqad answered your question , here is another approach:

How about using : $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+..+a^{n-k}b^{k-1}+..+b^k)$?

You have $a=2, b=1, n=k+1$. Then $$ 2^{k-1}-1=(2-1)(2^{k-1}+2^{k-2}1+..+1^k=2^{k-1}+2^{k-2}+...+2+1) $$.