Proving $\sum\limits_{i=1}^{n}{\frac{i}{2^i}}=2-\frac{n+2}{2^n}$ by induction.

Question

---

Theorem (Principle of mathematical induction):

Let $G\subseteq \mathbb{N}$, suppose that

a. $1\in G$
b. if $n\in \mathbb{N}$ and $\{1,...,n\}\subseteq G$, then $n+1\in G$

Then $G=\mathbb{N}$

---

Proof by Induction

Prove that $$\sum_{i=1}^{n}{\frac{i}{2^i}}=2-\frac{n+2}{2^n},\quad \quad \forall n\in \mathbb{N} \tag{1}$$

$\color{darkred}{\mbox{Proof:}}$ let $P(n)$ be the statement $\sum_{i=1}^{n}{\frac{i}{2^i}}=2-\frac{n+2}{2^n}$

$$\sum_{i=1}^{1}{\frac{i}{2^i}}=\frac{1}{2}=2-\frac{1+2}{2^1}\tag{Basis step $P(1)$}$$ Thus $P(1)$ is true
We assume that $P(n)$ is true and prove that $P(n+1)$ is true $$\sum_{i=1}^{n+1}{\frac{i}{2^i}}\stackrel{?}{=}2-\frac{(n+1)+2}{2^{n+1}} $$

We know that $$ \begin{align*} \sum_{i=1}^{n+1}{\frac{i}{2^i}}&=\color{darkred}{\underbrace{\sum_{i=1}^{n}{\frac{i}{2^i}}}_\text{P(n) is true}}+\frac{n+1}{2^{n+1}} \tag{LHS} \\ &=\color{darkred}{2-\frac{n+2}{2^n}} + \frac{n+1}{2^{n+1}}\\ &=\frac{2^{n+1}-n-2}{2^n} + \frac{n+1}{2^{n+1}}\\ &=\frac{2\cdot 2^{n+1}-2n-4+n+1}{2^{n+1}}\\ &=\frac{2\cdot 2^{n+1}-n-3}{2^{n+1}}\tag{2}\\ \end{align*} $$

And $$ \begin{align*} 2-\frac{(n+1)+2}{2^{n+1}}&=\frac{2\cdot 2^{n+1}-n-3}{2^{n+1}} \tag{RHS} \end{align*} $$

So

$$\sum_{i=1}^{n+1}{\frac{i}{2^i}}\stackrel{}{=}2-\frac{(n+1)+2}{2^{n+1}} \tag{3}$$

Hence, if $P(n)$ is true, then $P(n+1)$ is true.
Therefore $\sum\limits_{i=1}^{n}{\frac{i}{2^i}}=2-\frac{n+2}{2^n},\quad \quad \forall n\in \mathbb{N} $ $\hspace{8cm}$ ${\Large ▫}$

---

My Question

$(i)$ does my solution make sense (is it correct?)
$(ii)$ If so, is this an correct approach to proving formulas by induction?

Can someone give me some hints/tips?

Answer 1

Your proof appears correct (though I did not check your arithmetic). An easier way is to first trivially inductively prove the Fundamental Theorem of Difference Calculus

$$\rm\ F(n)\ =\ \sum_{i\: =\: 1}^n\:\ f(i)\ \ \iff\ \ \ F(n) - F(n\!-\!1)\ =\ f(n),\quad\ F(0) = 0$$

Your special case now follows immediately by verifying that

$$\rm\ F(n)\ =\ 2 - \frac{n\!+\!2}{2^n}\ \ \Rightarrow\ \ F(n)-F(n\!-\!1)\ =\: \frac{n}{2^n}\:.\ $$

By employing the Fundamental Theorem we have reduced the proof to the trivial mechanical verification of a simple equation, which does not require any ingenuity (doable by computer).

Note that the proof of the Fundamental Theorem is much more obvious than that for your special case because the telescopic cancellation is obvious at this level of generality, whereas it is usually obfuscated in most specific instances. Namely, the proof of the Fundamental Theorem is just a rigorous inductive proof of the following telescopic cancellation $$\rm - F(0)\!+\!F(1) -F(1)\!+\!F(2) - F(2)\!+\!F(3)-\:\cdots - F(n-1)\!+\!F(n)\ =\:\: -F(0) + F(n) $$ where all but the end terms cancel out. For further discussion see my many posts on telescopy.

Answer 2

Absolutely correct, this is it.

Answer 3

You can also notice that $$\sum\limits_{i=1}^n \frac{i}{2^i} = \sum\limits_{i=1}^n \frac{1}{2^i}+ \sum\limits_{i=2}^{n} \frac{1}{2^i} + \dots + \sum\limits_{i=n}^n \frac{1}{2^i}= \sum\limits_{j=1}^n \sum\limits_{i=j}^n \frac{1}{2^i}$$ So you can find the result without knowing it in advance; this is only a geometric series.