# Prove the following identity: 1−2·2+3·4−4·8+· · ·±n·2n−1 = (1−(−2)n(3n+1))/9.?

1−2·2+3·4−4·8+· · ·±n·2n−1 = (1−(−2)n(3n+1))/9.

Relevance
• Anonymous

Sum [k=1..n] k*(-2)^(k-1) = (1-(-2)^n*(3n+1))/9

First we try it for a few numbers "to get a feeling for the sequence":

n=1:

1 = 1

(1-(-2)^1(3*1+1))/9 = (1+2*4)/9 = 1

n=2:

1-2*2 = 1-4 = -3

(1-(-2)^2(3*2+1))/9 = (1-4*7)/9 = -27/9 = -3

n=3:

1-*2*2+3*4 = 1-4+12 = -3+12 = 9

(1-(-2)^3(3*3+1))/9 = (1+8*10)/9 = 81/9 = 9

n=4:

1-*2*2+3*4-4*8 = 1-4+12-32 = 9-32 = -23

(1-(-2)^4(3*4+1))/9 = (1-16*13)/9 = -207/9 = -23

n=5:

1-*2*2+3*4-4*8+5*16 = 1-4+12-32+80 = -23+80 = 57

(1-(-2)^5(3*5+1))/9 = (1+32*16)/9 = 513/9 = 57

Works!! The proof is probably by induction .. . So we try it!

Induction starts are all the above! (usually one starts from n=1, but if you prove something manually for n = 1 and 2 and 3, you can then also say that your start is at n = 3).

Induction hypothesis: The formula is true for some n.

Now we try it for n+1:

Sum [k=1..n+1] k*(-2)^(k-1) =

...we split of the sum for 1..n, because we know its formula from the hypothesis!

Sum [k=1..n] k*(-2)^(k-1) + (n+1)*(-2)^n

We must now show that this is equal to the formula when one replaces n with n + 1. I do this by writing this as a "question" as follows:

Sum [k=1..n] k*(-2)^(k-1) + (n+1)*(-2)^n =? (1-(-2)^(n+1)*(3(n+1)+1))/9

Note the =? sign: We do not yet know this - but if it turns out to be true, we are done (my mathematics teacher allowed this sort of proof - it is helpful, as you always see where you have to go).

Ok - we replace the left sum with the formula from the hypothesis:

(1-(-2)^n*(3n+1))/9 + (n+1)*(-2)^n =? (1-(-2)^(n+1)*(3(n+1)+1))/9 ... *9

(1-(-2)^n*(3n+1)) + 9*(n+1)*(-2)^n =? (1-(-2)^(n+1)*(3(n+1)+1)) ... -1

-(-2)^n*(3n+1) + 9*(n+1)*(-2)^n =? (-2)^(n+1)*(3(n+1)+1) ... rewrite (-2)^(n+1)

-(-2)^n*(3n+1) + 9*(n+1)*(-2)^n =? (-2)^n*(-2)*(3(n+1)+1) ... /(-2)^n

-(3n+1) + 9*(n+1) =? (-2)*(3(n+1)+1) ... Expand all

-3n - 1 + 9n + 9 =? (-2)*(3n + 3 + 1) ...

6n + 8 =? -6n - 8

... oops, I made some sign error somewhere above: If this is corrected, then we can write

6n + 8 =! 6n + 8

now with an exclamation mark: This is always correct, and as we only did equivalent rewrites of the formulas, also the first line with =? is then correct, and hence we have proven the formula by induction fully.

I'll leave it at that ... it's your job to find that error (preferably by redoing the computations without the error :-) ).

Hope that helps!