Proof by induction

  • Thread starter Link
  • Start date
  • #1
134
1
I am supposed to prove a conjecture by induction. I have worked out that the series can be described by:

a = 2,6,12,20,30
S = 2+8+20+40....

(n^2) + n = (1/3) ((n^3)+3(n^2)+2n)

However, i cannot prove it by induction. It seems like there is smth wrong with the K^3.
 

Answers and Replies

  • #2
695
0
What series? And what precisely is it that you want to prove? I doubt that you actually want to prove that (n^2) + n = (1/3) ((n^3)+3(n^2)+2n), because that's not true (for all n).
 
  • #3
benorin
Homework Helper
Insights Author
1,309
114
This should help

Muzza said:
What series? And what precisely is it that you want to prove? I doubt that you actually want to prove that (n^2) + n = (1/3) ((n^3)+3(n^2)+2n), because that's not true (for all n).
I think Link means [tex]\sum_{k=1}^{n} \left(k^2 + k\right) = \frac{1}{3}(n^3+3n^2+2n)[/tex], which is in fact true.
The inductive proof goes like this:
i. [tex]\sum_{k=1}^{n} \left(k^2 + k\right) = \frac{1}{3}(n^3+3n^2+2n)[/tex] , holds for [tex]n=1[/tex];
ii. Assume [tex]\sum_{k=1}^{n} \left(k^2 + k\right) = \frac{1}{3}(n^3+3n^2+2n)[/tex] holds for some fixed n, so that
[tex]\sum_{k=1}^{n} \left(k^2 + k\right) = \frac{1}{3}(n^3+3n^2+2n)\Rightarrow \sum_{k=1}^{n} \left(k^2 + k\right) + \left((n+1)^2 + (n+1)\right) = \frac{1}{3}(n^3+3n^2+2n) + \left((n+1)^2 + (n+1)\right)[/tex]
[tex]\Rightarrow \sum_{k=1}^{n+1} \left(k^2 + k\right) = \frac{1}{3}(n^3+6n^2+11n+6) = \frac{1}{3}\left((n+1)^3+3(n+1)^2+2(n+1)\right) [/tex].
Therefore, [tex]\sum_{k=1}^{n} \left(k^2 + k\right) = \frac{1}{3}(n^3+3n^2+2n)[/tex] holds for every positive integer n.
 
Last edited:
  • #4
134
1
thanks! but there is another problem arising from this, regarding the interpretation of a question.

Based on the results obtained above, how can i calculate 1^2 + 2^2 + 3^2.....+n^2?

the problem is the word "calculate", do you think they want me to use the same method to derive a general expression for this series, or actually get an numerical value (i dont think its obtainable)? Im the only one in class doin this investigation and I cannot reach my teacher this week so advice on the meaning of this is appreciated.
 
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,847
966
Well, you now know that
[tex]\sum_{k=1}^{n} \left(k^2 + k\right)=\sum_{k=1}^nk^2+ \sum_{k=1}^nk = \frac{1}{3}(n^3+3n^2+2n)[/tex]
If you know a formula for
[tex]\sum_{k=1}^{n} k[/tex]
just subtract that from both sides.
 

Related Threads on Proof by induction

  • Last Post
Replies
6
Views
883
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
4
Views
887
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
961
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
944
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
16
Views
2K
Top