1
$\begingroup$

I am struggling to understand basics as it related to forming a closed form expression from a summation. I understand the goal at hand, but do not understand the process for which to follow in order to accomplish the goal.

Find a closed form for the sum k+2k+3k+...+K^2. Prove your claim

My first approach was to turn it into a recurrence relation, which did not work cleanly. After that I would attempt to turn from a recurrence relation into a closed form, but I am unssucecssful in getting there.

Does anyone know of a strong approach for solving such problems? Or any simplistic tutorials that can be provided? The material I find online does not help, and causes further confusion.

My answer is below but Would like to see if there are more general approaches for ALL summations, as opposed to this specific example.


d=1 (difference in arithmetic series)
k+2k+3k+...+k(k) = k(1+2+3+...+k)
                 = k(k(1+k)1)
                 = k(k+k^2)
                 = k^2 +k^3 

If anyone could please maybe check the above, and also if there is a general approach for summations that dont happen to have an easily identifiable arithmetic series, even thought his one did. Also, how exactly would I prepare a proof for this claim?

proof attempt


k^2 + k^3 | k = 1 | = 1+1 = 2 = (1 + 1(1)). Base Case passes
assume True for k = n
Test for n + 1

(n+1)^2 + (n+1)^3 = (n^2 + 2n +1) + (n^3 +3n^2 + 3n + 1) 
                  = n^3 + 4n^2 +5n + 2
                  = 
I get stuck around here, I think I am doing something wrong, not sure how to prove correctly

Thanks

$\endgroup$
  • $\begingroup$ I've tried editing your post but I gave up. Please learn how to format formulae using the LaTeX style. $\endgroup$ – Alex M. Apr 26 '15 at 18:42
  • $\begingroup$ You are making a mistake: $1+2+ \cdots +k = \frac {k(k+1)} 2$, not what you write above. (You have a $\frac 1 2$ missing.) $\endgroup$ – Alex M. Apr 26 '15 at 18:44
0
$\begingroup$

$$S(k) = \sum_{i=1}^kk\cdot i = k\cdot\frac{k(k+1)}{2} = \frac12k^2(k+1)$$ It should be apparent from the above equation, but we can verify with induction: $k = 1 \implies S(1) = \frac12(1)^2(2) = 1 = \sum_{i=1}^1 i\cdot 1$.
If we assume $S(n - 1) = \frac12(n-1)^2n$, $$S(n) = \sum_{i=1}^nn\cdot i = \frac{n}{n-1}S(n-1) + n^2$$ $$= \frac{1}{2}n^2(n-1) + n^2 = \frac12n^2(n+1), \text{as desired}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.