Minimal recurrences for binomial power sums

For every positive integer $r$, we prove that the least order of a polynomial-coefficient recurrence for $F_r(n)=\sum_{k=0}^n\binom nk^r$ is $\lfloor(r+1)/2\rfloor$. This establishes the unrestricted minimal-order assertion arising from Franel's work of 1894–1895. We also determine the least order $\lfloor r/2\rfloor$, for $r\geq2$, of the alternating sums $(-1)^n\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^r$. The lower bounds follow from real moment representations: every nonzero singularity of the representing measure forces a root of the leading characteristic polynomial of the recurrence. A common reflection argument gives telescoping recurrences attaining both bounds. For the ordinary sums, we combine the deformation of Straub and Zudilin with a shifted prime-power congruence to prove that the minimal shift operator is irreducible over \C(n).