Verification of Sum without closed-form expression

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)

• Is there an actual application to this? – Dando18 Aug 12 '17 at 19:34
• 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. – 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.

• 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. – Ruan Sunkel Aug 12 '17 at 20:01
• Unless you calculate the sum then you can't compare for equality. Except for some tricks, but there's no definite way to tell. – Dando18 Aug 12 '17 at 20:03
• @RuanSunkel see my edits – Dando18 Aug 12 '17 at 21:16
• That makes a lot of sense, thank you, I appreciate it. – Ruan Sunkel Aug 12 '17 at 21:31