Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicate:
How do I prove this by induction? (sum of powers of 2)
Summation equation for $2^{x-1}$

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.

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

up vote 2 down vote accepted

When $n=1$, we see


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$$



share|cite|improve this answer
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?

share|cite|improve this answer

(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.

share|cite|improve this answer
Sometimes you might want to lop off a couple of terms.... – ncmathsadist Oct 8 '12 at 23:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.