Recurrence relation of order $n$: $f(n) = \dfrac{1}{k-1}\sum\limits_{i=1}^n {n \choose i} f(n-i)$.

Question

I came across this recurrence relation while looking for a closed form for $S(n,k) = \sum\limits_{i=0}^\infty \dfrac{i^n}{k^i}$.
After a few manipulations, I came across this recurrence relation: $f(n) = \dfrac{1}{k-1}\sum\limits_{i=1}^n {n \choose i}f(n-i)$, where $f(n) = S(n, k)$ for a fixed $k$.
Any standard recurrence relation solving method doesn't work.

Answer 1

Taking $k=1/x$, your function is a power series: $$ S(n,k)=\sum\limits_{i=0}^\infty\dfrac{i^n}{k^i}= \sum\limits_{i=0}^\infty{i^n}{x^i}=S(n,1/x)=f_n(x). $$ Maybe you are interested only in the $k\in{\Bbb N}$ case, but power series are a very powerful tool.

EDIT: $$f_0(x)=\sum\limits_{i=0}^\infty{x^i}={1\over 1-x}, $$

$$ f_0'(x)=\cdots $$

Answer 2

This is not really an answer to your question yet I will give you another way of calculation $S(n,k)$. Since $i^n = \left.d^n_x \exp(x i) \right|_{x=0}$ we have: \begin{equation} S(n,k) = \left.\frac{d^n}{ d x^n} \frac{k}{k - \exp(x)}\right|_{x=0} \end{equation} Now we can caluculate the derivative for $n=0,1,2,3,\dots$ and we quickly see a pattern: \begin{equation} S(n,k) = \left.\sum\limits_{p=1}^{n+1} \frac{a^{(n)}_p}{(k - \exp(x))^p} \right|_{x=0} \end{equation} where the coefficients satisfy a following recursion relation: \begin{equation} a^{(n)}_p = \left.-p a_p^{(n-1)}\right|_{p\le n} + \left.k(p-1) a_{p-1}^{(n-1)}\right|_{p\ge 2} \quad\mbox{for}\quad p=1,2,\dots,n+1 \end{equation} subject to $a^{(0)}_1 = 1$. We find closed form expressions for the coefficients: \begin{eqnarray} a^{(n)}_{n+1} &=& k^n n! \\ a^{(n)}_{n} &=& -\frac{1}{2} k^{n-1} (n+1)! \\ \vdots \end{eqnarray} In principle one can keep work out expressions downwards, ie by taking $p=n,n-1,n-2,\dots..$ and using the results calculated before. The challenge is , however to find a closed form expression for $a^{(n)}_p$ for arbitrary values of $p$ and $n$.