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