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.

I am very confused with complete induction. Because in every task there is something different to do, and I never know what to insert (thats my biggest problem). Here's the example: Proof with complete induction. Please please help me, because I have exams coming up (I am just becoming a primary school teacher..)

For $n\in\mathbb{N}$:

$$\sum^n_{i=1}\frac{1}{(2i-1)(2i+1)}=\frac{n}{2n+1}$$

share|improve this question
    
rewrite your question in correct format! –  Maisam Hedyelloo Feb 20 '13 at 17:53
1  
As the solutions show, complete (or strong) induction is not needed here: ordinary induction suffices. –  Pete L. Clark Feb 20 '13 at 18:40
2  
@PeteL.Clark This may be a matter of translation (I dunno where Sophia is from). For example, the German translation for mathematical induction happens to be vollständige Induktion, which translates back literally to complete induction. –  Hagen von Eitzen Feb 20 '13 at 21:47
    
@Hagen What is the German term for non-mathematical (empirical) induction? –  Math Gems Feb 20 '13 at 22:40
1  
@MathGems: Induktion. –  Brian M. Scott Feb 21 '13 at 13:23

3 Answers 3

up vote 9 down vote accepted

For a full solution, proceed like this:

$n=1$: $$\sum_{i=1}^1 \frac{1}{(2i-1)(2i+1)} = \frac{1}{(2-1)(2+1)} = \frac{1}{3} = \frac{1}{2 \cdot 1 +1},$$ so it holds for $n=1$.

Assume next that it holds for some generic $n$. You need to show that then it also holds for $n+1$. As it holds for $n$, you can assume that $$\sum_{i=1}^n \frac{1}{(2i-1)(2i+1)} = \frac{n}{2n+1}. \quad (1),$$ and want to show that $$\sum_{i=1}^{n+1} \frac{1}{(2i-1)(2i+1)} = \frac{n+1}{2(n+1)+1}. \quad (2)$$ Then: $$\begin{align} \sum_{i=1}^{n+1} \frac{1}{(2i-1)(2i+1} &= \sum_{i=1}^n \frac{1}{(2i-1)(2i+1)} + \frac{1}{(2(n+1)-1)(2(n+1)+1)} \\ & = \frac{n}{2n+1} + \frac{1}{(2n+1)(2n+3)} \quad \text{using (1)} \\ & = \frac{n(2n+3)}{(2n+1)(2n+3)} + \frac{1}{(2n+1)(2n+3)} \\ & = \frac{2n^2 +3n +1}{(2n+1)(2n+3)} \\ & = \frac{(n+1)(2n+1)}{(2n+1)(2n+3)} = \frac{n+1}{2(n+1)+1},\\ \end{align}$$ which is (2), and was to be shown.

share|improve this answer
    
Thank youuuuuuuuuuuu!!! –  Sophia Feb 20 '13 at 18:25
10  
Looking at the edit records, gnometorule answered the question at 2013-02-20 18:13:32Z and amWhy's edit at 2013-02-20 18:19:07Z shows the same content from "Assume next that it holds for some generic $n$." The edits are more than 5 minutes apart (5:35), so it doesn't appear that gnometorule could have copied from amWhy's edit. –  robjohn Feb 20 '13 at 19:13

For general inductive proofs it may well be true that "there is something different to do" in each new problem, e.g. it may require genuine ingenuity to devise an appropriate induction hypothesis. However, this is not the case for inductive proofs of sums like the above. As I explained in this answer, many inductive proofs of sums and products are of a very simple inductive type known as telescopy. For inductions of this type one can do the induction uniformly - once and for all - by abstracting it into a theorem that applies to all such problems. For sums this yields

Theorem $\rm \displaystyle\ \ \sum_{i\,=\,1}^n\, f(i)\, =\, g(n)\iff f(1) = g(1)\ {\rm\ and\ }\ f(n) \,=\, g(n)-g(n\!-\!1)\:\ $ for $\rm\,n > 1.$

In your case we have

$$\rm f(n) \,=\, \frac{1}{(2n-1)(2n+1)},\quad g(n) \,=\, \frac{n}{2n+1}$$

Thus, applying the theorem, we check that $\rm\ f(1) = 1/3 = g(1)\ $ and

$$\rm g(n) - g(n\!-\!1) = \frac{n}{2n\!+\!1} - \frac{n\!-\!1}{2n\!-\!1}\, =\, \frac{n(2n\!-\!1)-(2n\!+\!1)(n\!-\!1)}{(2n\!-\!1)(2n\!+\!1)}\, = \frac{1}{(2n\!-\!1)(2n\!+\!1)} = f(n)$$

which completes the proof. Notice that the proof required no ingenuity - only verifying some simple polynomial (or rational function) equalities - a mechanical process.

share|improve this answer
2  
I had thought about presenting a proof using telescoping series. My reason for not posting my proof was that the question was more on the mechanics of induction than on possible simplifications in special cases. Perhaps the downvoter (not I) was thinking this was more confusing to someone just beginning with induction. –  robjohn Feb 20 '13 at 21:11
6  
@amWhy I never imagined anyone would consider linking to related posts as "self-advertising". I am here first and foremost to teach mathematics. So, e.g. when I teach telescopic induction I think it is helpful to link to other examples of telescopic induction (which arises in many guises). –  Math Gems Feb 20 '13 at 21:18
2  
@MathGems: I agree. I believe that in most cases, a downvote without a reason is non-constructive criticism. I am of the mind that a constructive comment is better than a downvote anyway. –  robjohn Feb 20 '13 at 21:31
3  
@amWhy: Math Gems definitely has a certain style :) –  The Chaz 2.0 Feb 22 '13 at 23:55
1  
@The Chaz 2.0 Yes, indeed! :-) –  amWhy Feb 22 '13 at 23:59

There is one more (easier) way to solve this problem without induction: Expand the summand into partial fractions to obtain (denote $S_n$ the actual sum): $$ S_n = \frac{1}{2} \sum_{k=1}^{n}\bigg(\frac{1}{2k-1}-\frac{1}{2k+1} \bigg)=\frac{1}{2} \bigg(1-\frac{1}{3} +\frac{1}{3} + \cdots - \frac{1}{2n+1} \bigg) = \frac{n}{2n+1} $$

share|improve this answer

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.