# summation question

• May 24th 2007, 06:57 AM
margaritas
summation question
Hey guys I can't solve the second part of this following question, i.e. 'hence, ...' onwards.

Prove by induction that, for all positive integers n, [(end value=n) (summation notation, sigma) (starting value: r=1)] (r+1)2^r = n[2^(n+1)].

Hence, deduce that [(end value=2n) (summation notation, sigma) (starting value: r=n+1)] [(r+1)2^r + 2^(n+1)] = n[2^(2n+2)].

Sorry it's so messy but I don't have the programs for 'typing math'. Thanks in advance if anybody could help! :)
• May 24th 2007, 07:43 AM
CaptainBlack
Quote:

Originally Posted by margaritas
Hey guys I can't solve the second part of this following question, i.e. 'hence, ...' onwards.

Prove by induction that, for all positive integers n, [(end value=n) (summation notation, sigma) (starting value: r=1)] (r+1)2^r = n[2^(n+1)].

Hence, deduce that [(end value=2n) (summation notation, sigma) (starting value: r=n+1)] [(r+1)2^r + 2^(n+1)] = n[2^(2n+2)].

Sorry it's so messy but I don't have the programs for 'typing math'. Thanks in advance if anybody could help! :)

You have:

$
\sum_1^{n} (r+1)2^r = n[2^{n+1}] \ \ \ \ ...(1)
$

Then:

$
\sum_1^{2n} (r+1)2^r - \sum_1^{n-1} (r+1)2^r =
\sum_{n}^{2n} (r+1)2^r
$

So just use (1) to replace the two sums on the left hand side with their
respective totals to get the result.

RonL
• May 24th 2007, 11:11 PM
margaritas
Thanks but I still don't get it!
• May 25th 2007, 10:34 AM
CaptainBlack
Quote:

Originally Posted by CaptainBlack
You have:

$
\sum_1^{n} (r+1)2^r = n[2^{n+1}] \ \ \ \ ...(1)
$

Then:

$
\sum_1^{2n} (r+1)2^r - \sum_1^{n-1} (r+1)2^r =
\sum_{n}^{2n} (r+1)2^r
$

So just use (1) to replace the two sums on the left hand side with their
respective totals to get the result.

RonL

Quote:

Originally Posted by margaritas
Thanks but I still don't get it!

You split the sum from 1 to 2n into two parts one from 1 to n-1 and the
other fron n to 2n. The formula you already have:

$
\sum_1^{n} (r+1)2^r = n[2^{n+1}] \ \ \ \ ...(1)
$

tells you that:

$
\sum_1^{2n} (r+1)2^r = 2n[2^{2n+1}]
$

and that:

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

So:

$
\sum_{n}^{2n} (r+1)2^r = \sum_1^{2n} (r+1)2^r - \sum_1^{n-1} (r+1)2^r = 2n[2^{2n+1}] - (n-1) 2^{n}
$

RonL
• May 25th 2007, 10:38 AM
Soroban
Hello, margaritas!

I've got the first part . . .

Quote:

Prove by induction that, for all positive integers n:
. . $\sum_{r = 1}^n (r+1)\cdot2^r \:= \:n\cdot2^{n+1}$

Verify that $S(1)$ is true.
. . $S(1) \:=\:(1 + 1)\cdot2^1 \:=\:1\cdot2^2\quad\Rightarrow\quad 4 = 4$ . . . true!

Assume that $S(k)$ is true:
. . $\sum_{r=1}^k(r + 1)\cdot2^r \:=\:k\cdot2^{k+1}$

Add $(k+2)\cdot2^{k+1}$ to both sides:
. . $\sum_{r=1}^k(r+1)\cdot2^r + (k+2)\cdot2^{k+1} \;=\;k\cdot2^{k+1} + (k+2)\cdot2^{k+1}$

The left side is: . $\sum^{k+1}_{r=1} (r+1)\cdot2^r$ . . . the left side of $S(k+1).$

The right side is: . $\underbrace{k\cdot2^{k+1} + k\cdot2^{k+1}} +\,2^{k+2}$
. . . . . . . . . . . . . . $= \;2k\cdot2^{k+1} + 2^{k+2}$

. . . . . . . . . . . . . . $= \;k\cdot2^{k+2} + 2^{k+2}$

. . . . . . . . . . . . . . $= \;(k+1)\cdot2^{k+2}$ . . . the right side of $S(k+1)$

The inductive proof is complete.