1
$\begingroup$

I am aware of that this question shall be rather basic, and that there may be a lot of resources on this, but it is quite complicated to use Google to find relevant results for this (I have not found anything relevant after a fast scan of Concrete Mathematics (Graham-Knuth-Patashnik) as well).

My question is: can be a sum $\sum_{k=0}^n p(k) \cdot f(k),$ where $p(n)$ is a polynomial and $f(n)$ is an arbitrary function, expressed in terms of $f(n)$ and, perhaps, $\sum_{k=0}^n f(k),$ in some general manner? That is, is there any general formula to express sums of that form in terms of $f(n)$ and its sum?

I am aware of the method of per-partes summation. But, to my knowledge, this method can be applied to sums of this type only if $f(n) = \Delta g(n)$ for some known function $g(n)$. The result is then in terms of $g(n)$ and its sum. My question therefore essentially is, if it is possible to overcome this.

  • 0
    @J.M. Sorry, of course, it was a typo. I have edited the question.2012-08-15

1 Answers 1

1

You remark that summation by parts can be applied if $f(n)=\Delta g(n)$. By a theorem analagous to the Fundamental Theorem of Calculus, it can be shown that $g(n)=\sum_{k=0}^{n-1}f(k) \implies \Delta g(n)=\sum_{k=0}^{n}f(k)-\sum_{k=0}^{n-1}f(k)=f(n)$ Does this help?

  • 0
    In that case, I suspect that the answer is no (not that I can think of how to prove it).2012-08-15