arjundabra's blog

Power Sums
By arjundabra, history, 4 months ago, In English

Hi all,

I made a short video on some nice observations about Power Sums of the form 1^n+2^n+3^n+.....+m^n and how to calculate formulae for them.

I hope this will be useful for some.

Let me know if you enjoyed the video and feedback / any questions in the comments below.

Hope you all have a good day! :)

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Can you add practice problem for this topic? This topic is way beyond my rating but I have a keen love for math since years.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    $$$1^k + 2^k + ... + n^k$$$ itself is here

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

    stop cheating first

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      like this?

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Nope, Like this BLATANT

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Coming from a new acc like cheaters do so that they can't get exposed from their original id submissions. Get some guts to come from real id then we'll talk troll

          → Reply
          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it +9 Vote: I do not like it

            u cheated though

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              Nope I didn't. There's just one skipped contest coz that solution happened to be similar to someone else. Can't help that. There'll be some minor similarities in some questions. It wasn't a copy though (and none of them are)

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                minor similarities (no).
                notorious co-incidence (yes)

                → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks!

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

O

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

At 12:30 in the video, you claimed that,

$$$ \displaystyle \sum_{r=2}^{n+1} \binom{n+1}{r} (-1)^r \sum_{k=1}^{m} k^{n+1-r} $$$

is a polynomial of degree n in m.

But shouldn't it be a polynomial of degree n+1 in m. Consider the following:

$$$ \displaystyle \sum_{r=0}^{n+1} \binom{n+1}{r} m^r = (1+m)^{n+1} $$$

which is actually a polynomial of degree n+1.

Also, where is the final formula to get the required sum for $$$ \displaystyle m>=10^9 $$$ in $$$ \displaystyle O(n) $$$ ?

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ig for the final sum we gotta use faulhaber polynomials. that would require counting for bernoulli numbers first

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The final formula usually is just using the fact that it's a polynomial to do polynomial interpolation.

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please note that the one you described is essentially different as the highest degree of m in your case will be n+1 (as r goes from 0 to n+1) but in the formulae described at 12:30 (the power of k is n+1-r) so the max power of k will be when r=2 i.e n+1-2 = n-1 and thus the sum over k will be a polynomial of degree n (1 more than the power) in m and not n+1 and C(n+1,r) (r goes from 2 to n+1) does not depend on m, hence this will not change the degree of the polynomial

    Using this method as it is described in the video I don't think so you can compute this in O(n), You can do something on the order of n^2 with this.

    There are other ways for example Lagrange interpolation using which you can calculate it faster, I will upload a video later on this.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok understood.

      I was actually thinking that even if you considered the second summation to be equal to 1. Even then the final answer would be $$$2^{n+1} +$$$ some constant. I was just focusing on the maximum power of $$$n$$$ occurring there and forgot the fact that the polynomial was a function of m.

      → Reply
»
4 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

nvm i was wrong

→ Reply
»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

I realized that I used NTT to calculate Stiring numbers, then to get the answer. But Lagrange Interpolation doesn't need to deal with any of Stiring. It's faster and shorter.

→ Reply