Take for example the sum $\sum_{k=0}^{n}f(n,k)$, where $f(n,k)$ is some expression. Assume there is no closed-form expression for the sum.

Given some value S which is believed to be the value of the sum, and given the details of $f(n,k)$, is there a method to verify that S is the actual value of the sum without explicitly evaluating it? (In the case where evaluating the sum is intractable)

  • $\begingroup$ Is there an actual application to this? $\endgroup$ – Dando18 Aug 12 '17 at 19:34
  • $\begingroup$ Well, I have a sum involving floor, sqrt, ceil. I can predict what the actual value will be for large n, but evaluating the sum for large n is not feasible, and no closed-form exists, so my predicted values are useless. A crude example of this is, I have this very large number n, and I predict that this number is prime, or not prime, but it will take to long to test. Obviously, this is nonsense, but it just illustrates the idea. I am interested if this type of concept exists, and how one would go about defining and formalizing it. $\endgroup$ – Ruan Sunkel Aug 12 '17 at 20:38

You're asking if you can verify that $S = \sum_{k=0}^n f(n,k)$, only knowing $S$. The answer is no. Think if I asked you to show that $x=5$, but I didn't tell you anything about $x$. You couldn't unless I told you the value of $x$.

It's the same thing with your question. Without summing the terms or evaluating a closed form, I know nothing about the value of $\sum_{k=0}^n f(n,k)$.

Now there are some observations you can make, but they don't work $100\%$ of the time.

  • Look at the signs. If $S>0$, but $f(n,k)<0,\ \forall n,k$, then there is certainly no equality. More generally, if $\text{sgn}(S)\ne\text{sgn}(f(n,k)),\ \forall n,k \implies S \ne \sum_{k=0}^n f(n,k)$.

  • Look at the behavior. If $S<f(n,0)$ and $f'(n,k)>0,\ \forall k>0$, then there is no equality.

In response to your comment on the question: without knowing $f(n,k)$, there's no general solution to solve this without calculating the sum. You can find properties of $f(n,k)$ that you can leverage to answer your problem. To show this I'll address the example you've given

I have a sum involving floor, sqrt, ceil

The best you're going to get here is approximations. Take, $$ \sum_{k=a}^n \lfloor c\cdot k\rfloor $$ There's no closed-form for this, so the best we can do is bound it very tight. See my my question here, where I show $$ \sum_{k=a}^n \lfloor c\cdot k\rfloor \approx \frac{(a-n-1)(ac+cn-1)}{-2} $$ is a very accurate approximation. Even for large $n$.

This is just an example of approximations you can make and unfortunately, without calculating the series or a closed form, probably the best you can do is exploit properties of the sum.

  • $\begingroup$ I understand. f(n,k) is just an example, it can be any expression. So what I mean is, S is known, the expression is also known, but it is also known that there is no closed-form for the sum, if that makes sense. $\endgroup$ – Ruan Sunkel Aug 12 '17 at 20:01
  • $\begingroup$ Unless you calculate the sum then you can't compare for equality. Except for some tricks, but there's no definite way to tell. $\endgroup$ – Dando18 Aug 12 '17 at 20:03
  • $\begingroup$ @RuanSunkel see my edits $\endgroup$ – Dando18 Aug 12 '17 at 21:16
  • $\begingroup$ That makes a lot of sense, thank you, I appreciate it. $\endgroup$ – Ruan Sunkel Aug 12 '17 at 21:31

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.