Recurrences for sums of powers of binomial coefficients (Q1823940)

Let \(S_ n^{(r)}=\sum^{n}_{k=0}\left( \begin{matrix} n\\ k\end{matrix} \right)^ r\) \((r=1,2,...)\). An elementary method is given for finding recurrence relation for \(S_ n^{(r)}\) with \([(r+3)/2]\) terms. This confirms a conjecture of Franel. This method could easily be implemented on a computer and would require vastly less computation than Perlstadt's symbolic manipulation program MACSYMA. The recurrence relation obtained is of the type \(\sum^{k}_{j=0}b_ j^{(r)}(n)S^{(r)}_{n+1- j}=0.\) A closer examination of the proof would lead to determination of the degrees of the polynomials \(b_ j^{(r)}(n)\).