Evaluating $S_{N} = \sum_{i=0}^\infty \frac{i^N}{4^i}$ using recursion

Question

I am trying to obtain a formulae for a summation problem under section (d) given in a solutions manual for "Data Structures and Algorithm Analysis in C - Mark Allen Weiss", here's the screen shot

As the pdf is protected i could not download it. Here's my attempt at it. Let $S_{N} = \sum_{i=0}^\infty \frac{i^N}{4^i}$, then starting from $N = 4$ we have $S_{0} = \frac{4}{3}, S_{1} = \frac{4}{9} , S_{2} = \sum_{i=0}^\infty \frac{2i + 1}{3*4^i}, S_{3} = \sum_{i=0}^\infty \frac{3i^2 + 3i + 1}{3*4^i},S_{4} = \sum_{i=0}^\infty \frac{4i^3 + 6i^2 + 4i + 1}{3*4^i}$.

Using recursion, we have $S_{0} = \frac{4}{3}, S_{1} = \frac{1}{3}S_{0} , S_{2} = \frac{2S_{1} + S_{0}}{3} = \frac{5}{9}S_{0} , S_{3} = \frac{3S_{2} + 3S_{1} + S_{0}}{3} = \frac{11}{9}S_{0}, S_{4} = \frac{4S_{3} + 6S_{2} + 4S_{1} + S_{0}}{3} = \frac{95}{27}S_{0}$.

After cleaning up further we have $$S_{0} = \frac{4}{3}, S_{1} = \frac{1}{3}S_{0} , S_{2} = \frac{5}{9}S_{0} , S_{3} = \frac{11}{9}S_{0}, S_{4} = \frac{95}{27}S_{0}$$ I dont see a pattern emerging to make a formulae.I may be doing something wrong, any help is greatly appreciated.

Answer 1

The technique given in the question gives the recurrence:

$$3S_N=\sum_{i}\frac{(i+1)^N-i^N}{4^i}=\sum_{j=0}^{N-1} \binom Nj S_j$$

This follows from the binomial theorem: $$(i+1)^N-i^n=\sum_{j=0}^{N}\binom Nj i^j$$

But “solving” this recurrence is very painful. I don’t know how to solve it. It’s not even clear the book is asking you to solve the recurrence.

Answer 2

I agree with the answer by @ThomasAndrews in terms of the fact that this recursion is difficult to be solved directly, although I have a feeling it can be solved using finite difference calculus, since there is at least one solution to it as I demonstrate below.

Define the function

$$F_N(e^x)=\sum_{n=0}^{\infty}n^N e^{nx}=\frac{d^N}{d x^N }\left(\frac{1}{1-e^x}\right)$$

We will attempt to explicitly evaluate the derivatives. We get extremely lucky because of the occurrence of $e^x$ which massively reduces Faa di Bruno's formula for $f(x)=1/(1-x), g(x)=e^x$ in terms of the Bell polynomial to:

$$F_N(e^x)=\sum_{n=1}^N f^{(k)}(e^x)B_{N,k}(e^x,..., e^x)$$

Note that since $B_{N,k}(x,...,x)=S(N,k)x^k$ - where $S(N,k)$ are the Stirling numbers of the 2nd kind - we can express the formula for $S_N(x)$ concisely as follows:

$$F_N(x)=\frac{1}{1-x}\sum_{k=1}^N k!S(N,k)\left(\frac{x}{1-x}\right)^k$$

Which shows that $\frac{3}{4}F_N(1/4)=\sum_{k=1}^N k!S(N,k)\left(\frac{1}{3}\right)^k$.

EDIT: It turns out that there is a simple way to solve the recursion formula directly, by using generating functions. The recursion relation for arbitrary $x$ reads

$$\frac{1-x}{x}F_N(x)=\sum_{k=0}^{N-1}{N\choose k} F_k(x)$$

Now multiply by $y^N/N!$ and sum for $N\geq 1$. Define $S(y;x)=\sum_{N=1}^{\infty}F_N(x) y^N/N!$. Now it is easy to show that the recursion relation as posed leads to the following generating function

$$S(y;x)=F_0(x)\frac{\frac{x}{1-x}(e^y-1)}{1-\frac{x}{1-x}(e^y-1)}~~,~~ F_0(x)=(1-x)^{-1}$$

Now expand in powers of $e^y-1$, use the fact that $$(e^{y}-1)^k=k!\sum_{n=k}^{\infty}\frac{y^n}{n!}S(n,k)$$ and exchange the order of summation to obtain the desired result.