Proof by InductionDate: 7/3/96 at 19:0:59 From: Scott Turner Subject: Proof by Induction I'm trying to prove that 1 + 1/4 + 1/9 + ... 1/n^2 < 2 - 1/n for all n > 1. Now the base step is simple: n = 2: 1 + 1/4 < 2 - 1/2, true The inductive step is assume true for n. I must show it is also true for n + 1 so 1 + 1/4 + 1/9 + .. 1/n^2 + 1/(n+1)^2 < 2 - 1/n+1 which I know is < (2 - 1/n) + 1/(n+1)^2 by the inductive hypothesis. My problem is that I end up with an algebraic equation which can't be broken down and which I can't assume proves my above assertion. Help. St Date: 7/4/96 at 2:22:32 From: Doctor Pete Subject: Re: Proof by Induction The assumption that the statement to be proved is true for some n is called the induction hypothesis. It is not circular reasoning because the proof requires that the given is true for *all* n. The inductive step is the part where you show that the truth of the induction hypothesis implies that the given statement is also true for the next value of n. This completes the proof. So in order to work this out, you show the first case (n=2); this was done. Then you make the induction hypothesis, which you also have done. Then you start from the induction hypothesis to create the next case, n --> n+1, and show this is true. With this in mind, we have 1 + 1/4 + 1/9 + ... + 1/n^2 < 2 - 1/n [1] => 1 + 1/4 + ... + 1/n^2 + 1/(n+1)^2 < 2 - 1/n + 1/(n+1)^2 [2] = 2 - (1/n - 1/(n+1)^2) < 2 - (1/n - 1/(n*(n+1))) [3] = 2 - (1 - 1/(n+1))/n [4] = 2 - ((n+1-1)/(n+1))/n = 2 - (n/(n+1))/n = 2 - 1/(n+1). [1]: This is the induction hypothesis. [2]: Added 1/(n+1)^2 to both sides. [3]: Note 1/(n+1)^2 = 1/((n+1)*(n+1)) < 1/(n*(n+1)). [4]: Factored out 1/n. Since we have shown the (n+1)th case is true if the (n)th case is true, and the case for n=2 is true, then the given statement is true for all n greater than or equal to 2. I believe that the problem you were running into had more to do with finding the appropriate simplification, but it was complicated by the fact that when you were working this out, you started from the (n+1)th case. Also, perhaps you were looking for strict equalities to transform one case into the next, rather than for a chain of inequalities that allow for the right simplifications: note I used an inequality in step [3]. Hope this clears things up. :) -Doctor Pete, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/