Summation to Closed Form conversion

1,331

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

Share:
1,331

Related videos on Youtube

Busturdust
Author by

Busturdust

media and entertainment.

Updated on April 27, 2020

Comments

  • Busturdust
    Busturdust over 3 years

    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

    • Alex M.
      Alex M. over 8 years
      I've tried editing your post but I gave up. Please learn how to format formulae using the LaTeX style.
    • Alex M.
      Alex M. over 8 years
      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.)