Induction ProblemDate: 10/14/97 at 20:30:20 From: sharon wesolowski Subject: Induction Hi, I am having a problem with the reasoning of the left side of an induction problem. Here's the original problem: Use math induction to prove that (1 + 2 + 3 +....n)^2 = 1^3 + 2^3 + 3^3....n^3 This is what I have done: p(k) = (6)^2 = 36 n^2 = [(n)(n+1)(2n+1)]/6{p} = {pk} [n^2(n+1)^2]/4 [k(k+1)(2k+1)}/6 = [k^2(k+1)^2]/4 Pk+1 = [(k+1)^2(k+2)^2/4 = (4k-3) + (4k+1) Here I am stuck. Is the basis right? How do I match the right and the left? Thanks. Sharon W. Date: 10/15/97 at 18:56:38 From: Doctor Tom Subject: Re: Induction Hi Sharon, There are a couple of ways to do this. What you seem to be doing is the fastest, assuming that you already know how to add up the cubes of the numbers to get 1^3 + ... + n^3 = [n^2(n+1)^2]/4. If you know that, and you also know that 1 + 2 + ... + n = n(n+1)/2, then squaring that value obviously gives you the sum-of-cubes number and you're done, with no induction at all. Actually, induction was involved, since you need it to prove the two formulas that you used. But the problem can be solved directly by induction as well, as follows. First check that it works for n=1. 1^2 = 1^3 - yup - that part's okay. Now assume it's true for n = k: (1 + 2 + ... + k)^2 = 1^3 + 2^3 + ... + k^3. What is: (1 + 2 + ... + k + (k+1))^2? Let's look at it like this: ((1 + 2 + ... + k) + (k+1))^2, which is (A+B)^2, if A = (1 + 2 + ... + k) and B is (k+1), right? Well, (A + B)^2 = A^2 + 2AB + B^2, so your sum is: (1 + 2 + ... + k)^2 + 2(1 + 2 + ... + k)(k+1) + (k+1)^2 (1) I assume you know that 1 + 2 + ... + k = k(k+1)/2, so (1) becomes: (1 + 2 + ... + k)^2 + 2k(k+1)(k+1)/2 + (k+1)^2 (2) By your induction hypotheses, the first term of (2) is just: 1^3 + 2^3 + ... + k^3 and so we just need to show that the rest of the junk on the right of (2) adds up to (k+1)^3. 2k(k+1)(k+1)/2 + (k+1)^2 = k(k+1)^2 + (k+1)^2 = (k+1)(k+1)^2 = (k+1)^3. QED. -Doctor Tom, 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/