Originally Posted by

**HABMD** The question is:

Prove by induction for all positive integers n:

1 + 2(2) + 3(2^2) + 4(2^) + ... n(2^(n-1)) = (n-1)(2^n) + 1

I'm stuck on this and it's bothering me! Here are my workings so far:

1. Show proposition is true for n=1

LHS: P(1) = 1(2^(1-1)) = 1

RHS: P(1) = (1-1)(2^1) + 1 = 1

1=1

=> P(1) is true

2. Assume that P(k) is true

1 + 2(2) + 3(2^2) + ... k(2^(k-1) = (k-1)(2^k) + 1

3. Prove P(k+1) is true, given P(k) is true

To prove: 1 + 2(2) + 3(2^2) + ... k(2^(k-1)) + (k+1)(2^((k+1)-1) = (k)(2^(k+1)) + 1

Proof:

1 + 2(2) + 3(2^2) + ... k(2^(k-1) = (k-1)(2^k) + 1 (Assumption)

Add new term:

1 + 2(2) + ... k(2^(k-1)) + (k+1)(2^k) = (k-1)(2^k)+1 + (k+1)(2^k)

(This is where it got a bit messy ...)

= (4^k)(k) +1 ???????

Could anyone please tell me where I have gone wrong?