# How can I find $n$ such that $\sum_{k=1}^n f(k) \leq c$ without computing many partial sums?

Say I have a series $\sum_{k=1}^n f(k)$ for some function $f$. I want to find the biggest $n \in \mathbb{N}$ such that $\sum_{k=1}^n f(k) \leq c$ for some $c \in \mathbb{R}$ without actually computing the partial sums. Is there a method for finding such $n$ for general $f$?

For example take

$$\sum_{k=1}^n \binom{12}{k} \frac{1}{k} \leq 400.$$

If I am not mistaken, this should hold for $n \leq 4$. How would I find this without computing the partial sums? Thanks in advance for any help.

A technique that can help to solve many complicated sums is called calculus of finite differences. If the tools of calculus are defined over infinitesimal intervals, expressed in various ways, the calculus of finite differences defines similar tools to deal with differences over discrete intervals.

Using calculus of finite differences, you can reduce complex sigma expressions into integrals, or directly reduce them using the similar tools you'd use to find an anti-derivative.

There is actually not as much information about the calculus of finite differences as I'd hoped. However, after searching a bit, I found the wonderful article that introduced me to the subject, and a few more. Its name will no doubt sound rather appealing.

A Tutorial for Solving Nasty Sums - A wonderful article that provides a detailed, but not too technical look at calculus of finite differences as used to solve various sigma expressions.

Introduction to Difference Equations - A more comprehensive book about the topic. Not everything here is directly relevant.

Concrete Mathematics - Another rich book on the topic. Also contains identities specifically regarding binomials and binomial sums. Alas, nothing to compute the example problem.

Additional information and methods of finite calculus:

Indefinite Sum, Wikipedia - Wikipedia article. Has a good overview of indefinite sums and several useful identities and rules.

Euler-Maclaurin Formula, Wikipedia - Which defines a relation between the integral of a function and the indefinite sum of a function. Highly powerful for evaluating indefinite sums.

The problem posed in the question is an example that probably can't be solved using finite calculus, because the sum $\sum_{k}^{m} \binom{n}{k}$ doesn't have a closed form representation.

as far as I know, this specific sum cannot be computed without also computing all the partial sums.

Still, I hope this information helps you out.

• Can you show how to apply this method to this particular problem? Nov 8 '12 at 19:15
• I've edited my answer to provide additional information, and also pointed out (and realized, actually) that there is no way to solve the example sum using this method. Nov 9 '12 at 2:58