Evaluating $S_{N} = \sum_{i=0}^\infty \frac{i^N}{4^i}$ using recursion 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.

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.
