8
$\begingroup$

$$\displaystyle\sum_{i=0}^\infty \frac {i^N} {4^i}$$

I'm supposed to evaluate this as I'm working through Data Structures and Algorithm Analysis in C++. I've solved similar problems, and after trying all of the algebra-fu manipulations I could think of, I'm stumped.

My first efforts were, similar to how I solved the three previous problems in the series, to try doing things like setting it equal to S, dividing both sides by four, and subtracting the equations, in various ways in an attempt to cancel terms. However, I'm missing some step to make it happen.

$\endgroup$
  • 1
    $\begingroup$ Do you know about derivatives in calculus? $\endgroup$ – Jonas Meyer May 17 '13 at 4:16
7
$\begingroup$

Note that for $\vert x \vert < 1$, we have $$\sum_{i=0}^{\infty} x^i = \dfrac1{1-x}$$ We then have $$\sum_{i=0}^{\infty} ix^i = x \dfrac{d}{dx}\left(\sum_{i=0}^{\infty} x^i \right) = x \dfrac{d}{dx}\left(\dfrac1{1-x}\right)$$ If we denote the operator $x\dfrac{d}{dx}$ as $L$, we then have $$\sum_{i=0}^{\infty} ix^i = L\left(\dfrac1{1-x}\right)$$ $$\sum_{i=0}^{\infty} i^2x^i = L\left(L\left(\dfrac1{1-x}\right) \right) = L^2\left(\dfrac1{1-x}\right)$$ And in general, $$\sum_{i=0}^{\infty} i^Nx^i = L^N\left(\dfrac1{1-x}\right)$$ Hence, $$\sum_{i=0}^{\infty} \dfrac{i^N}{4^i} = \left.L^N\left(\dfrac1{1-x}\right) \right \vert_{x=1/4}$$ Also, this is nothing but $$\text{Li}_{-N}\left(\dfrac14\right),$$ where $\text{Li}_s(z) = \displaystyle \sum_{k=1}^{\infty} \dfrac{z^k}{k^s}$, the Polylogarithm function.

$\endgroup$
3
$\begingroup$

Related techniques:(I), (II), (III). Recalling the identity for the operator $(xD)^n$, where $D=\frac{d}{dx}$,

$$ (xD)^n = \sum_{k=0}^{n}\begin{Bmatrix} n\\k \end{Bmatrix}x^k D^k , $$

where $\begin{Bmatrix} n\\k \end{Bmatrix}$ are the Stirling numbers of the second kind. One can get a closed form for the sum in terms of a finite sum. Applying this operator to the function $\frac{1}{1-x}$

$$ \sum_{k=0}^{\infty}{k^n}{x^k}= (xD)^n\frac{1}{1-x} = \sum_{k=0}^{n}\begin{Bmatrix} n\\k \end{Bmatrix}x^k D^k \frac{1}{1-x} $$

$$\implies \sum_{k=0}^{\infty}{k^n}{x^k}= \sum_{k=0}^{n}\begin{Bmatrix} n\\k \end{Bmatrix} k!\frac{x^k}{(1-x)^{k+1}}. $$

Subs $x=\frac{1}{4}$ in the above identity gives

$$ \sum_{k=0}^{\infty}\frac{k^n}{4^k} = 4\sum_{k=0}^{n}\begin{Bmatrix} n\\k \end{Bmatrix} \frac{k!}{3^{k+1}}. $$

Here is some values of the last formula for $1\leq n \leq 7$

$$ \left\{ \frac{4}{9},{\frac {20}{27}},{\frac {44}{27}},{\frac {380}{81}},{ \frac {4108}{243}},{\frac {17780}{243}},{\frac {269348}{729}} \right\} . $$

$\endgroup$
  • $\begingroup$ Interesting answer. (+1) $\endgroup$ – Olivier Oloa Jul 28 '16 at 7:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.