Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

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.

3 Answers

up vote 2 down vote accepted

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

share|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
add comment

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|improve this answer
add comment

(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|improve this answer
    
Sometimes you might want to lop off a couple of terms.... –  ncmathsadist Oct 8 '12 at 23:51
add comment

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