7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Yes, your solution is correct and this is a good approach to proving formulas by induction. Also, this is very nicely typed up. $\endgroup$ – Deven Ware Oct 9 '12 at 21:53
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @JL90 Nice. I just wanted to add that if he had failed to notice this, it was unnecessary to put the 2 over a common denominator as the 2 should remain in the final form. $\endgroup$ – Mike Oct 9 '12 at 22:10
2
$\begingroup$

Absolutely correct, this is it.

$\endgroup$
  • $\begingroup$ That was quick! Thank you. $\endgroup$ – Onur Oct 9 '12 at 21:57
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.