Prove that sum_(k=1)^n k 2^k = (n-1)2^(n+1) + 2 ?

Oct 5, 2017

Induction Proof - Hypothesis

We seek to prove that:

$S \left(n\right) = {\sum}_{k = 1}^{n} \setminus k {2}^{k} = \left(n - 1\right) {2}^{n + 1} + 2$ ..... [A]

So let us test this assertion using Mathematical Induction:

Induction Proof - Base case:

We will show that the given result, [A], holds for $n = 1$

When $n = 1$ the given result gives:

$L H S = {\sum}_{k = 1}^{1} \setminus k {2}^{k} = 1 \cdot {2}^{1} = 2$
$R H S = \left(1 - 1\right) {2}^{1 + 1} + 2 = 2$

So the given result is true when $n = 1$.

Induction Proof - General Case

Now, Let us assume that the given result [A] is true when $n = m$, for some $m \in \mathbb{N} , m > 1$, in which case for this particular value of $m$ we have:

${\sum}_{k = 1}^{m} \setminus k {2}^{k} = \left(m - 1\right) {2}^{m + 1} + 2$ ..... [B]

Consider the LHS of [A] with the addition of the next term, in which case we have

$L H S = {\sum}_{k = 1}^{m + 1} \setminus k {2}^{k}$
$\setminus \setminus \setminus \setminus \setminus \setminus \setminus \setminus = \left\{{\sum}_{k = 1}^{m} \setminus k {2}^{k}\right\} + \left\{\left(m + 1\right) {2}^{m + 1}\right\}$
$\setminus \setminus \setminus \setminus \setminus \setminus \setminus \setminus = \left(m - 1\right) {2}^{m + 1} + 2 + \left(m + 1\right) {2}^{m + 1} \setminus \setminus \setminus$ using [B]
$\setminus \setminus \setminus \setminus \setminus \setminus \setminus \setminus = \left\{\left(m - 1\right) + \left(m + 1\right)\right\} {2}^{m + 1} + 2$
$\setminus \setminus \setminus \setminus \setminus \setminus \setminus \setminus = \left(2 m\right) {2}^{m + 1} + 2$
$\setminus \setminus \setminus \setminus \setminus \setminus \setminus \setminus = m {2}^{m + 2} + 2$
$\setminus \setminus \setminus \setminus \setminus \setminus \setminus \setminus = \left(\left(m - 1\right) + 1\right) {2}^{\left(m + 1\right) + 1} + 2$

Which is the given result [A] with $n = m + 1$

Induction Proof - Summary

So, we have shown that if the given result [A] is true for $n = m$, then it is also true for $n = m + 1$ where $m > 1$. But we initially showed that the given result was true for $n = 1$ so it must also be true for $n = 2 , n = 3 , n = 4 , \ldots$ and so on.

Induction Proof - Conclusion

Then, by the process of mathematical induction the given result [A] is true for $n \in \mathbb{N}$

Hence we have:

${\sum}_{k = 1}^{n} \setminus k {2}^{k} = \left(n - 1\right) {2}^{n + 1} + 2$ QED

Oct 5, 2017

See below.

Explanation:

Considering ${\sum}_{k = 0}^{n} {x}^{k} = \frac{{x}^{n + 1} - 1}{x - 1}$ and

$\frac{d}{\mathrm{dx}} {\sum}_{k = 0}^{n} {x}^{k} = {\sum}_{k = 0}^{n} k {x}^{k - 1}$ we have

${\sum}_{k = 1}^{n} k {x}^{k} = x {\sum}_{k = 0}^{n} k {x}^{k - 1} = {\sum}_{k = 0}^{n} k {x}^{k} = {\sum}_{k = 1}^{n} k {x}^{k}$

so

${\sum}_{k = 1}^{n} k {x}^{k} = x \frac{d}{\mathrm{dx}} \left(\frac{{x}^{n + 1} - 1}{x - 1}\right) = \frac{x + \left(n \left(x - 1\right) - 1\right) {x}^{1 + n}}{x - 1} ^ 2$

Making now $x = 2$ we have

${\sum}_{k = 1}^{n} k {2}^{k} = \left(n - 1\right) {2}^{n + 1} + 2$

Oct 5, 2017

Pease refer to a Proof in the Explanation.

Explanation:

Let, $S \left(n\right) = {\sum}_{k = 1}^{k = n} k {2}^{k} .$

$\therefore S \left(n\right) = 1 \cdot {2}^{1} + 2 \cdot {2}^{2} + 3 \cdot {2}^{3} + \ldots + \left(n - 1\right) {2}^{n - 1} + n \cdot {2}^{n} .$

$\therefore 2 S \left(n\right) = 1 \cdot {2}^{2} + 2 \cdot {2}^{3} + 3 \cdot {2}^{4} + \ldots + \left(n - 1\right) {2}^{n} + n \cdot {2}^{n + 1} .$

$\therefore S \left(n\right) - 2 S \left(n\right) = 1 \cdot {2}^{1} + \left(2 - 1\right) {2}^{2} + \left(3 - 2\right) {2}^{3} + \ldots + \left(n - \underline{n - 1}\right) {2}^{n} - n \cdot {2}^{n + 1} .$

$\therefore - S \left(n\right) = \left\{{2}^{1} + {2}^{2} + {2}^{3} + \ldots + {2}^{n}\right\} - n \cdot {2}^{n + 1} .$

We see that, the Series in $\left\{\ldots\right\}$ is a GP, having ${1}^{s t}$ term

$a = 2 = r = \text{common ratio,}$ so that, the sum of its $n$ terms is,

$\frac{a \left({r}^{n} - 1\right)}{r - 1} = \frac{2 \left({2}^{n} - 1\right)}{2 - 1} = 2 \left({2}^{n} - 1\right) .$

$\therefore - S \left(n\right) = 2 \left({2}^{n} - 1\right) - n \cdot {2}^{n + 1} .$

$\therefore S \left(n\right) = n \cdot {2}^{n + 1} - 2 \left({2}^{n} - 1\right) = n \cdot {2}^{n + 1} - {2}^{n + 1} + 2.$

$\Rightarrow {\sum}_{k = 1}^{k = n} k {2}^{k} = \left(n - 1\right) {2}^{n = 1} + 2.$

Enjoy Maths.!