• Support PF! Buy your school textbooks, materials and every day products Here!

Prove by Induction

  • Thread starter Jimmy84
  • Start date
  • #1
191
0

Homework Statement


Prove by induction

1^2 + 2^2 + ... + (n-1)^2 < (n^3)/3

(This is the problem on page 33 of Apostol's book)



Homework Equations





The Attempt at a Solution



A(k) = 1^2 + 2^2 + ... + (k-1)^2 < (k^3)/3

A(k+1) = 1^2 + 2^2 + ... + k^2 < (k+1)^3/3


Start with A(k) and add k^2 to both sides. This gives the inequality

1^2 + 2^2 + ... + k^2 < (k^3)/3 + k^2


To obtain A(k+1) as a consequence of this, it suffices to show that

k^3/3 + k^2 < (k+1)^3 /3




Now (k+1)^3 /3 = k^3/3 + k^2 +k +1/3 which is greater than k^3/3 + k^2


Which proves the inequality. However I dont understand why does

k^3/3 + k^2 < (k+1)^3 /3 suffice to prove the inequality

Can anyone explain in detail why does that inequality proves it?
 

Answers and Replies

  • #2
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,553
1,157
They're using the transitive property of <. You know

1^2 + 2^2 + ... + k^2 < (k^3)/3 + k^2.

If you can show (k^3)/3 + k^2 < (k+1)^3/3, then you'll have

1^2 + 2^2 + ... + k^2 < (k^3)/3 + k^2 < (k+1)^3/3

Homework Statement


Prove by induction

1^2 + 2^2 + ... + (n-1)^2 < (n^3)/3

(This is the problem on page 33 of Apostol's book)



Homework Equations





The Attempt at a Solution



A(k) = 1^2 + 2^2 + ... + (k-1)^2 < (k^3)/3

A(k+1) = 1^2 + 2^2 + ... + k^2 < (k+1)^3/3


Start with A(k) and add k^2 to both sides. This gives the inequality

1^2 + 2^2 + ... + k^2 < (k^3)/3 + k^2


To obtain A(k+1) as a consequence of this, it suffices to show that

k^3/3 + k^2 < (k+1)^3 /3




Now (k+1)^3 /3 = k^3/3 + k^2 +k +1/3 which is greater than k^3/3 + k^2


Which proves the inequality. However I dont understand why does

k^3/3 + k^2 < (k+1)^3 /3 suffice to prove the inequality

Can anyone explain in detail why does that inequality proves it?
 
  • #3
191
0
Thanks a lot, I really appreciate it. :) I have been struggling with this for quite some time.
 

Related Threads for: Prove by Induction

  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
17
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
5K
Replies
2
Views
5K
Replies
3
Views
3K
Replies
3
Views
3K
Top