# Prove by Mathematical Induction? :  1 + 2(1/2) + 3(1/2)^2 + 4(1/2)^3 + ...+ n(1/2)^(n-1) = 4 - ((n+2)/2^(n-1))

Aug 22, 2017

We seek to prove that:

$1 + 2 \left(\frac{1}{2}\right) + 3 {\left(\frac{1}{2}\right)}^{2} + 4 {\left(\frac{1}{2}\right)}^{3} + \ldots + n {\left(\frac{1}{2}\right)}^{n - 1} = 4 - \left(\frac{n + 2}{2} ^ \left(n - 1\right)\right)$

Or, alternatively, using Sigma Notation:

${\sum}_{r = 0}^{n} r {\left(\frac{1}{2}\right)}^{r - 1} = 4 - \left(\frac{n + 2}{2} ^ \left(n - 1\right)\right)$

So let us test this assertion using Mathematical Induction:

Induction Proof - Hypothesis

We aim to prove by Mathematical Induction that for $n \in \mathbb{N}$ that:

${\sum}_{r = 0}^{n} r {\left(\frac{1}{2}\right)}^{r - 1} = 4 - \left(\frac{n + 2}{2} ^ \left(n - 1\right)\right)$ ..... [A]

Induction Proof - Base case:

We will show that the given result, [A], holds for and $n = 1$ (and actually for $n = 0$)

When $n = 0$ the given result gives:

$L H S = 0$
$R H S = 4 - \left(\frac{2}{2} ^ \left(- 1\right)\right) = 0$

When $n = 1$ the given result gives:

$L H S = 1$
$R H S = 4 - \left(\frac{3}{2} ^ \left(0\right)\right) = 1$

So the given result is true when $n = 1$ (and in fact $n = 0$)

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}_{r = 0}^{m} r {\left(\frac{1}{2}\right)}^{r - 1} = 4 - \left(\frac{m + 2}{2} ^ \left(m - 1\right)\right)$ ..... [B]

So, let us add the next term to the series, so that we have:

${\sum}_{r = 0}^{m + 1} r {\left(\frac{1}{2}\right)}^{r - 1} = \left({\sum}_{r = 0}^{m} r {\left(\frac{1}{2}\right)}^{r - 1}\right) + \left(m + 1\right) {\left(\frac{1}{2}\right)}^{m}$

Then using [B] we have:

${\sum}_{r = 0}^{m + 1} r {\left(\frac{1}{2}\right)}^{r - 1} = 4 - \left(\frac{m + 2}{2} ^ \left(m - 1\right)\right) + \left(m + 1\right) {\left(\frac{1}{2}\right)}^{m}$
$\text{ } = 4 - \left(\frac{m + 2}{2} ^ \left(m - 1\right)\right) \cdot \frac{2}{2} + \frac{m + 1}{{2}^{m}}$
$\text{ } = 4 - \frac{2 \left(m + 2\right)}{{2}^{m}} + \frac{m + 1}{{2}^{m}}$
$\text{ } = 4 - \frac{2 \left(m + 2\right) - \left(m + 1\right)}{{2}^{m}}$
$\text{ } = 4 - \frac{2 m + 4 - m - 1}{{2}^{m}}$
$\text{ } = 4 - \frac{m + 3}{{2}^{m}}$
$\text{ } = 4 - \frac{\left(m + 1\right) + 2}{{2}^{m + 1} - 1}$

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$. But we initially showed that the given result was true for $n = 0$ and $n = 1$ so it must also be true for $n = 2 , n = 3 , n = 4 , \ldots$ and so on.

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

Hence we have:

${\sum}_{r = 0}^{n} r {\left(\frac{1}{2}\right)}^{r - 1} = 4 - \left(\frac{n + 2}{2} ^ \left(n - 1\right)\right)$

Aug 25, 2017

An Alternative Proof, without using the Induction is given in

the Explanation.

#### Explanation:

Respected Steve M. Sir has solved, as is required, the

Problem using the Principle of Mathematical Induction.

Let us, as an Aliter, prove it without it.

Let, $\left(1\right) \ldots {S}_{n} = 1 + 2 \left(\frac{1}{2}\right) + 3 {\left(\frac{1}{2}\right)}^{2} + 4 {\left(\frac{1}{2}\right)}^{3} + \ldots + \left(n - 1\right) {\left(\frac{1}{2}\right)}^{n - 2} + n {\left(\frac{1}{2}\right)}^{n - 1} .$

Multiplying both sides by, $\frac{1}{2} ,$ we get,

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

Then, $\left(1\right) - \left(2\right) \Rightarrow {S}_{n} - \frac{1}{2} \cdot {S}_{n} = 1 + \left(2 - 1\right) \left(\frac{1}{2}\right) + \left(3 - 2\right) {\left(\frac{1}{2}\right)}^{2} + \left(4 - 3\right) {\left(\frac{1}{2}\right)}^{3} + \ldots + \left(n - \left(n - 1\right)\right) {\left(\frac{1}{2}\right)}^{n - 1} - n {\left(\frac{1}{2}\right)}^{n} ,$

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

We easily recognise that the Series in $\left\{\ldots \ldots\right\}$ is Geometric,

having, (n-1)" terms, the first term, "a=1/2="the common ratio "r;

hence, its sum=$\frac{a \left(1 - {r}^{n - 1}\right)}{1 - r}$

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

$\therefore \frac{1}{2} \cdot {S}_{n} = 1 + \left\{1 - {\left(\frac{1}{2}\right)}^{n - 1}\right\} - n {\left(\frac{1}{2}\right)}^{n} , i . e . ,$

$= 2 - \left(1 + \frac{1}{2} \cdot n\right) {\left(\frac{1}{2}\right)}^{n - 1} , \mathmr{and} ,$

$\Rightarrow \frac{1}{2} \cdot {S}_{n} = 2 - \frac{1}{2} \cdot \left(\frac{n + 2}{2} ^ \left(n - 1\right)\right) , \text{ giving, }$

${S}_{n} = 4 - \left(\frac{n + 2}{2} ^ \left(n - 1\right)\right) ,$ as desired.

Enjoy Maths.!