# Proving $\sum\limits_{i=0}^n i 2^{i-1} = (n+1) 2^n - 1$ by induction

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?

-

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

## 2 Answers

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.

-

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.

-

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. – Gone Nov 30 '11 at 19:10
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 6, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9408401846885681, "perplexity_flag": "middle"}