1
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ Is there an actual application to this? $\endgroup$
    – Dando18
    Commented Aug 12, 2017 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$ Commented Aug 12, 2017 at 20:38

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Commented Aug 12, 2017 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
    Commented Aug 12, 2017 at 20:03
  • $\begingroup$ @RuanSunkel see my edits $\endgroup$
    – Dando18
    Commented Aug 12, 2017 at 21:16
  • $\begingroup$ That makes a lot of sense, thank you, I appreciate it. $\endgroup$ Commented Aug 12, 2017 at 21:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .