Inductive Proof on Well Known Sum


by Shackman
Tags: inductive, proof
Shackman
Shackman is offline
#1
Feb25-08, 06:59 PM
P: 22
1. The problem statement, all variables and given/known data
Use induction to prove the equation
(1+2+...+n)^2 = 1^3 + 2^3 + ... + n^3

2. The attempt at a solution
I've done three inductive proofs previous to this one where I showed that the equation was true for some case (usually n=1), then assumed it was true for n, and proved it was true for n+1. This proof doesn't seem to fit that form though because for the other proofs I could write it as the right hand side of the equation (since it's assumed that it is true for n) plus the right hand side of the equation when n+1 is plugged in. But in this case..

(1+2+...+n+(n+1))^2 != (1+2+...+n)^2 + (n+1)^2

So, I guess I haven't done a proof like this and could use a nudge in the right direction..
Phys.Org News Partner Science news on Phys.org
Review: With Galaxy S5, Samsung proves less can be more
Making graphene in your kitchen
Study casts doubt on climate benefit of biofuels from corn residue
Mystic998
Mystic998 is offline
#2
Feb25-08, 07:02 PM
P: 206
What is [tex]\sum^{n}_{i=1} i[/tex]?
Shackman
Shackman is offline
#3
Feb25-08, 07:11 PM
P: 22
n(n+1)/2

In an effort to see where you're going with this, I thought I'd do the same for i^2 and got

n^2(n^2 + 1)/4

Either this isn't correct or I'm not sure where you're headed.

Mystic998
Mystic998 is offline
#4
Feb25-08, 07:16 PM
P: 206

Inductive Proof on Well Known Sum


Quote Quote by Shackman View Post
n(n+1)/2

In an effort to see where you're going with this, I thought I'd do the same for i^2 and got

n^2(n^2 + 1)/4

Either this is correct or I'm not sure where you're headed.
Well, the second part isn't correct at all ([itex]\sum^{n}_{i=1} i^2 = \frac{n(n+1)(2n+1)}{6}[/itex]), but that wasn't really my point. Look at the left hand side of your proposed equality.
Shackman
Shackman is offline
#5
Feb25-08, 07:27 PM
P: 22
Alright, so the left hand side is equal to ((n(n+1))/2)^2 or (n^4 +2n^3 +n^2)/4...
Mystic998
Mystic998 is offline
#6
Feb25-08, 07:31 PM
P: 206
So prove that (n(n+1)/2)^2 is equal to the right hand side. Much easier to verify.
Shackman
Shackman is offline
#7
Feb25-08, 09:33 PM
P: 22
That is a proof of the equality but it isn't inductive though. Inductive proofs always follow the form:
1) prove the base case
2) write the induction hypothesis for the case of n (assume its true basically)
3) use 2) to prove for n+1
Hurkyl
Hurkyl is offline
#8
Feb25-08, 09:54 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
Quote Quote by Shackman View Post
(1+2+...+n+(n+1))^2 != (1+2+...+n)^2 + (n+1)^2
As you say, that is not the correct formula for the square of two things. Fortunately, you know the right formula for the square of two things.... (right?)
Shackman
Shackman is offline
#9
Feb25-08, 10:02 PM
P: 22
You're talking about the binomial theorem right?


Register to reply

Related Discussions
Inductive effect Chemistry 2
Inductive acceleration General Physics 12
Help with an inductive proof Introductory Physics Homework 5
inductive playgrounds Set Theory, Logic, Probability, Statistics 0
Inductive Proof General Math 2