# How to prove by induction that $\sum^n_{i=1}2^{i-1}=2^n-1$? [duplicate]

How can I prove the following by induction? $$\sum^n_{i=1}2^{i-1}=2^n-1$$ I get to $$\ldots+2^{i-1}=2^n-1+2^{i-1}$$ and don't see what the next step is.

-

## marked as duplicate by Dilip Sarwate, Marvis, Gerry Myerson, Thomas, Ross MillikanOct 9 '12 at 0:15

When $n=1$, we see

$$2-1=2^0$$

so LHS=RHS. Assuming that

$$\sum_{i=1}^n 2^{i-1}=2^n-1$$

we have, changing $n$ to $n+1$, the inductive step:

$$\sum_{i=1}^{n+1} 2^{i-1} = 2^n+\sum_{i=1}^{n} 2^{i-1}=2^n+2^{n}-1=2^{n+1}-1$$

so LHS=RHS.

QED

-
I'm not following you at the inductive step. Shouldn't it be $\sum^{n+1}_{i=1}2^{i-1}=2^n-1+\sum^n_{i=1}2^{i-1}$? – mirai Oct 8 '12 at 23:05
@mirai, the term $2^n$ results from evaluating the summand at $i=n+1$ and separating it from the summation notation. In other words, $2^{i-1}=2^{n+1-1}=2^{n}$. Hence, $$\sum_{i=1}^{n+1}2^{i-1}=2^n+\sum_{i=1}^{n}2^{i-1}.$$ – 000 Oct 8 '12 at 23:22
@Limitless That makes sense, thanks. – mirai Oct 8 '12 at 23:29
@mirai, You're welcome! – 000 Oct 8 '12 at 23:34

You start with the inductive hypothesis $$\sum_{i=1}^n2^{i-1} = 2^n - 1$$ for some $n$. Now for $n+1$ you have $$\sum_{i=1}^{n+1}2^{i-1} = 2^n + \sum_{i=1}^n2^{i-1}$$ Can you see how to finish it off?

-

(Warning: Puckishness ahead!) When you do induction on a sum $\sum_{k=a}^b x_k$, you either decapitate like so $$\sum_{k=a}^b x_k = x_b + \sum_{k=a}^{b-1} x_k,$$ or you exungulate (trim toenails) like so $$\sum_{k=a}^b x_k = x_a + \sum_{k=a+1}^b x_k.$$ This will convey you to the induction step neatly.

-
Sometimes you might want to lop off a couple of terms.... – ncmathsadist Oct 8 '12 at 23:51