0
$\begingroup$

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.

3 Answers 3

2

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

  • 0
    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}$?2012-10-08
  • 0
    @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}.$$2012-10-08
  • 0
    @Limitless That makes sense, thanks.2012-10-08
  • 0
    @mirai, You're welcome!2012-10-08
2

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?

0

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

  • 0
    Sometimes you might want to lop off a couple of terms....2012-10-08