Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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_{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?

share|improve this question
2  
Yes, your solution is correct and this is a good approach to proving formulas by induction. Also, this is very nicely typed up. –  Deven Ware Oct 9 '12 at 21:53

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
@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. –  Mike Oct 9 '12 at 22:10

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.

share|improve this answer

Absolutely correct, this is it.

share|improve this answer
    
That was quick! Thank you. –  Onur Oct 9 '12 at 21:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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