Solve for the upper limit of a summation

320 Views Asked by At

$a,b$ and $c$ are all natural numbers, and function $f(x)$ always returns a natural number. If$$ \sum_{n=b}^{a} f(n) = c,$$ in terms of $b,c$ and $f$, how would you solve for $a$? Do I require more information to solve for $a$?

EDIT: If $x$ increases $f(x)$ increases

3

There are 3 best solutions below

0
On BEST ANSWER

Once you add that $f(n)$ is increasing with $n$ you can set an upper bound by $\sum_{n=b}^{a} f(n) \ge (a-b+1)f(b)$. As long as $f(b) \gt 0$ you can say $a \le \frac c{f(b)}+b-1$. Now if you have a closed form you have brackets for your root finding, which can guarantee that you terminate.

0
On

Here's a thought, assuming $f$ is invertible:

\begin{align} \sum_{n=b}^a f(n) = c &\iff f(1)+f(2)+ \cdots + f(a) = c\\ &\iff f(a) = c-f(1)-f(2)-\cdots-f(a-1) \\ &\iff a = f^{-1}(c-f(1)-f(2)-\cdots-f(a-1)) \end{align}

0
On

If you do not have any other info, I doubt any closed form is possible.

It really depends on what can we do about $f$, suppose there is a quick way to evaluate $g(x)=\sum_{n=b}^x f(n)$, then note that $g$ is an increasing function and a method such as binary search might suitable to find the preimage of $g^{-1}(c)$.

Suppose $g$ is not easily computable, I agree with Ross that perhaps, we have to add a term at a time until we hit the number $c$.