How to find closed forms of summations
1,253
HINT:
$$\left(3+\dfrac{2r}n\right)^2=9+\dfrac{12}n\cdot r+\dfrac4{n^2}\cdot r^2$$
$$\sum_{r=1}^n1=n$$
$$\sum_{r=1}^nr=\dfrac{n(n+1)}2$$
$$\sum_{r=1}^nr^2=\dfrac{n(n+1)(2n+1)}6$$
Related videos on Youtube
Author by
Legion Daeth
Updated on March 03, 2020Comments

Legion Daeth over 3 years
My question is simple. Could someone explain in the simplest manner possible, how to find a closed form of a summation in general? Please explain it step by step because the book spends literally two sentences discussing the process.
Take this as an example problem. This is as far as I've gotten. Other articles seem to suggest that there is usually a pattern, and there's no standardized technique to find things like that.

Admin over 6 yearsThere is no simple and general method. Formulas are available for the particular cases $\sum_k k^n$ and $\sum_k r^k$ ($n$ natural, $r$ real). With more effort, one can solve $\sum_k P(k)r^k$ where $P$ is an arbitrary polynomial. Using complex numbers, you can also handle $\sum_k P(k)r^k\cos(k\theta),\sum_k P(k)r^k\sin(k\theta)$. Using the Taylor series approach, other cases are solved, involving terms with rational functions of $k$ and/or factorials, but there is no systematism.

Admin over 6 yearsIf you want to know all secrets, I can recommend "Concrete Mathematics, Second Edition by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: AddisonWesley, 1994), xiii+657pp. ISBN 0201558025", but this is probably way too advanced for your needs.

Jack D'Aurizio over 6 yearsLemma: if $p(x)$ is a polynomial with degree $d$, $$P(n)=\sum_{k=1}^{n}p(k)$$ is a polynomial with degree $d+1$, whose coefficients can be found through Lagrange's interpolation.


Legion Daeth over 6 yearsCould you post the worked out solution? I substituted algebraically and got an incorrect answer.