\documentclass[11pt]{amsart}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern,microtype}
\usepackage[a4paper,margin=27mm]{geometry}
\usepackage{amsmath,amssymb,mathtools,booktabs,needspace}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!40!black,citecolor=blue!40!black,urlcolor=blue!40!black]{hyperref}
\hypersetup{pdftitle={Minimal recurrences for binomial power sums},
  pdfauthor={Khai-Hoan Nguyen-Dang},
  pdfsubject={Franel recurrences, moment singularities and arithmetic of solutions}}
\setlength{\emergencystretch}{2em}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\DeclareMathOperator{\CT}{CT}
\DeclareMathOperator{\singsupp}{sing\,supp}
\DeclareMathOperator{\Diag}{Diag}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\den}{den}
\DeclareMathOperator{\lcm}{lcm}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\Z}{\mathbb Z}
\newcommand{\T}{\mathbb T}
\newcommand{\D}{\mathcal D}
\newcommand{\dd}{\mathrm d}
\newcommand{\Acal}{\mathcal A}
\numberwithin{equation}{section}
\title[Minimal recurrences for binomial power sums]{Minimal recurrences for binomial power sums}
\author{Khai-Hoan Nguyen-Dang}
\date{}

\begin{document}
\begin{abstract}
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)$. 
\end{abstract}
\subjclass[2020]{Primary 11B37; Secondary 05A10, 11B65, 33F10, 39A06}

\keywords{Generalized Franel numbers, binomial power sums, Ap\'ery limits}
\maketitle


\section{Introduction}\label{sec:introduction}

For a positive integer $r$, the sums
\begin{equation}\label{eq:franel}
 F_r(n)=\sum_{k=0}^{n}\binom nk^r,
 \qquad n=0,1,2,\ldots,
\end{equation}
form a classical family in the theory of polynomial-coefficient
recurrences. The first two cases are $F_1(n)=2^n$ and
$F_2(n)=\binom{2n}{n}$. Franel found second-order recurrences for
$F_3$ and $F_4$ in 1894 and 1895 and proposed a general form for the
recurrences \cite{Franel1894,Franel1895}. The order suggested by those
examples is
\[
 m_r=\left\lfloor\frac{r+1}{2}\right\rfloor.
\]
The present paper proves that this order is minimal for every $r$.
It also determines the corresponding orders for alternating binomial
power sums and proves irreducibility and arithmetic rigidity for the
ordinary Franel recurrences.

This long-standing problem is supported by a rich history of ideas and prior work. Perlstadt \cite{Perlstadt1987} computed recurrences for $r=5,6$,
and McIntosh \cite{McIntosh1989} treated $r\leq10$.
Cusick \cite{Cusick1989} proposed a general construction; Stoll
\cite{Stoll1997} identified a gap in its nonvanishing argument and
proved the upper bound $m_r$. Minimality is a separate question:
a recurrence obtained from a given summand need not be the shortest
recurrence of the sum. Earlier minimality results for $r=3,4,5,6$
are attributed to Schmidt and Yuan (1995) by Yuan Jin and Dickinson
\cite[p.~350]{YuanDickinson2000}. Yuan, Lu and Schmidt
\cite{YuanLuSchmidt2008} ruled out first-order recurrences for every
$r\geq3$. Straub and Zudilin \cite[Theorem~1.1]{StraubZudilin2023}
proved the lower bound $m_r$ for recurrences obtained by creative
telescoping from \eqref{eq:franel}. They also verified unrestricted
minimality computationally for $r\leq20$
\cite[Remark~4.1]{StraubZudilin2023}. Van Hoeij
\cite[\S5, Remark~6]{VanHoeij2025} subsequently obtained the
matching telescoping upper bound by polynomial reduction and reflection.
For more information, see Tonien's paper \cite{Tonien2026}.

To state the results clearly, we use the following conventions throughout. A recurrence of order $M$
for a sequence $u$ is an identity
\begin{equation}\label{eq:recurrence}
 \sum_{j=0}^{M}p_j(n)u(n+j)=0
 \qquad(n\text{ sufficiently large}),
 \qquad p_j\in\C[n],\quad p_0p_M\ne0.
\end{equation}
Rational-function coefficients give the same notion after clearing
denominators. Note that the order is the width of the shifts, not the degree of the coefficient polynomials. Two sequences define the same
\emph{eventual germ} if they agree for all sufficiently large indices. All solution spaces below are spaces of such germs. 

For a nonzero recurrence, put
\begin{equation}\label{eq:characteristic}
 D=\max_j\deg p_j,\qquad
 \chi(X)=\sum_j[n^D]p_j(n)X^j.
\end{equation}
We call $\chi$ its \emph{leading characteristic polynomial}. This
definition refers to the highest degree in $n$; its degree in $X$
can be smaller than the order of the recurrence.

The second family considered here is
\begin{equation}\label{eq:alternating}
 T_r(n)=(-1)^n\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^r
       =\sum_{k=-n}^{n}(-1)^k\binom{2n}{n+k}^r,
 \qquad r\geq2.
\end{equation}
Write $a_r=\lfloor r/2\rfloor$ and define the monic polynomials
\begin{align}
 H_r(X)&=\prod_{0\leq k<r/2}(X-\lambda_{r,k}),
 &\lambda_{r,k}&=(-1)^k\left(2\cos\frac{\pi k}{r}\right)^r,
 \label{eq:H}\\
 \widetilde H_r(X)&=\prod_{h=0}^{a_r-1}(X-\nu_{r,h}),
 &\nu_{r,h}&=\left(2\cos\frac{(2h+1)\pi}{2r}\right)^{2r}.
 \label{eq:Htilde}
\end{align}
The formula for $H_r$ also gives $H_1(X)=X-2$.

\begin{theorem}
\label{thm:orders}
The least recurrence orders of $F_r$ for $r\geq1$ and $T_r$ for
$r\geq2$ are respectively $m_r$ and $a_r$. Both bounds are attained over $\Q(n)$ by rational
telescoping of the displayed binomial summands.

Moreover, the polynomials $H_r$ and $\widetilde H_r$ belong to $\Z[X]$.
For every polynomial-coefficient recurrence of $F_r$, one has
$H_r\mid\chi$; for every such recurrence of $T_r$, one has
$\widetilde H_r\mid\chi$. 
\end{theorem}

In particular, at the minimum order
the corresponding leading characteristic polynomial is a nonzero
scalar multiple of $H_r$ or $\widetilde H_r$. The formula for $H_r$ determines the characteristic polynomial
discussed in \cite[\S7, Question~1]{VanHoeij2025}.
The divisibility assertion applies to every recurrence, regardless
of how it is obtained.

For the alternating sums, McIntosh \cite[Theorem~1]{McIntosh1993}
gave a construction of recurrences of order at most $a_r$ and
established sharpness when $r$ is prime or a power of $2$
\cite[Theorem~2]{McIntosh1993}.
His lower bound uses the algebraic degree of the dominant growth
constant. The proof here uses every nonzero critical value of a real
torus symbol, including values outside the Galois orbit of the dominant
one. This gives the same conclusion for all $r$.

Let $S$ denote the forward shift, $Su(n)=u(n+1)$, and let
\[
 \C(n)[S;\sigma],\qquad \sigma(c(n))=c(n+1),
 \qquad Sc(n)=c(n+1)S,
\]
be the shift Ore ring. Let $L_r\in\Q(n)[S;\sigma]$ be the monic
minimal operator of $F_r$. Here monic means that the coefficient of
$S^{m_r}$ is $1$.

\begin{theorem}[Irreducibility]\label{thm:irreducibility}
For every $r\geq1$, the operator $L_r$ is irreducible in
$\C(n)[S;\sigma]$.
\end{theorem}

Furthermore, one can show that every nonzero complex solution germ of $L_r$
has the same monic minimal annihilator $L_r$, and every annihilator
of that germ is a left multiple of $L_r$. For $r\geq3$, no nonzero
solution germ is hypergeometric over $\C(n)$.

We first establish minimality and then use the arithmetic congruence
to deduce irreducibility. The coefficient field in
Theorem~\ref{thm:irreducibility} is $\C(n)$; the automorphism fixes
the complex constants and sends $n$ to $n+1$.
Hypergeometric means $U(n+1)=a(n)U(n)$ on a tail for some
$a(n)\in\C(n)$.

The arithmetic of the other solutions is also rigid. A rational
sequence is \emph{globally bounded} on a tail if there are positive
integers $B,C$ such that $BC^nu(n)$ is integral for all sufficiently
large $n$. For a rational function $R(x_1,\ldots,x_d)$ regular at
the origin, its diagonal is
\[
 \Diag R(z)=\sum_{n\geq0}
 [x_1^n\cdots x_d^n]R(x_1,\ldots,x_d)z^n.
\]

\begin{theorem}[Rational solutions]\label{thm:rational-solutions}
Let $V_r$ be the rational-valued solution space of $L_r$. The limit
\[
 \mathcal L(U)=\lim_{n\to\infty}\frac{U(n)}{F_r(n)}
\]
exists for every $U\in V_r$ and gives a $\Q$-linear isomorphism
\begin{equation}\label{eq:limit-space}
 V_r\ \xrightarrow{\ \mathcal L\ }\ 
 \Q\oplus\Q\pi^2\oplus\cdots\oplus\Q\pi^{2m_r-2}.
\end{equation}
\end{theorem}

Note that within $V_r$, each of the following conditions describes exactly
the line $\Q F_r$: bounded denominators on a tail; denominators
involving only a fixed finite set of primes; global boundedness;
and a generating series which, modulo an element of $\Q[z]$, is the diagonal
of a rational function over $\Q$ regular at the origin.
For $r\geq2$, the integer-valued solution germs form the group
$\tfrac12\Z F_r$.

The explicit deformation and the values underlying
\eqref{eq:limit-space} are due to Straub and Zudilin
\cite[Theorem~1.3]{StraubZudilin2023}. Together with van Hoeij's
order bound, their independence already makes these solutions a
basis of the minimal telescoper. The unrestricted minimality proved
here identifies that operator with $L_r$.
A congruence at shifted prime powers then separates the basis
vectors arithmetically. The denominator growth can be read from
the limit itself: if a nonzero solution has
$\mathcal L(U)=P_U(\pi^2)$, with $P_U\in\Q[X]$ of degree less
than $m_r$, its common denominators through index $N$ have
logarithm $2\deg(P_U)N+o(N)$
(Theorem~\ref{thm:denominators}). This yields the classification
in Theorem~\ref{thm:rational-solutions}. For $r=3$, it also answers
the integer-sequence question of Schulte, VanSchalkwyk and Yang
\cite[Conjecture~4.5]{SchulteVanSchalkwykYang2014}; a short
independent proof is given in Corollary~\ref{cor:classical-integers}.

\subsection*{The two mechanisms}
The analytic part begins with a general observation. If
$u(n)=\int x^n\,\dd\mu(x)$ for a compactly supported measure,
then a recurrence for $u$ becomes a differential equation for $\mu$.
Away from zero, each point where $\mu$ fails to have a smooth density
must be a zero of $\chi$ (Proposition~\ref{prop:obstruction}).
Moment recurrences and differential equations have long been studied
together; relevant forms appear in Batenkov's work on piecewise
$D$-finite functions \cite[Theorems~2.9 and~2.13]{Batenkov2009}
and in the work of Bostan,
Elvey Price, Guttmann and Maillard on Stieltjes moment sequences
\cite[Theorem~3]{BostanElveyPriceGuttmannMaillard2020}.
The distributional formulation used here applies directly to
eventual recurrences and retains the exact polynomial $\chi$.

Franel already derived the $r=3$ recurrence from a double integral
\cite[p.~46]{Franel1894}. Here the measures are pushforwards of Haar
measure under explicit real Laurent polynomials. Every critical point
lying over a nonzero value is a nondegenerate extremum. At each such value the local
density contributions have the same sign and orientation, so they
cannot cancel. Counting these values proves the required lower bounds.
Essam and Guttmann \cite[\S III\,B]{EssamGuttmann1995} developed the
lattice-walk interpretation of $F_r$ and related its generating
function to Green functions of projected lattices. Our measure
is the spectral measure at the origin of a symmetric lattice-walk operator.
Its critical-value singularities are the density-of-states phenomenon studied by van Hove
\cite{VanHove1953}. The recurrence consequence uses the interior
critical values as well as the spectral edge.

The arithmetic part uses a different feature. After multiplication
by a suitable power of $p$, each deformation coefficient at $p+b$
reduces to a fixed nonzero multiple of $F_r(b)$. An annihilating
recurrence for any nonzero linear combination can therefore be
transferred to $F_r$. A finite-dimensional descent over $\Q$
makes this argument work for arbitrary complex coefficients
(Proposition~\ref{prop:transfer}). It proves irreducibility without
factoring the recurrence operator.

\subsection*{Organization}

Sections~\ref{sec:moments}--\ref{sec:telescoping} prove
Theorem~\ref{thm:orders}. Section~\ref{sec:arithmetic} develops the
congruence and proves Theorem~\ref{thm:irreducibility};
Section~\ref{sec:denominators} proves the arithmetic classification.
Appendix~\ref{sec:certificate} determines the exact dependence of a
minimal telescoping certificate on its summation variable, resolving
that part of the patterns recorded in
\cite[Remark~4.1]{StraubZudilin2023}.

\section{A singular-support bound for moment recurrences}
\label{sec:moments}

A distribution is smooth on an interval if it is given there by a
$C^\infty$ function times Lebesgue measure. Its singular support
is the complement of the largest open set on which it is smooth.
For a compactly supported distribution $\mu$, its moments
$\langle\mu,x^n\rangle$ are well-defined by inserting any smooth
cutoff equal to $1$ near its support.

\begin{proposition}\label{prop:obstruction}
Let $\mu$ be a compactly supported distribution on $\R$ and put
$u(n)=\langle\mu,x^n\rangle$. Suppose
\begin{equation}\label{eq:moment-recurrence}
 \sum_{j=0}^{M}p_j(n)u(n+j)=0\qquad(n\geq N),
 \qquad p_j\in\C[n],\quad (p_0,\ldots,p_M)\ne0.
\end{equation}
Here $N\in\Z_{\geq0}$. With $D$ and $\chi$ as in
\eqref{eq:characteristic},
\begin{equation}\label{eq:singular-support}
 \singsupp\mu\setminus\{0\}
 \subseteq\{x\in\R:\chi(x)=0\}.
\end{equation}
In particular, $M$ is at least the number of distinct nonzero
points of $\singsupp\mu$.
\end{proposition}

\begin{proof}
Use bilinear distribution pairing. The Euler operator
$E=x\,\dd/\dd x$ has formal transpose $E^*=-x\,\dd/\dd x-1$.
The compactly supported distribution
\[
 T=\sum_{j=0}^{M}p_j(E^*)(x^j\mu)
\]
satisfies $\langle T,x^n\rangle=0$ for $n\geq N$, since
$Ex^n=nx^n$. Every moment of $x^NT$ therefore vanishes.
The Fourier--Laplace transform of a compactly supported distribution
is entire, and its derivatives at zero are its moments, up to
nonzero constants. Thus the transform of $x^NT$ vanishes identically,
and uniqueness of the Fourier transform gives $x^NT=0$.
Consequently $T=0$ away from $0$.

The coefficient of $\mu^{(D)}$ in $T$ is
\[
 (-1)^D x^D\chi(x).
\]
Indeed, the highest derivative in $(E^*)^D(x^j\mu)$ has coefficient
$(-1)^Dx^{D+j}$. By definition of $D$, the polynomial $\chi$ is
nonzero. Near a point $x_0\ne0$ where $\chi(x_0)\ne0$, the equation
$T=0$ is a regular linear ordinary differential equation for $\mu$.
Its distributional solutions are smooth: for $D>0$, form the
first-order system for $(\mu,\mu',\ldots,\mu^{(D-1)})$ and multiply
by the inverse of a smooth fundamental matrix. The resulting
distributional vector has derivative zero and is constant.
For $D=0$, multiplication by a nonvanishing function forces $\mu$
to vanish locally. This proves \eqref{eq:singular-support}.
The last assertion follows from $\deg\chi\leq M$.
\end{proof}


The exclusion of $0$ is necessary: a distribution supported at $0$
can have all sufficiently high moments equal to zero. Positivity
is not required in the proposition. It enters through the following
criterion for a critical value to belong to the singular support.

\begin{lemma}\label{lem:morse}
Let $P$ be a smooth real function on a compact smooth manifold
without boundary of dimension $d\geq1$, equipped with a positive smooth density.
Let $\mu$ be its pushforward under $P$. Suppose that the critical
points in the fiber $P^{-1}(\lambda)$ form a nonempty finite set,
are all nondegenerate, and are all local maxima or all local minima.
Then $\lambda\in\singsupp\mu$.
\end{lemma}

\begin{proof}
Choose disjoint neighborhoods of these critical points and smooth
nonnegative cutoffs equal to $1$ near them. The Morse lemma gives
coordinates in which $P=\lambda+\eta|y|^2$, with the same
$\eta\in\{1,-1\}$ at every point. Polar integration shows that
the local pushforward density, with $t=\eta(x-\lambda)$, has the form
\begin{equation}\label{eq:morse-density}
 \mathbf1_{\{t>0\}}t^{d/2-1}h(t),
 \qquad h\in C^\infty([0,\epsilon)),\quad h(0)>0.
\end{equation}
The spherical average of the smooth coordinate density is a smooth
even function of the radius, hence a smooth function of its square.
This proves the asserted smoothness of $h$. The contribution
from the remainder of the manifold is smooth near $\lambda$, by
integration along regular level sets. Compactness and nondegeneracy
ensure that a sufficiently small neighborhood of $\lambda$ contains
no further critical points outside the chosen neighborhoods.

Adding the local terms preserves the form \eqref{eq:morse-density}
with positive $h(0)$. A one-sided power with exponent $d/2-1$ is
not smooth at zero: for an integer exponent a derivative has a
jump, and for a noninteger exponent a derivative is unbounded.
A smooth remainder cannot remove this defect. Hence $\mu$ is
not smooth at $\lambda$.
\end{proof}

\section{The real torus symbols and their critical values}
\label{sec:critical-values}

Fix $r\geq2$ and put $d=r-1$. On the torus $\T^d$, write
$z_j=e^{i\theta_j}$, $Z=z_1\cdots z_d$, and
\[
 A(z)=\prod_{j=1}^{d}(1+z_j),\qquad
 P=A+A(z^{-1})=A(1+Z^{-1}),\qquad
 Q=\frac{A-A(z^{-1})}{i}=\frac{A(1-Z^{-1})}{i}.
\]
Both $P$ and $Q$ are real-valued on the torus. With
$s=\theta_1+\cdots+\theta_d$, they become
\begin{equation}\label{eq:torus-symbols}
 P(\theta)=2^r\prod_{j=1}^{d}\cos(\theta_j/2)\cos(s/2),
 \qquad
 Q(\theta)=2^r\prod_{j=1}^{d}\cos(\theta_j/2)\sin(s/2).
\end{equation}
These products are periodic, despite the separate half-angle factors.
Let $\mu_r$ be the pushforward of normalized Haar measure under $P$,
and let $\widetilde\mu_r$ be its pushforward under $R=Q^2$.

\begin{lemma}\label{lem:representations}
For every $n\geq0$,
\begin{equation}\label{eq:moment-identities}
 F_r(n)=\CT P^n=\int x^n\,\dd\mu_r(x),
 \qquad
 T_r(n)=\CT Q^{2n}=\int x^n\,\dd\widetilde\mu_r(x).
\end{equation}
\end{lemma}

\begin{proof}
Expanding $(1+Z^{-1})^n$ gives
\[
 \CT P^n=\sum_{k=0}^{n}\binom nk\CT(A^nZ^{-k})
        =\sum_{k=0}^{n}\binom nk^r.
\]
Likewise,
\[
 \CT Q^{2n}=(-1)^n\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}
                   \CT(A^{2n}Z^{-k})=T_r(n).
\]
Constant terms are torus integrals against normalized Haar measure.
\end{proof}

\begin{lemma}\label{lem:critical-points}
The distinct nonzero critical values of $P$ are exactly
$\lambda_{r,k}$, $0\leq k<r/2$. At each such value all critical
points are nondegenerate extrema of the same type.
The distinct nonzero critical values of $R=Q^2$ are exactly
$\nu_{r,h}$, $0\leq h<a_r$. All critical points at these values
are nondegenerate local maxima.
\end{lemma}

\begin{proof}
At a point where $P\ne0$, all factors in \eqref{eq:torus-symbols}
are nonzero, and
\[
 \partial_{\theta_j}\log|P|
 =-\frac12\tan(\theta_j/2)-\frac12\tan(s/2).
\]
Thus all $\theta_j$ at a nonzero critical point are equal modulo
$2\pi$, say to $\theta$, and $r\theta\equiv0\pmod{2\pi}$.
The possible points are $\theta_j=2\pi k/r$, $0\leq k<r$;
the point with $\theta_j=\pi$, when present, has value zero and is
excluded. The value at every other point is
\[
 P=(-1)^k\left(2\cos\frac{\pi k}{r}\right)^r.
\]
The indices $k$ and $r-k$ give the same value. The representatives
$0\leq k<r/2$ have strictly decreasing absolute values, so they
give all the distinct nonzero critical values. At these points,
\begin{equation}\label{eq:ordinary-hessian}
 \operatorname{Hess}\log|P|
 =-\frac14\sec^2\left(\frac{\pi k}{r}\right)(I_d+J_d),
\end{equation}
where $J_d$ is the all-ones matrix. This matrix is negative definite.
Since $\operatorname{Hess}P=P\operatorname{Hess}\log|P|$ at a
critical point, a positive critical value is a nondegenerate maximum
and a negative one is a nondegenerate minimum.

For $Q\ne0$, the critical equations instead read
\[
 \partial_{\theta_j}\log|Q|
 =-\frac12\tan(\theta_j/2)+\frac12\cot(s/2)=0.
\]
They force $\theta_j=(2h+1)\pi/r$, $0\leq h<r$.
Writing $\alpha=(2h+1)\pi/(2r)$, one obtains
\[
 Q=(-1)^h(2\cos\alpha)^r,
 \qquad
 \operatorname{Hess}\log|Q|
 =-\frac14\sec^2\alpha\,(I_d+J_d).
\]
When $r$ is odd, the point with $\theta_j=\pi$ has value zero
and is excluded. Since $\nabla R=2Q\nabla Q$, there are no other
nonzero critical points of $R$. At every such point,
$\operatorname{Hess}R=2Q^2\operatorname{Hess}\log|Q|$ is negative
definite. Pairing $h$ with $r-1-h$ leaves precisely the distinct
values $\nu_{r,h}$ in \eqref{eq:Htilde}.
\end{proof}

Lemmas~\ref{lem:morse} and \ref{lem:critical-points} show that each
$\lambda_{r,k}$ belongs to $\singsupp\mu_r$ and each $\nu_{r,h}$
belongs to $\singsupp\widetilde\mu_r$. Proposition~\ref{prop:obstruction}
therefore proves the divisibilities in Theorem~\ref{thm:orders} and
the lower bounds $m_r$ and $a_r$. The case $r=1$ follows directly
from $F_1(n)=2^n$: its recurrence implies
$\sum_jp_j(n)2^j=0$, hence $\chi(2)=0$.

\begin{lemma}\label{lem:integral-characteristics}
One has $H_r,\widetilde H_r\in\Z[X]$.
\end{lemma}

\begin{proof}
For $z^r=1$, the values $(1+z)^r$ are precisely the critical values
of $P$, with the possible additional value zero. Inversion pairs
the equal values; the value at $z=1$ is unpaired. Thus the distinct
nonzero values form the root set of $H_r$. They are algebraic
integers and this set is stable under the Galois group of the
cyclotomic field. The coefficients of $H_r$ are consequently
rational algebraic integers.

Similarly, for $z^r=-1$, the values $-(1+z)^{2r}$ are precisely
the roots of $\widetilde H_r$, with each nonzero value counted twice
and the additional value zero when $r$ is odd. The same argument
proves the assertion for $\widetilde H_r$.
\end{proof}

Some small cases illustrate the two spectra:
\begin{center}
\begin{tabular}{c@{\qquad}ll}
\toprule
$r$&$H_r(X)$&$\widetilde H_r(X)$\\
\midrule
2&$X-4$&$X-4$\\
3&$(X-8)(X+1)$&$X-27$\\
4&$(X-16)(X+4)$&$X^2-136X+16$\\
5&$(X-32)(X^2+11X-1)$&$X^2-625X+3125$\\
6&$(X-64)(X+27)(X-1)$&$(X-64)(X^2-2702X+1)$\\
\bottomrule
\end{tabular}
\end{center}

The positive roots of $\widetilde H_r$ also give a sparsity bound:
every recurrence of $T_r$ has at least $a_r+1$ coefficient
polynomials of maximal degree. Indeed, a nonzero real or imaginary
part of $\chi$ has the $a_r$ distinct positive roots $\nu_{r,h}$,
so Descartes' rule of signs requires at least $a_r+1$ nonzero
monomials. In particular, every coefficient of a minimum-order
alternating recurrence has maximal degree. For a minimum-order
ordinary recurrence, both endpoint coefficients have maximal degree,
since $H_r$ is monic and has nonzero constant coefficient.

\begin{remark}\label{rem:positivity}
The representation of $T_r$ makes it a Stieltjes moment sequence
with support exactly $[0,\nu_{r,0}]$. Indeed, the continuous image
of the connected torus under $Q^2$ is this interval, and the inverse
image of every open interval meeting it has positive Haar measure.
Consequently all its Hankel minors with strictly increasing row
and column indices are positive. To see the strictness, the
determinant integration identity expresses such a minor as
\[
 \frac1{s!}\int
   \det[x_\ell^{a_i}]_{i,\ell=1}^{s}
   \det[x_\ell^{b_j}]_{j,\ell=1}^{s}
   \prod_{\ell=1}^{s}\dd\widetilde\mu_r(x_\ell),
\]
where $a_i$ and $b_j$ are strictly increasing nonnegative integers.
Both generalized Vandermonde determinants are positive when
$0<x_1<\cdots<x_s$, and their product is nonnegative everywhere.
Full support gives strict positivity of the integral. In particular,
the ratios $T_r(n+1)/T_r(n)$ increase strictly to $\nu_{r,0}$.
These are standard consequences of the moment representation;
the recurrence lower bound requires its additional interior
singularities.
\end{remark}

\section{A common telescoping construction}\label{sec:telescoping}

We give a common proof of the matching upper bounds. The ordinary
case follows the reduction and reflection argument of van Hoeij
\cite[\S5, Remark~6]{VanHoeij2025}. The signed formulation below
also treats the alternating sums and verifies the certificate boundary
terms. In particular, a minimum-order recurrence of $F_r$ telescopes
the original summand, as required for the deformation theorem used
in Section~\ref{sec:arithmetic}. Write
$(x)_j=x(x+1)\cdots(x+j-1)$, with $(x)_0=1$.

\begin{lemma}\label{lem:unified-telescoping}
Let $r\geq2$ and $\varepsilon\in\{1,-1\}$, and put
\[
 q_\varepsilon=\begin{cases}1,&\varepsilon=1,\\2,&\varepsilon=-1,\end{cases}
 \qquad
 m_\varepsilon=\begin{cases}
 \lfloor(r+1)/2\rfloor,&\varepsilon=1,\\
 \lfloor r/2\rfloor,&\varepsilon=-1.
 \end{cases}
\]
There exist $p_0,\ldots,p_{m_\varepsilon}\in\Q[n]$, not all zero,
and $C\in\Q(n,k)$ such that, for
$f_\varepsilon(n,k)=\varepsilon^k\binom nk^r$,
\begin{equation}\label{eq:unified-telescoper}
 \sum_{a=0}^{m_\varepsilon}p_a(n)
       f_\varepsilon(n+q_\varepsilon a,k)
 =C(n,k+1)f_\varepsilon(n,k+1)-C(n,k)f_\varepsilon(n,k).
\end{equation}
For all sufficiently large nonnegative integers $n$, the certificate
product has well-defined, finitely supported values on $k\in\mathbb Z$,
with removable singularities interpreted by continuation. Its bilateral
forward difference therefore sums to zero.
\end{lemma}

\begin{proof}
Work over $K=\Q(n)$ and set
\[
 \D_\varepsilon C(k)
 =\varepsilon\left(\frac{n-k}{k+1}\right)^rC(k+1)-C(k),
 \qquad
 Q_j(k)=\frac{(n+1)_j^r}{(n-k+1)_j^r}.
\]
Brackets denote classes modulo $\D_\varepsilon K(k)$. We will bound
only the span of the selected shift classes $[Q_{q_\varepsilon a}]$.

First remove the poles of $Q_j$ from right to left. If the rightmost
remaining pole is $k=n+h$, write its principal part as
$A(k)/(n-k+h)^r$, with $\deg_k A<r$. Since $k^r$ is invertible
modulo $(n-k+h)^r$ in $K[k]$, choose $H\in K[k]$, $\deg H<r$, with
\[
 k^rH(k)\equiv A(k)\pmod{(n-k+h)^r}.
\]
For $V_h(k)=k^rH(k)/(n-k+h)^r$ one has
\[
 \D_\varepsilon V_h(k)
 =\varepsilon\frac{(n-k)^rH(k+1)}{(n-k+h-1)^r}
       -\frac{k^rH(k)}{(n-k+h)^r}.
\]
Adding this expression cancels the pole at $n+h$ and introduces at
most a pole at $n+h-1$; for $h=1$ its first term is polynomial.
Thus $P_j=Q_j+\D_\varepsilon U_j$ is polynomial, where $U_j$ is a
finite sum of such $V_h$. For $j=0$ take $P_0=1$ and $U_0=0$.

Each $V_h$ is $O(k^{r-1})$ at infinity. If
$\varepsilon(-1)^r=1$, the multiplier in $\D_\varepsilon$ is
$1+O(k^{-1})$, so the leading terms cancel and
$\D_\varepsilon V_h=O(k^{r-2})$. Otherwise it is
$-1+O(k^{-1})$, giving $\D_\varepsilon V_h=O(k^{r-1})$.
Since $Q_j$ is proper for $j\geq1$, in both cases
\[
 \deg P_j<b_\varepsilon,
 \qquad
 b_\varepsilon=r-\mathbf1_{\{\varepsilon(-1)^r=1\}}.
\]

Let $JC(k)=C(n-k)$. Direct substitution gives
\[
 J\D_\varepsilon C=\D_\varepsilon C^\star,
 \qquad
 C^\star(k)=-\varepsilon
       \left(\frac{k}{n-k+1}\right)^r C(n-k+1).
\]
Hence $J$ induces an involution on the quotient. Moreover,
\[
 \varepsilon^jJQ_j-Q_j=\D_\varepsilon B_j,
 \qquad
 B_j(k)=\sum_{\ell=0}^{j-1}
 \frac{\varepsilon^\ell(n+1)_j^r}
 {(k+1)_\ell^r(n-k+1)_{j-\ell}^r}.
\]
Indeed, after multiplication by $f_\varepsilon(n,k)$, this is the
telescoping sum of the $j$ consecutive shifts in $k$ of
$f_\varepsilon(n+j,k)$.
For $j=q_\varepsilon a$ one has $\varepsilon^j=1$. Consequently
\[
 S_j=\frac{P_j+JP_j}{2},
 \qquad
 Q_j-S_j=-\frac12\D_\varepsilon
                   (U_j+U_j^\star+B_j).
\]
The polynomial $S_j$ is even in $k-n/2$ and has degree less than
$b_\varepsilon$. Such polynomials form a space of dimension
$\lceil b_\varepsilon/2\rceil=m_\varepsilon$, with basis
\[
 1,(k-n/2)^2,\ldots,(k-n/2)^{2(m_\varepsilon-1)}.
\]
Thus the $m_\varepsilon+1$ representatives
$S_0,S_{q_\varepsilon},\ldots,S_{q_\varepsilon m_\varepsilon}$
are linearly dependent over $K$. The displayed certificate identity,
followed by clearing denominators in $n$, gives
\eqref{eq:unified-telescoper}.

For the boundary assertion, specialize $n=N$ to a sufficiently large
nonnegative integer, avoiding all parameter poles in the finitely many
rational functions used above. Put $\delta=(1-\varepsilon)/2$ and use
the entire continuation in $k$
\[
 f_\varepsilon(N,k)=e^{i\pi\delta k}
 \left\{\frac{\Gamma(N+1)}{\Gamma(k+1)\Gamma(N-k+1)}\right\}^{r}.
\]
It has zeros of order $r$ at every integer outside $[0,N]$.
Therefore $V_hf_\varepsilon$ has a removable singularity at its
only possible pole $k=N+h$, and its integer values have finite support.
The reflected certificate is explicitly
\[
 V_h^\star(k)=-\varepsilon
       \frac{k^rH(N-k+1)}{(k+h-1)^r}.
\]
It is polynomial when $h=1$; otherwise its sole possible pole is the
negative integer $1-h$, again canceled by a zero of order $r$.
Finally,
\[
 B_j(k)f_\varepsilon(N,k)
 =\sum_{\ell=0}^{j-1}f_\varepsilon(N+j,k+\ell),
\]
whose integer values also have finite support. Every certificate in
the construction is a finite linear combination of these products.
Their bilateral forward differences consequently sum to zero.
\end{proof}

\begin{proof}[Completion of the proof of Theorem~\ref{thm:orders}]
For $\varepsilon=1$, bilateral summation in
Lemma~\ref{lem:unified-telescoping} gives a nonzero recurrence of
order at most $m_r$ for $F_r$. For $\varepsilon=-1$, specialize
the parameter to $2n$ and use
\[
 \sum_k f_{-1}(2n+2j,k)=(-1)^{n+j}T_r(n+j).
\]
The resulting recurrence is
$\sum_{j=0}^{a_r}(-1)^jp_j(2n)T_r(n+j)=0$ and has order at most
$a_r$. Nonzero polynomial coefficients remain nonzero under the
substitution $n\mapsto2n$. If either endpoint vanished, translating
the index would give a recurrence of smaller width, contrary to the
lower bounds proved in Section~\ref{sec:critical-values}.
The divisibility already proved then gives $\chi=cH_r$ or
$c\widetilde H_r$ at the minimum order. For $r=1$, the identity
$F_1(n+1)=2F_1(n)$ supplies the upper bound. Its normalized
certificate is $-k/(n-k+1)$, whose product with $\binom nk$ is
$-\binom n{k-1}$ and has finite support on the integer lattice.
\end{proof}

\section{The deformation and its arithmetic}
\label{sec:arithmetic}

\subsection{A deformation theorem}

Define the even rational function
\begin{equation}\label{eq:deformation}
 \Acal_r(n,t)=\sum_{k=0}^{n}\binom nk^r
 \left\{\prod_{h=1}^{k}\left(1-\frac th\right)
        \prod_{h=1}^{n-k}\left(1+\frac th\right)\right\}^{-r}
 =\sum_{j\geq0}A_{r,j}(n)t^{2j}.
\end{equation}
Empty products are $1$. Evenness follows by replacing $k$ by
$n-k$, and every $A_{r,j}(n)$ is rational. In particular,
$A_{r,0}=F_r$. We use the following result with its original
attribution.

\begin{theorem}[Straub--Zudilin, {\cite[Theorems~1.3 and~3.1]{StraubZudilin2023}}]
\label{thm:SZ}
Every recurrence over $\Q(n)$ obtained by rational telescoping from
$\binom nk^r$ is solved, for all sufficiently large $n$, by
$A_{r,j}$ for $2j<r$. For every $j\geq0$,
\begin{equation}\label{eq:SZ-limits}
 \lim_{n\to\infty}\frac{A_{r,j}(n)}{F_r(n)}
 =\phi_{r,j}\pi^{2j},\qquad
 \phi_{r,j}=[t^{2j}]\left(\frac{t}{\sin t}\right)^r
 \in\Q_{>0}.
\end{equation}
\end{theorem}

The telescoping construction in Section~\ref{sec:telescoping} and
minimality show that $A_{r,0},\ldots,A_{r,m_r-1}$ solve $L_r$.
The case $r=1$ is immediate from $A_{1,0}(n)=2^n$.
Independence follows from these limits and the transcendence of $\pi$,
as in \cite[proof of Theorem~1.1]{StraubZudilin2023}. We give an
arithmetic proof as part of a congruence that will control denominators
and annihilators.

\subsection{One congruence at shifted prime powers}

Write $v_p$ for the valuation normalized by $v_p(p)=1$, with
$v_p(0)=+\infty$, and
$\Z_{(p)}=\{x\in\Q:v_p(x)\geq0\}$.
Congruences of formal power series are coefficientwise. Put
$\ell_n=\lcm(1,\ldots,n)$ for $n\geq1$, and $\ell_0=1$.

\begin{lemma}\label{lem:arithmetic-scaling}
For every $r\geq1$ and $n\geq0$,
\begin{equation}\label{eq:integral-scaling}
 \Acal_r(n,\ell_nt)\in\Z[[t]].
\end{equation}
For any prime $p$ and integers $\alpha\geq1$ and $0\leq b<p$,
the series $\Acal_r(p^\alpha+b,p^\alpha t)$ lies in
$\Z_{(p)}[[t]]$ and
\begin{equation}\label{eq:prime-power-series}
 \Acal_r(p^\alpha+b,p^\alpha t)
 \equiv F_r(b)\bigl((1-t)^{-r}+(1+t)^{-r}\bigr)\pmod p.
\end{equation}
Consequently, for every $j\geq0$,
\begin{equation}\label{eq:prime-power-coefficients}
 \ell_n^{2j}A_{r,j}(n)\in\Z,\qquad
 p^{2j\alpha}A_{r,j}(p^\alpha+b)
 \equiv C_{r,j}F_r(b)\pmod p,
 \quad C_{r,j}=2\binom{r+2j-1}{2j}.
\end{equation}
For fixed $r,j,b$, one has
$v_p(A_{r,j}(p^\alpha+b))=-2j\alpha$ for all sufficiently large
primes $p$, uniformly in $\alpha\geq1$.
\end{lemma}

\begin{proof}
Replacing $t$ by $\ell_nt$ in \eqref{eq:deformation} makes every
factor $(1\pm\ell_nt/h)^{-r}$ an integral formal power series.
This proves \eqref{eq:integral-scaling}.

Put $N=p^\alpha+b<2p^\alpha$. For $1\leq h\leq N$ one has
$v_p(h)\leq\alpha$. The only index with valuation $\alpha$ is
$h=p^\alpha$. After replacing $t$ by $p^\alpha t$, every factor
therefore lies in $\Z_{(p)}[[t]]$, and every factor except the
one with $h=p^\alpha$ is congruent to $1$ modulo $p$.
The identity
\[
 (1+x)^N\equiv(1+x^{p^\alpha})(1+x)^b\pmod p
\]
shows that the summands with $b<k<p^\alpha$ vanish modulo $p$.
For $0\leq k\leq b$, the exceptional factor occurs in the second
product and gives $(1+t)^{-r}$, while
$\binom Nk\equiv\binom bk\pmod p$. For
$k=p^\alpha+q$, $0\leq q\leq b$, it occurs in the first product
and gives $(1-t)^{-r}$, while
$\binom N{p^\alpha+q}\equiv\binom bq\pmod p$.
Summing proves \eqref{eq:prime-power-series}.
Coefficient extraction gives \eqref{eq:prime-power-coefficients}.
Its right side is a fixed nonzero integer, so it is a unit at all
sufficiently large primes. This proves the valuation assertion.
\end{proof}

\begin{proposition}\label{prop:basis}
The eventual germs $A_{r,0},\ldots,A_{r,m_r-1}$ form a basis
of the rational solution space of $L_r$ over $\Q$ and of the
complex solution space over $\C$. The limit map in
\eqref{eq:limit-space} is a $\Q$-linear isomorphism.
\end{proposition}

\begin{proof}
In fact, every finite collection $A_{r,0},\ldots,A_{r,J}$ is
linearly independent over $\Q$ as eventual germs. In a nonzero
proposed relation, let $J$ be the highest index with nonzero
coefficient. For every sufficiently large prime $p$, all its
nonzero rational coefficients are $p$-adic units, and
Lemma~\ref{lem:arithmetic-scaling} with $b=0$, $\alpha=1$ gives
distinct valuations $-2j$ for the summands at index $p$.
The term with smallest valuation, at $j=J$, cannot cancel.

Choose $N$ beyond the poles and the zeros of the endpoint
coefficients of $L_r$, and beyond the index from which all
$A_{r,j}$ with $j<m_r$ satisfy that recurrence. Its order $m_r$ recurrence determines a
solution on this tail from $m_r$ consecutive values. The matrix
\[
 \bigl[A_{r,j}(N+i)\bigr]_{0\leq i,j<m_r}
\]
is nonsingular over $\Q$: otherwise a nonzero rational combination
would have $m_r$ consecutive zero values and would vanish on a
tail, contradicting independence. Its inverse has rational entries.
Thus the same sequences give both asserted bases.

For $U=\sum_jc_jA_{r,j}$, $c_j\in\Q$, Theorem~\ref{thm:SZ}
gives $\mathcal L(U)=\sum_jc_j\phi_{r,j}\pi^{2j}$.
The numbers $\phi_{r,j}$ are nonzero rationals, and the powers
$1,\pi^2,\ldots,\pi^{2m_r-2}$ are linearly independent over
$\Q$ by the transcendence of $\pi$. This proves the isomorphism.
\end{proof}

\subsection{Transferring annihilators}

The shifted congruence supplies more than independence. It transfers
an annihilator of any nonzero combination of the deformation
coefficients to the undeformed sequence. The following proof treats
complex constants directly.

\begin{proposition}\label{prop:transfer}
Fix $r\geq1$ and suppose, on a tail,
\[
 U=\sum_{j=0}^{J}c_jA_{r,j},\qquad c_j\in\C,\quad c_J\ne0.
\]
If $Q=\sum_{\ell=0}^{d}q_\ell(n)S^\ell$, $q_\ell\in\C[n]$, annihilates
$U$ eventually, then
\begin{equation}\label{eq:transfer}
 \sum_{\ell=0}^{d}q_\ell(b)F_r(b+\ell)=0\qquad(b\in\Z_{\geq0}).
\end{equation}
Every annihilator of $U$ in $\C(n)[S;\sigma]$ therefore also
annihilates $F_r$ eventually.
\end{proposition}

\begin{proof}
The case $Q=0$ is immediate. Otherwise choose a $\Q$-basis
$\beta_1,\ldots,\beta_t$ of the finite-dimensional $\Q$-vector
space spanned by all products $c_j[n^h]q_\ell(n)$. Write
\[
 c_jq_\ell(n)=\sum_{i=1}^{t}\beta_iq_{i,j,\ell}(n),
 \qquad q_{i,j,\ell}\in\Q[n].
\]
For every sufficiently large integer $n$, the identity $QU(n)=0$
becomes
\[
 \sum_{i=1}^{t}\beta_i
 \left(\sum_{j=0}^{J}\sum_{\ell=0}^{d}
 q_{i,j,\ell}(n)A_{r,j}(n+\ell)\right)=0.
\]
Each parenthesized expression is rational. Independence of the
$\beta_i$ over $\Q$ makes each expression zero separately.

Fix $b\geq0$. Evaluate these rational identities at $n=p+b$,
where $p>b+d$ is a sufficiently large prime avoiding all
coefficient denominators. Multiply by $p^{2J}$ and reduce modulo
$p$. By \eqref{eq:prime-power-coefficients}, the terms with $j<J$
vanish, leaving
\[
 C_{r,J}\sum_{\ell=0}^{d}q_{i,J,\ell}(b)F_r(b+\ell)\equiv0\pmod p.
\]
Here $q_{i,j,\ell}(p+b)\equiv q_{i,j,\ell}(b)\pmod p$.
The displayed rational number is independent of $p$ and is
divisible by infinitely many primes, so it is zero. Multiplying
by $\beta_i$ and summing over $i$, then canceling
$C_{r,J}c_J\ne0$, gives \eqref{eq:transfer}.
For rational-function coefficients, first clear their polynomial
denominators in $n$, which preserves annihilation on a tail.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:irreducibility}]
Suppose that $L_r=BR$ in $\C(n)[S;\sigma]$ with
$0<\ord R<m_r$. The constant coefficient of $R$ is nonzero,
because the constant coefficient of $L_r$ is nonzero. Beyond the
finitely many poles and endpoint zeros of $R$, nonzero initial
data give a nonzero solution germ $U$ of $R$: forward and backward
uniqueness prevent it from vanishing eventually. Then $L_rU=0$,
so Proposition~\ref{prop:basis} expresses $U$ as a nonzero complex
combination of $A_{r,0},\ldots,A_{r,m_r-1}$.
Proposition~\ref{prop:transfer} gives $RF_r=0$, contrary to the
minimal order $m_r$. This proves irreducibility.

For any nonzero solution germ $U$ of $L_r$ and any annihilator
$Q$ of $U$, Proposition~\ref{prop:transfer} gives $QF_r=0$.
Right division by the monic operator $L_r$ writes
$Q=HL_r+R$ with $\ord R<m_r$; this is the usual division
algorithm in the shift Ore ring \cite{Ore1933}. Since $RF_r=0$,
minimality forces $R=0$. Finally, a nonzero hypergeometric germ
has an annihilator $S-a(n)$ with $a(n)\in\C(n)$, impossible
when $r\geq3$ and $m_r\geq2$.
\end{proof}

\subsection{The rate of convergence of solution ratios}

The characteristic roots also give a uniform exponential rate for
the limits. This concerns complex solutions as well as rational ones.

\begin{corollary}\label{cor:perron}
For $r\geq3$ and every complex solution germ $U$ of $L_r$, the
limit $\mathcal L(U)=\lim U(n)/F_r(n)$ exists and
\begin{equation}\label{eq:ratio-rate}
 \limsup_{n\to\infty}
 \left|\frac{U(n)}{F_r(n)}-\mathcal L(U)\right|^{1/n}
 \leq\cos^r\left(\frac{\pi}{r}\right).
\end{equation}
For $r=1,2$, every solution germ is a constant multiple of $F_r$.
\end{corollary}

\begin{proof}
After clearing denominators, divide a minimum-order recurrence by
its coefficient of $S^{m_r}$. Theorem~\ref{thm:orders} shows that
the resulting coefficients tend to those of $H_r$, and the
trailing coefficient is nonzero on a sufficiently late tail.
The roots $\lambda_{r,k}$ are nonzero with distinct absolute
values. Perron's theorem \cite{Perron1909}, in the form stated in
\cite[\S4]{ChamberlandStraub2021}, therefore gives a basis of
solutions with successive ratios tending to $\lambda_{r,k}$.
The elementary bounds
\[
 \frac{2^{rn}}{(n+1)^{r-1}}\leq F_r(n)\leq2^{rn}
\]
show that $F_r(n)^{1/n}\to2^r=\lambda_{r,0}$, so $F_r$ has a
nonzero component in the dominant basis direction. Subtracting
the corresponding multiple of $F_r$ from $U$ leaves only the
other directions, whose largest exponential modulus is
$(2\cos(\pi/r))^r$. This proves \eqref{eq:ratio-rate}.
\end{proof}

\section{Denominators, diagonals and integer solutions}
\label{sec:denominators}

\subsection{Exact denominator growth}

For $x\in\Q$, let $\den(x)$ be its positive denominator in
lowest terms, with $\den(0)=1$. Fix an initial index $N_0\geq1$
from which the displayed basis expansion of the rational germ holds,
and put
\begin{equation}\label{eq:common-denominator}
 D_U(N)=\lcm\{\den(U(n)):N_0\leq n\leq N\}.
\end{equation}
Changing finitely many terms changes $\log D_U(N)$ by at most a
constant for all sufficiently large $N$, and hence does not affect
its exponential growth rate.
Write
$\psi(N)=\log\ell_N=\sum_{p^\alpha\leq N}\log p$.

\begin{theorem}\label{thm:denominators}
Let
\[
 U(n)=\sum_{j=0}^{J}c_jA_{r,j}(n),
 \qquad c_j\in\Q,\quad c_J\ne0,
\]
on the chosen tail. There are a finite set of primes $\mathcal S$
and an integer $B\geq1$ such that
\begin{align}
 v_p(U(p^\alpha))&=-2J\alpha
 &&(p\notin\mathcal S,\ \alpha\geq1),
 \label{eq:valuation-U}\\
 v_p(D_U(N))&=2J\lfloor\log_pN\rfloor
 &&(p\notin\mathcal S,\ N\geq N_0),
 \label{eq:valuation-D}
\end{align}
and
\begin{equation}\label{eq:denominator-growth}
 D_U(N)\mid B\ell_N^{2J},\qquad
 \log D_U(N)=2J\psi(N)+O_{U,N_0}(\log N).
\end{equation}
In particular,
\begin{equation}\label{eq:denominator-rate}
 \lim_{N\to\infty}\frac{\log D_U(N)}{N}=2J.
\end{equation}
\end{theorem}

\begin{proof}
Choose $B$ with $Bc_j\in\Z$ for every $j$. By
\eqref{eq:integral-scaling}, $B\ell_n^{2J}U(n)$ is integral,
which gives the divisibility in \eqref{eq:denominator-growth}.
Let $\mathcal S$ contain all primes at most $N_0$, the divisors
of $B$ and $C_{r,J}$, and the prime divisors of the numerator of
$c_J$ in lowest terms. Outside this finite set, $c_J$ is a unit
and the other $c_j$ are integral. At $n=p^\alpha$, the term
with $j=J$ has valuation exactly $-2J\alpha$ by
\eqref{eq:prime-power-coefficients}; every lower term has strictly
larger valuation. This proves \eqref{eq:valuation-U}.

For $p\notin\mathcal S$, the divisibility bound gives
$v_p(D_U(N))\leq2J\lfloor\log_pN\rfloor$.
If $p\leq N$, choose $\alpha=\lfloor\log_pN\rfloor$.
Then $N_0<p\leq p^\alpha\leq N$, so
\eqref{eq:valuation-U} gives the matching lower bound. If $p>N$,
both sides are zero. This proves \eqref{eq:valuation-D}.
Only the fixed exceptional primes can contribute to
$\log D_U(N)-2J\log\ell_N$, and each contributes $O(\log N)$.
Finally, the prime number theorem gives $\psi(N)\sim N$.
\end{proof}

For the solution space of $L_r$, Proposition~\ref{prop:basis}
shows that the possible nonzero-solution rates in
\eqref{eq:denominator-rate} are exactly
$0,2,\ldots,2m_r-2$. More precisely, the solutions with rate at
most $2J$ form
\[
 \operatorname{span}_{\Q}\{A_{r,0},\ldots,A_{r,J}\},
 \qquad 0\leq J<m_r.
\]
Equivalently, write the Ap\'ery limit uniquely as
$\mathcal L(U)=P_U(\pi^2)$, where $P_U\in\Q[X]$ and
$\deg P_U<m_r$. For every nonzero $U\in V_r$,
\begin{equation}\label{eq:limit-degree}
 \lim_{N\to\infty}\frac{\log D_U(N)}{N}=2\deg P_U.
\end{equation}
Indeed, \eqref{eq:SZ-limits} gives
$P_U(X)=\sum_jc_j\phi_{r,j}X^j$, and each $\phi_{r,j}$ is
nonzero. Thus the arithmetic filtration agrees with the polynomial
degree of the Ap\'ery limit.

\subsection{The globally bounded direction}

\begin{proof}[Proof of the arithmetic assertions in
Theorem~\ref{thm:rational-solutions}]
Write a nonzero rational solution in the basis of
Proposition~\ref{prop:basis}, and let $J$ be its highest nonzero
index. If $J=0$, it is a rational multiple of $F_r$ and has
bounded denominators. If $J>0$, equation \eqref{eq:valuation-U}
with $\alpha=1$ shows that its denominator at index $p$ is
divisible by $p^{2J}$ for every sufficiently large prime $p$.
It therefore has neither bounded denominators nor a fixed finite
set of denominator primes. It cannot be globally bounded, since
for $p\nmid BC$ multiplication by $BC^p$ does not change this
negative valuation.

Every diagonal of a rational function over $\Q$ regular at the
origin is globally bounded. For completeness, write that function
as $P(\boldsymbol x)/Q(\boldsymbol x)$ with integral polynomials
and $Q(0)=a\ne0$. The series $H=1-Q/a$ has zero constant term,
and
\[
 \frac P Q=\frac P a\sum_{q\geq0}H^q.
\]
A monomial of total degree $h$ receives terms only from $q\leq h$,
so its coefficient has denominator dividing $a^{h+1}$. A diagonal
in $d$ variables is consequently made integral by multiplying its
$n$th coefficient by $a(a^d)^n$; absolute values may be used to
make these scaling integers positive. A polynomial change affects
only a finite common denominator. Hence a diagonal solution germ
belongs to $\Q F_r$.
Conversely,
\begin{equation}\label{eq:diagonal}
 \sum_{n\geq0}F_r(n)z^n
 =\Diag\frac{1}{(1-x_1)\cdots(1-x_r)-x_1\cdots x_r}.
\end{equation}
Indeed, geometric expansion gives
$\sum_{k\geq0}(x_1\cdots x_r)^k
 \prod_i(1-x_i)^{-k-1}$, whose diagonal coefficient is
$\sum_{k=0}^{n}\binom nk^r$. Rational multiples are again
rational diagonals.

It remains to determine the integer lattice for $r\geq2$.
For every $N\geq1$,
\begin{equation}\label{eq:gcd-tail}
 \gcd\{F_r(n):n\geq N\}=2.
\end{equation}
Pairing the summands with indices $k$ and $n-k$ shows that
$F_r(n)$ is even for $n\geq1$: when $n=2h$, the unpaired
coefficient $\binom{2h}{h}=2\binom{2h-1}{h-1}$ is also even.
For every prime $p$, all interior coefficients
$\binom{p^\alpha}{k}$ are divisible by $p$. Thus
$F_r(p^\alpha)\equiv2\pmod p$, excluding all odd primes from
the gcd, and $F_r(2^\alpha)\equiv2\pmod4$ because $r\geq2$.
This proves \eqref{eq:gcd-tail}. An integer-valued solution germ
is already a rational multiple $cF_r$; the gcd says exactly that
the denominator of $c$ divides $2$.
\end{proof}

Theorem~\ref{thm:rational-solutions} has an equivalent interpretation
for binomial sums. Bostan, Lairez and Salvy
\cite[Theorem~3.5]{BostanLairezSalvy2017} characterize univariate
multiple binomial sums over $\Q$ as diagonals of rational power
series. Within their class, the solution germs of $L_r$ are
therefore exactly $\Q F_r$. The secondary deformation solutions
cannot be rewritten as multiple binomial sums in that class.
This conclusion concerns rational functions and sums over $\Q$;
these hypotheses specify the class of diagonals used here.

\subsection{The classical integer-sequence question}

The preceding theorem classifies eventual integer solutions for
$r\geq2$. In the classical case $r=3$, a much shorter argument
answers the question about entire integer sequences. This is
the converse asked in \cite[Conjecture~4.5]{SchulteVanSchalkwykYang2014},
where the initial values were assumed positive, and in the conclusion
of \cite{Tonien2026}. The Casoratian formula used in the proof is
also present in \cite[proof of Theorem~6]{Tonien2026}.

\begin{corollary}\label{cor:classical-integers}
An integer sequence $U(0),U(1),\ldots$ satisfies
\begin{equation}\label{eq:classical-recurrence}
 (n+1)^2U(n+1)=(7n^2+7n+2)U(n)+8n^2U(n-1),
 \qquad n\geq1,
\end{equation}
if and only if $U(n)=cF_3(n)$ for some $c\in\Z$.
More generally, a rational solution of
\eqref{eq:classical-recurrence} with bounded denominators on a
tail is a rational multiple of $F_3$ on the entire sequence.
\end{corollary}

\begin{proof}
The Casoratian
$W_n=F_3(n)U(n+1)-F_3(n+1)U(n)$ satisfies
\[
 W_n=-\frac{8n^2}{(n+1)^2}W_{n-1}
     =\frac{(-8)^n}{(n+1)^2}\bigl(U(1)-2U(0)\bigr).
\]
If $b=U(1)-2U(0)\ne0$, choose arbitrarily large odd primes
dividing neither the numerator nor denominator of $b$ nor a
common denominator for the tail of $U$. At $n=p-1$, the formula
gives $v_p(W_n)=-2$, contradicting bounded denominators of $W_n$.
Thus $U(1)=2U(0)$. The recurrence uniquely propagates these
initial values, giving $U=U(0)F_3$. Integrality at $n=0$ forces
$U(0)\in\Z$; the converse follows from the defining binomial sum.
\end{proof}

\subsection{Further questions}\label{sec:questions}

The minimal orders and the leading characteristic polynomials leave
several finer questions. Straub and Zudilin
\cite[Remark~4.1]{StraubZudilin2023} record experimental formulas
for the degree in $n$ of a primitive minimum-order Franel recurrence,
and additional factorization patterns in its certificate.
Appendix~\ref{sec:certificate} settles the denominator and degree
in the summation variable $k$. The degree in $n$ and the possible
factors depending only on $n$ require further arguments.

The analytic method applies more broadly to constant terms
$u(n)=\CT P^n$ of real Laurent polynomials on a torus. To prove
minimality, it is enough to exhibit sufficiently many distinct
nonzero values at which the pushforward measure is not smooth
and to construct a matching recurrence. Extrema of a common type
give a direct noncancellation criterion. For symbols with saddle
points or several types of critical points in the same fiber,
the local contributions must be compared more carefully.

Related extensions of the Straub--Zudilin deformation to other binomial
sums were studied by Dougherty-Bliss and Zeilberger
\cite{DoughertyBlissZeilberger2023}. The arithmetic method here requires
a rational basis whose scaled reductions at $p+b$ all
recover the same distinguished sequence at $b$, with distinct
scaling exponents. Establishing an analogous deformation and
congruence for the alternating family would give information
about its entire solution space. The moment argument alone
determines its minimal order and characteristic roots, but does
not supply that arithmetic structure.

\appendix
\section{The summation variable in a minimal certificate}\label{sec:certificate}

We determine the $k$-dependent denominator and numerator-degree
patterns observed in Remark~4.1 of Straub and Zudilin
\cite{StraubZudilin2023}. It does not address possible denominator factors
depending only on $n$, the predicted degree in $n$, or the further
factorization patterns in that remark.

Every minimum-order recurrence is a scalar multiple over $\Q(n)$
of the telescoper constructed in Section~\ref{sec:telescoping}:
after normalizing the leading coefficients, the difference of two
such operators would be an annihilator of smaller order. Hence
every recurrence in the following proposition has a rational certificate.

\Needspace{14\baselineskip}
\begin{proposition}\label{prop:certificate-structure}
Let $r\geq1$, $m=\lfloor(r+1)/2\rfloor$, and let
$\sum_{j=0}^{m}p_j(n)S^j$ be a minimal-order Franel recurrence, with
$p_j\in\mathbb Q[n]$ and $p_0p_m\ne0$. Its rational certificate
$C\in\mathbb Q(n,k)$ is characterized by
\[
 \mathcal D C
 =\sum_{j=0}^{m}p_j(n)Q_j(n,k),\qquad
 \mathcal D C=\frac{(n-k)^r}{(k+1)^r}C(n,k+1)-C(n,k),\quad
 Q_j=\frac{(n+1)_j^r}{(n-k+1)_j^r}.
\]
Put $K=\mathbb Q(n)$ and $B_m(k)=\prod_{h=1}^{m}(n-k+h)^r$.
Then the reduced denominator of $C$ in $K[k]$ is $B_m$, up to a unit of
$K$. Equivalently,
\[
 C(n,k)=\frac{A(n,k)}{B_m(k)},\qquad A\in K[k],\qquad
 \gcd_{K[k]}(A,B_m)=1.
\]
Moreover,
\[
 k^r\mid A(n,k),\qquad
 \deg_k A=rm+\mathbf1_{\{r\text{ even}\}}.
\]
For a fixed recurrence its rational certificate is unique.
\end{proposition}

\begin{proof}
Write $T=\sum_jp_jQ_j$. Its only possible finite poles in $k$ are
$n+1,\ldots,n+m$, each of order at most $r$. Work over an algebraic
closure of $K$ and group the finitely many poles of $C$ into orbits under
integer translation. In each occupied orbit choose a pole $\alpha$ for which none of
$\alpha-1,\alpha-2,\ldots$ is a pole. At $k=\alpha-1$, the function $C(k+1)$ has a pole and $C(k)$ is
regular. The multiplier $(n-k)^r/(k+1)^r$ cannot remove this pole unless
$\alpha-1=n$; its pole at $-1$ only increases the order. Otherwise
$\alpha-1$ must be a pole of $T$. Thus every occupied orbit is $n+\mathbb Z$,
and its leftmost pole has the form $n+h$ with $h\geq1$.
At the rightmost pole $n+h$, the shifted term is regular, so $T$ has a
pole there. Hence $h\leq m$. Descending from this rightmost pole in
$\mathcal DC=T$ shows that every pole of $C$ has order at most $r$.
Therefore $B_mC\in K[k]$.

There is no pole of $C$ at $-1$ or $0$, and $T$ is regular at $-1$.
The order-$r$ pole of the multiplier there forces $C(k+1)$ to vanish to
order at least $r$. Hence $k^r\mid B_mC$, since $B_m(0)\ne0$ in $K$.

It remains to show that no factor of $B_m$ cancels. By Theorem~\ref{thm:orders},
\[
 \deg p_m=D:=\max_j\deg p_j.
\]
For $r=1$, the same equality follows directly from $p_0+2p_1=0$.
For a sufficiently large nonnegative integer $N$, interpret
$f(N,k)=\binom Nk^r$ by gamma-function continuation, as in the telescoping
construction. The pole bounds just proved imply that
$b(N,k)=C(N,k)f(N,k)$ is finite at every integer $k$ and has finite
support there. Summing its forward difference from $k=N+h$ to infinity
gives
\begin{equation}\label{eq:certificate-tail}
 b(N,N+h)
 =-\sum_{j=h}^{m}p_j(N)
       \sum_{\ell=0}^{j-h}\binom{N+j}{\ell}^{r},
 \qquad 1\leq h\leq m.                        
\end{equation}
The right side is a nonzero polynomial in $N$: its $j=m$ summand has
degree $D+r(m-h)$, with leading coefficient
$-[n^D]p_m/((m-h)!)^r$, whereas every $j<m$ summand has smaller degree.
Since $f(N,k)$ has a zero of exact order $r$ at $k=N+h$, equation~\eqref{eq:certificate-tail}
is incompatible with a pole of order less than $r$ for $C$ at
$k=n+h$. This proves the exact denominator assertion.

Finally, let $C=c(n)k^a(1+O(k^{-1}))$ at infinity, where
$a\in\mathbb Z$ and $c\ne0$. Since $Q_0=1$ and $Q_j=O(k^{-rj})$ for
$j\geq1$, one has $T=p_0+O(k^{-r})$. Direct expansion gives
\[
 \mathcal DC=
 \begin{cases}
 -2c(n)k^a(1+O(k^{-1})),&r\text{ odd},\\
 c(n)\bigl(a-r(n+1)\bigr)k^{a-1}(1+O(k^{-1})),&r\text{ even}.
 \end{cases}
\]
The displayed leading coefficients are nonzero in $K$. It follows that
$a=0$ for odd $r$ and $a=1$ for even $r$, proving the numerator degree.
The same expansion shows that $\ker\mathcal D=0$ on $K(k)$, which proves
uniqueness of the rational certificate.
\end{proof}

\begin{remark}
The argument proves the same conclusion for any polynomial-coefficient
telescoping relation of width $m$ satisfying $p_0p_m\ne0$ and
$\deg p_m=\max_j\deg p_j$. Minimality is used only to supply this last
degree equality. All denominator statements above are in $K[k]$; elements
of $K^\times$ are units and are not controlled by this proposition.
\end{remark}


\begin{thebibliography}{99}

\bibitem{Batenkov2009}
D. Batenkov, Moment inversion problem for piecewise D-finite functions,
\emph{Inverse Problems} \textbf{25} (2009), no.~10, 105001, 24~pp.
\href{https://doi.org/10.1088/0266-5611/25/10/105001}{doi:10.1088/0266-5611/25/10/105001}.

\bibitem{BostanElveyPriceGuttmannMaillard2020}
A. Bostan, A. Elvey Price, A. J. Guttmann and J.-M. Maillard,
Stieltjes moment sequences for pattern-avoiding permutations,
\emph{Electronic Journal of Combinatorics} \textbf{27} (2020), no.~4,
Paper~P4.20, 59~pp.
\href{https://doi.org/10.37236/9402}{doi:10.37236/9402}.

\bibitem{BostanLairezSalvy2017}
A. Bostan, P. Lairez and B. Salvy, Multiple binomial sums,
\emph{Journal of Symbolic Computation} \textbf{80} (2017), 351--386.
\href{https://doi.org/10.1016/j.jsc.2016.04.002}{doi:10.1016/j.jsc.2016.04.002}.

\bibitem{ChamberlandStraub2021}
M. Chamberland and A. Straub, Ap\'ery limits: Experiments and proofs,
\emph{American Mathematical Monthly} \textbf{128} (2021), no.~9, 811--824.
\href{https://doi.org/10.1080/00029890.2021.1962153}{doi:10.1080/00029890.2021.1962153}.

\bibitem{Cusick1989}
T. W. Cusick, Recurrences for sums of powers of binomial coefficients,
\emph{Journal of Combinatorial Theory, Series A} \textbf{52} (1989), no.~1, 77--83.
\href{https://doi.org/10.1016/0097-3165(89)90063-0}{doi:10.1016/0097-3165(89)90063-0}.

\bibitem{DoughertyBlissZeilberger2023}
R. Dougherty-Bliss and D. Zeilberger, Exploring general Ap\'ery limits
via the Zudilin--Straub $t$-transform,
\emph{Journal of Difference Equations and Applications}
\textbf{29} (2023), no.~1, 32--42.
\href{https://doi.org/10.1080/10236198.2022.2159817}{doi:10.1080/\allowbreak10236198.2022.2159817}.

\bibitem{EssamGuttmann1995}
J. W. Essam and A. J. Guttmann, Vicious walkers and directed polymer
networks in general dimensions, \emph{Physical Review E}
\textbf{52} (1995), no.~6, 5849--5862.
\href{https://doi.org/10.1103/PhysRevE.52.5849}{doi:10.1103/PhysRevE.52.5849}.

\bibitem{Franel1894}
J. Franel, Question n\textsuperscript{o}~42 (Laisant),
\emph{L'Interm\'ediaire des Math\'ematiciens} \textbf{1} (1894), 45--47.

\bibitem{Franel1895}
J. Franel, Question n\textsuperscript{o}~170 (J.~Franel),
\emph{L'Interm\'ediaire des Math\'ematiciens} \textbf{2} (1895), 33--35.

\bibitem{McIntosh1989}
R. J. McIntosh, \emph{Asymptotic and Arithmetic Properties of Recurrent Sequences},
Ph.D. thesis, University of California, Los Angeles, 1989.

\bibitem{McIntosh1993}
R. J. McIntosh, Recurrences for alternating sums of powers of binomial
coefficients, \emph{Journal of Combinatorial Theory, Series A}
\textbf{63} (1993), no.~2, 223--233.
\href{https://doi.org/10.1016/0097-3165(93)90058-G}{doi:10.1016/0097-3165(93)90058-G}.

\bibitem{Ore1933}
O. Ore, Theory of non-commutative polynomials,
\emph{Annals of Mathematics}, Second Series,
\textbf{34} (1933), no.~3, 480--508.
\href{https://doi.org/10.2307/1968173}{doi:10.2307/1968173}.

\bibitem{Perlstadt1987}
M. A. Perlstadt, Some recurrences for sums of powers of binomial coefficients,
\emph{Journal of Number Theory} \textbf{27} (1987), no.~3, 304--309.
\href{https://doi.org/10.1016/0022-314X(87)90069-2}{doi:10.1016/0022-314X(87)90069-2}.

\bibitem{Perron1909}
O. Perron, \"Uber einen Satz des Herrn Poincar\'e,
\emph{Journal f\"ur die reine und angewandte Mathematik}
\textbf{136} (1909), 17--37.
\href{https://doi.org/10.1515/crll.1909.136.17}{doi:10.1515/crll.1909.136.17}.

\bibitem{SchulteVanSchalkwykYang2014}
A. Schulte, S. VanSchalkwyk and A. Yang, On the divisibility and valuations
of the Franel numbers, in \emph{2014 MSRI-UP Research Reports}, pp.~127--162.

\bibitem{Stoll1997}
M. Stoll, Bounds for the length of recurrence relations for convolutions
of P-recursive sequences, \emph{European Journal of Combinatorics}
\textbf{18} (1997), no.~6, 707--712.
\href{https://doi.org/10.1006/eujc.1996.0123}{doi:10.1006/eujc.1996.0123}.

\bibitem{StraubZudilin2023}
A. Straub and W. Zudilin, Sums of powers of binomials, their Ap\'ery limits,
and Franel's suspicions, \emph{International Mathematics Research Notices}
\textbf{2023} (2023), no.~11, 9861--9879.
\href{https://doi.org/10.1093/imrn/rnac125}{doi:10.1093/imrn/rnac125}.


\bibitem{Tonien2026}
J. Tonien, Franel numbers and a continued fraction conjecture discovered
by the Ramanujan Machine, \emph{The Mathematical Intelligencer}
\textbf{48} (2026), no.~3, 222--227; published online 24 February 2026.
\href{https://doi.org/10.1007/s00283-025-10497-9}{doi:10.1007/s00283-025-10497-9}.

\bibitem{VanHoeij2025}
M. van Hoeij, Submodule approach to creative telescoping,
\emph{Journal of Symbolic Computation} \textbf{126} (2025), 102342.
\href{https://doi.org/10.1016/j.jsc.2024.102342}{doi:10.1016/j.jsc.2024.102342}.


\bibitem{VanHove1953}
L. van Hove, The occurrence of singularities in the elastic frequency
distribution of a crystal, \emph{Physical Review} \textbf{89} (1953), no.~6,
1189--1193.
\href{https://doi.org/10.1103/PhysRev.89.1189}{doi:10.1103/PhysRev.89.1189}.

\bibitem{YuanDickinson2000}
Yuan Jin and H. Dickinson, Ap\'ery sequences and Legendre transforms,
\emph{Journal of the Australian Mathematical Society, Series A}
\textbf{68} (2000), no.~3, 349--356.
\href{https://doi.org/10.1017/S1446788700001440}{doi:10.1017/S1446788700001440}.

\bibitem{YuanLuSchmidt2008}
J. Yuan, Z.-J. Lu and A. L. Schmidt, On recurrences for sums of powers of
binomial coefficients, \emph{Journal of Number Theory}
\textbf{128} (2008), no.~10, 2784--2794.
\href{https://doi.org/10.1016/j.jnt.2008.03.011}{doi:10.1016/j.jnt.2008.03.011}.

\end{thebibliography}

\end{document}