Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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}$$
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.
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.
$\endgroup$
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.
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} $$
