0

$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

V..
  • 3
  • Methods for this are going to be quite ad hoc unless you tell us more about $f$. –  Mar 20 '18 at 02:55
  • @user296602 I do not know anything else about $f$... – V.. Mar 20 '18 at 02:58
  • If we don't have a closed form for the sum, I don't see anything better than adding up the sum until it reaches $c$. You may be able to approximate it with an integral if you can regard $f$ as a function on the reals. If we do have a closed form, you can do one dimensional root finding on sum-c – Ross Millikan Mar 20 '18 at 03:15

3 Answers3

0

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}

BSplitter
  • 1,553
0

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$.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
0

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.

Ross Millikan
  • 374,822