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.

$\endgroup$
2
  • 2
    $\begingroup$ $\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... $\endgroup$
    – J. M. ain't a mathematician
    Commented Aug 15, 2012 at 11:48
  • $\begingroup$ @J.M. Sorry, of course, it was a typo. I have edited the question. $\endgroup$
    – 042
    Commented Aug 15, 2012 at 11:55

1 Answer 1

Reset to default
1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – 042
    Commented Aug 15, 2012 at 10:48
  • $\begingroup$ In that case, I suspect that the answer is no (not that I can think of how to prove it). $\endgroup$
    – preferred_anon
    Commented Aug 15, 2012 at 11:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .