# General technique to find partial sum formula for series such as $\sum n^3/2^n$

Background. Working in a secondary school class on random walks that could only head in two directions (e.g., South and West) we stumbled upon the following summation to be evaluated:

$$\sum_{n=0}^{\infty} \frac{(n-1)n(n+1)}{2^n}$$

We were able to "solve" this in three ways: using some probabilistic intuition, plugging the formula directly into Mathematica/Wolfram Alpha, and using the identity:

$$\frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots$$

differentiated a few times over to find (verification pasted from Wolfram Alpha):

after which plugging in $x = 1/2$ gives roughly the series about which we were curious.

Another instructor was able to tinker with the above-mentioned series and figure out a closed form for the $m$th partial sums, which could then be verified by induction (after which taking the limit as $m \rightarrow \infty$ resolves the matter). In fact, Wolfram Alpha produces the closed form for this partial sum immediately upon input. For example, inputting the series above yields:

Question: Given an infinite series that consists of the ratio of a polynomial in $n$ (numerator) to a constant raised to some power that is linear in $n$ (denominator) what is a general technique to produce the closed formula corresponding to the series' $m$th partial sums?

Given the context, material at the level of strong secondary mathematics (or early undergraduate mathematics) would be ideal, but mathematics at any level - references, related problems and/or solutions, and extensions - are all welcome, too.

I would especially appreciate answers that "fill in" all details, e.g., by including a worked example, so as to make this post more pedagogically effective in a self-contained manner.

Let's say you want to compute $$\sum_{n=0}^{m}\frac{a_0+a_1n+\dotsb+a_kn^k}{c^n} =\sum_{n=0}^{m}\frac{P(n)}{c^n}.$$ First note that $$\sum_{n=0}^{\infty}(a_0+a_1n+\dotsb+a_kn^k)x^n=P(xD)\left(\frac{1}{1-x}\right)=G(x)$$ where $xD$ is the operator $x\frac{d}{dx}$. Then $$G(x/c)=\sum_{n=0}^{\infty}\left(\frac{a_0+a_1n+\dotsb+a_kn^k}{c^n}\right)x^n;\quad |x|<|c|.$$ In particular $$\frac{1}{1-x}G(x/c)=\sum_{n=0}^{\infty}\left(\sum_{m=0}^{n}\left(\frac{a_0+a_1n+\dotsb+a_kn^k}{c^n}\right)\right)x^{n}.$$ Hence it suffices to compute the coefficient of $x^{n}$ in $\frac{1}{1-x}G(x/c)$ which is typically done (by hand) with partial fractions.