Thread: Proof by induction (proving formula for sum of a series) ?

1. Proof by induction (proving formula for sum of a series) ?

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)
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?

2. Re: Proof by induction (proving formula for sum of a series) ?

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)
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?
You're very close,

\displaystyle \begin{align*} \sum_{ r = 0 }^{k} { \left[ \left( r + 1 \right) 2^r \right] } &= \sum_{r =0}^{k - 1}{ \left[ \left( r + 1 \right) 2^r \right] } + \left( k + 1 \right) 2^k \\ &= \left( k - 1 \right) 2^k + 1 + \left( k + 1 \right) 2^k \\ &= \left( k - 1 \right) 2^k + \left( k + 1 \right) 2^k + 1 \\ &= 2^k \left( k - 1 + k + 1 \right) + 1 \\ &= 2^k \cdot 2k + 1 \\ &= k \cdot 2^{k + 1} + 1 \end{align*}

3. Re: Proof by induction (proving formula for sum of a series) ?

Thanks a million, I think I understand now!