Mathematical induction proof problem

Question

How to prove with mathematical induction that

$$\sum _{k=1}^{n}\frac{2k-1}{2^k}=3-\frac{2n+3}{2^n}$$

if $n \in \mathbb N$?

Answer 1

We first show that for $n = 1$ (start of induction): We have $$ \sum _{k=1}^{n}\frac{2k-1}{{2^k}} = \frac{2-1}{2} = \frac 1 2 = 3-\frac{2+3}{{2}} =3-\frac{2n+3}{{2^n}}.$$ Now we assume that $$\sum _{k=1}^{n}\frac{2k-1}{{2^k}}=3-\frac{2n+3}{{2^n}}$$ holds for an $n \in \mathbb N$. We have to show that it also holds for $n+1$ then (induction step). We get that \begin{align*} \sum _{k=1}^{n+1}\frac{2k-1}{{2^k}} &= \frac{2(n+1)-1}{{2^{n+1}}} + \sum _{k=1}^{n}\frac{2k-1}{{2^k}} \\ &= \frac{2(n+1)-1}{{2^{n+1}}} + 3-\frac{2n+3}{{2^n}} \\ &= \frac{2(n+1)-1}{{2^{n+1}}} + 3-\frac{4n+6}{{2^{n+1}}} \\ &= 3 + \frac{2(n+1)-1 -(4n+6)}{{2^{n+1}}} \\ &= 3 + \frac{-2n -5}{{2^{n+1}}} \\ &= 3 - \frac{2n +5}{{2^{n+1}}} \\ &= 3-\frac{2(n+1)+3}{{2^{n+1}}}. \end{align*} Thus we get the statement by using induction. I hope it helps you :)

Answer 2

Hint: The basic steps are the same for any inductive proof.

First, show the statement is true when $n=1$.

Then, assuming it is true for the case $n=N$, show it must then be true for the case $n=N+1$. In this case, you probably want to notice that $\sum_1^{N+1} = \sum_1^N + \; (\textrm{term for }N+1)$, and use your assumption to replace $\sum_1^N$ with what the formula says it is.

Answer 3

Nice thing about summation proves by inductions:

Proving $\sum_{k=1}^n a_i = G_n$

boils down to proving

A) $a_1 = \sum_{k=1}^1 a_i = G_1$

and

B) $G_{n+1} = \sum_{k=0}^{n+1} a_i = \sum_{k=1}^n a_i + a_{n+1} = G_n + a_i$.

So proving $\sum _{k=1}^{n\:}\frac{2k-1}{^{2^k}}\:=\:3\:-\:\frac{2n\:+\:3}{^{2^n}}$

Is a matter of proving:

A)$a_1 = G_1$ i.e.

$\frac {2(1)-1}{2^1} = 3 - \frac{2(1) +3}{2^1} \iff$

$\frac 12 = 3 - \frac 52$ which it is.

and B) $G_{n+1} = G_n + a_{n+1}$ i.e.

$3-\frac{2(n+1)+3}{2^{n+1}} = 3-\frac{2n+3}{2^{n}}+\frac{2(n+1) -1}{2^{n+1}}$

which is straightforward

$3-\frac{2(n+1)+3}{2^{n+1}} = 3-\frac{2n+3}{2^{n}}+\frac{2(n+1) -1}{2^{n+1}} \iff$

$3 -\frac{2n + 5}{2^{n+1}} = 3 -\frac{(2n+3)2}{2^{n+1}} + \frac{2n + 1}{2^{n+1}}\iff$

$\frac{2n + 5}{2^{n+1}} = \frac{(4n+6)-(2n + 1)}{2^{n+1}}\iff$

$\frac{2n + 5}{2^{n+1}}=\frac{2n + 5}{2^{n+1}}$.

That's it. We're done.