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}$$

  • rewrite your question in correct format! – M.H 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
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.

  • 11
    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.

  • 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} $$

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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