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.

I'm trying to apply an induction proof to show that $((n+1) 2^n - 1 $ is the sum of $(i 2^{i-1})$ from $0$ to $n$.

  • the base case: L.H.S = R.H.S
  • we assume that $(k+1) 2^k - 1 $ is true.
  • we need to prove that $(k+2) 2^{k+1} - 1$

My try to prove 3 is as follows:

$(k+2) 2^{k+1} - 1$

$(k+2) (2^k * 2) - 1$ , from 2: $2^k = 1/(k+1)$

$(k+2) (2 / (k+1)) - 1$

$(k+1) 2 - 1$

My question is, how could I get to $2^k$ from the last line to prove this formula is right?

share|improve this question
    
I don't think you have the right formula. It does not hold for $n=1$. –  David Mitra Nov 30 '11 at 11:45
    
Two similar questions: math.stackexchange.com/questions/53496/… and math.stackexchange.com/questions/11464/… (But I do not think that this should be closed as duplicate - since OP is asking about mistake in his approach and he is interested only in the proof by induction. I just wanted to point him to similar question.) –  Martin Sleziak Nov 30 '11 at 12:02
add comment

2 Answers 2

up vote 3 down vote accepted

You have a typo in your statement. You want to show $$ \sum_{i=0}^n i 2^{i-1} = n 2^n - 2^n + 1 $$

Base case $n = 0$:

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

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

Then make an induction step from $n$ to $n+1$. This means you want to show that given your assumption you can show

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

Do this as follows:

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

Which is what you wanted to show. Hope this helps.

share|improve this answer
2  
Is this right? $(n+1)2^n+(n+1 )2^n-1 = 2(n+1)2^n-1=(n+1)2^{n+1}-1$... The OP's formula does not hold for $n=1$. –  David Mitra Nov 30 '11 at 11:43
    
Darn, you're right! –  Matt N. Nov 30 '11 at 11:44
    
@DavidMitra: Let's assume it's a typo. Let's see whether I can fix this. –  Matt N. Nov 30 '11 at 11:45
    
@DavidMitra: Thanks, David. Fixed. –  Matt N. Nov 30 '11 at 11:57
    
Thanks! very clear.. –  Sosy Nov 30 '11 at 18:25
show 1 more comment

HINT $\ $ The RHS should be $\rm\:(n-1)\ 2^n + 1\:.\:$ As always, by telescopy, the inductive step arises from equating the first difference of the LHS and RHS. Here that yields the trivially proved identity

$$\rm (n+1)\ 2^n\ =\ n\ 2^{n+1} - (n-1)\ 2^n $$

which, combined with the trivial proof of the base case $\rm\:n=0\:,\:$ completes the proof by induction.

REMARK $\ $ Note that absolutely no ingenuity is required. The proof by telescopy is so mechanical that it can be done by a machine. Indeed, cancelling the factor of $\rm\:2^n\:,\:$ said inductive step reduces to proving the polynomial identity $\rm\ n+1\ =\ 2\:n - (n-1)\:.\:$ For much further discussion see my many posts on telescopy.

share|improve this answer
    
sounds very helpful, but hmmm what is the first difference of the LHS and RHS? at what value (k or k+1)? –  Sosy Nov 30 '11 at 18:05
    
@Sosy The first difference of $\rm\:f(n)\:$ wrt $\rm\:n\:$ is $\rm\:\Delta_n f(n) := f(n+1) - f(n)\:.\:$ The displayed equation above is $\rm\: \Delta\: LHS(n) = \Delta\: RHS(n)\:.\:$ This method works to mechanically "discover" the induction step on all problems of this type. See the linked posts on telescopy for background. –  Bill Dubuque Nov 30 '11 at 19:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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