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
Best Answer
$$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}.$$