Register to reply

Inductive Proof on Well Known Sum

by Shackman
Tags: inductive, proof
Share this thread:
Shackman
#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
Wildfires and other burns play bigger role in climate change, professor finds
SR Labs research to expose BadUSB next week in Vegas
New study advances 'DNA revolution,' tells butterflies' evolutionary history
Mystic998
#2
Feb25-08, 07:02 PM
P: 206
What is [tex]\sum^{n}_{i=1} i[/tex]?
Shackman
#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
#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
#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
#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
#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
#8
Feb25-08, 09:54 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,092
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
#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