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.

  • 2
    $\sum\limits_{k=0}^n f(n)=(n+1)f(n)$, so with your question as it stands, there's not much that can be done...2012-08-15
  • 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
    Well, yes. However, my question has been probably a little inaccurate. This method is fine, but leads to a double sum of $f(n)$ after the application of the summation by parts. And I am interested, if there is a method that leads to the closed-form solution, where the ordinary sum of $f(n)$ is allowed, i.e., a solution without the need of summing the sum of $f(n)$. However, it is possible that this question does not make much sense. My apologies, if the transition to such a solution is straightforward.2012-08-15
  • 0
    In that case, I suspect that the answer is no (not that I can think of how to prove it).2012-08-15