Let $\ R_o(q,n) = \sum_{i=1}^n q^i$, $\ R_1(q,n) = \sum_{i=1}^n i*q^i$, $\ R_2(q,n) = \sum_{i=1}^n i^2*q^i$ etc...
Prove that $\ R_k (q,n) = [n^k*q^{n+1}+\sum_{i=1}^k (-1)^i*\binom{k}{i}*R_{k-i}(q,n)]/(q-1)$
I have tried the following $\ (R_k=R_k(q,n))$. Let
$\ R_k = 1^k*q+2^k*q^2...+n^k*q^n$ (I)
$\ q*R_k = 1^k*q^2+...+n^k*q^{n+1}$ (II)
Subtracting (II) and (I) we get:
$\ (q-1)*R_k= -1^k*q-(2^k-1^k)*q^2-...-(n^k-(n-1)^k)*q^n+n^k*q^{n+1}$
Now, expanding the general term $\ (n-1)^k$ using the binomial theorem we have
$\ (n^k-(n-1)^k)=\sum_{i=1}^k \binom{k}{i}*(-1)^{i+1}*n^{k-i}$
And I got stocked here. Any ideas? Thanks.
Isolating the sum on the right hand side and changing the order of summation :
$$\sum_{i=1}^k (-1)^i{k\choose i}\sum_{m=1}^n m^{k-i}q^m=\sum_{m=1}^nq^m\sum_{i=1}^{n}(-1)^i{k\choose i} m^{k-i}\\=\sum_{m=1}^{n}q^l((l-1)^m-l^m)\\=qR_m(q,n-1)-R_m(q,n)\\=(q-1)R_m(q,n)-n^mq^{n+1}$$
which is what we wanted to show. Line 2 follows from the binomial theorem, line 3 from a trivial relabelling of indices and line 4 from the obvious identity $R_{m}(q,n-1)=R_m(q,n)-n^m q^n$.