Minimal recurrences for binomial power sums

Introduction

For a positive integer $r$, the sums

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 [8, 9]. The order suggested by those examples is

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 [13] computed recurrences for $r=5,6$, and McIntosh [10] treated $r\le10$. Cusick [5] proposed a general construction; Stoll [16] 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 [21 p. 350]. Yuan, Lu and Schmidt [22] ruled out first-order recurrences for every $r\ge3$. Straub and Zudilin [17, Theorem 1.1] proved the lower bound $m_r$ for recurrences obtained by creative telescoping from (1). They also verified unrestricted minimality computationally for $r\le20$ [17 Remark 4.1]. Van Hoeij [19 §5, Remark 6] subsequently obtained the matching telescoping upper bound by polynomial reduction and reflection. For more information, see Tonien’s paper [18].

To state the results clearly, we use the following conventions throughout. A recurrence of order $M$ for a sequence $u$ is an identity

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 eventual germ if they agree for all sufficiently large indices. All solution spaces below are spaces of such germs.

For a nonzero recurrence, put

We call $\chi$ its 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

Write $a_r=\lfloor r/2\rfloor$ and define the monic polynomials

The formula for $H_r$ also gives $H_1(X)=X-2$.

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 [19 §7, Question 1]. The divisibility assertion applies to every recurrence, regardless of how it is obtained.

For the alternating sums, McIntosh [11, Theorem 1] gave a construction of recurrences of order at most $a_r$ and established sharpness when $r$ is prime or a power of $2$ [11 Theorem 2]. 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

be the shift Ore ring. Let $L_r\in\mathbb{Q}(n)[S;\sigma]$ be the monic minimal operator of $F_r$. Here monic means that the coefficient of $S^{m_r}$ is $1$.

We first establish minimality and then use the arithmetic congruence to deduce irreducibility. The coefficient field in Theorem 1.2 is $\mathbb{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\mathbb{C}(n)$.

The arithmetic of the other solutions is also rigid. A rational sequence is globally bounded on a tail if there are positive integers $B,C$ such that $BC^n u(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

The two mechanisms

The analytic part begins with a general observation. If $u(n)=\int x^n\,\mathrm{d}\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 2.1). Moment recurrences and differential equations have long been studied together; relevant forms appear in Batenkov’s work on piecewise $D$-finite functions [1 Theorems 2.9 and 2.13] and in the work of Bostan, Elvey Price, Guttmann and Maillard on Stieltjes moment sequences [2 Theorem 3]. 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 [8 p. 46]. 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 [7 §III B] 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 [20]. 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 $\mathbb{Q}$ makes this argument work for arbitrary complex coefficients (Proposition 5.4). It proves irreducibility without factoring the recurrence operator.

Organization

Sections 2–4 prove Theorem 1.1. Section 5 develops the congruence and proves Theorem 1.2; Section 6 proves the arithmetic classification. Appendix § 7 determines the exact dependence of a minimal telescoping certificate on its summation variable, resolving that part of the patterns recorded in [17 Remark 4.1].

A singular-support bound for moment recurrences

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.

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.

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

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 (10) 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$. $\square$

The real torus symbols and their critical values

Fix $r \ge2$ and put $d=r-1$. On the torus $\mathbb{T}^{d}$, write $z_j=e^{i\theta_j}$, $Z=z_1\cdots z_d$, and

Both $P$ and $Q$ are real-valued on the torus. With $s=\theta_1+\cdots+\theta_d$, they become

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$.

Proof. Expanding $(1+Z^{-1})^n$ gives

Likewise,

Constant terms are torus integrals against normalized Haar measure. $\square$

Proof. At a point where $P \ne0$, all factors in (11) are nonzero, and

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\le k<r$; the point with $\theta_j=\pi$, when present, has value zero and is excluded. The value at every other point is

The indices $k$ and $r-k$ give the same value. The representatives $0\le k<r/2$ have strictly decreasing absolute values, so they give all the distinct nonzero critical values. At these points,

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

They force $\theta_j = (2h+1)\pi/r$, $0 \le h < r$. Writing $\alpha= (2h+1)\pi/(2r)$, one obtains

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 (6). □

Lemmas 2.2 and 3.2 show that each $\lambda_{r,k}$ belongs to $\operatorname{sing\,supp}\mu_r$ and each $\nu_{r,h}$ belongs to $\operatorname{sing\,supp}\widetilde{\mu}_r$. Proposition 2.1 therefore proves the divisibilities in Theorem 1.1 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_j p_j(n)2^j=0$, hence $\chi(2)=0$.

Some small cases illustrate the two spectra:

$r$	$H_r(X)$	$\widetilde{H}_r(X)$
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)$

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.

Remark 3.4. 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

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.

A common telescoping construction

We give a common proof of the matching upper bounds. The ordinary case follows the reduction and reflection argument of van Hoeij [19 §5, Remark 6]. 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 § 5. Write $(x)_j=x(x+1)\cdots(x+j-1)$, with $(x)_0=1$.

Proof. Work over $K=\mathbb{Q}(n)$ and set

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

For $V_h(k)=k^rH(k)/(n-k+h)^r$ one has

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\ge1$, in both cases

Let $JC(k)=C(n-k)$. Direct substitution gives

Hence $J$ induces an involution on the quotient. Moreover,

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

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 (14).

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$

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

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,

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. □

Completion of the proof of Theorem 1.1. For $\varepsilon=1$, bilateral summation in Lemma 4.1 gives a nonzero recurrence of order at most $m_r$ for $F_r$. For $\varepsilon=-1$, specialize the parameter to $2n$ and use

The resulting recurrence is $\sum_{j=0}^{\alpha_r}(-1)^jp_j(2n)T_r(n+j)=0$ and has order at most $\alpha_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 3. 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{n}{k}$ is $-\binom{n-1}{k-1}$ and has finite support on the integer lattice. □

The deformation and its arithmetic

A deformation theorem

Define the even rational function

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.

The telescoping construction in § 4 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 [17 proof of Theorem 1.1]. We give an arithmetic proof as part of a congruence that will control denominators and annihilators.

One congruence at shifted prime powers

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

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.

Proof. The case $Q=0$ is immediate. Otherwise choose a $\mathbb{Q}$-basis $\beta_1,\ldots,\beta_t$ of the finite-dimensional $\mathbb{Q}$-vector space spanned by all products $c_j[n^h]q_\ell(n)$. Write

For every sufficiently large integer $n$, the identity $QU(n)=0$ becomes

Each parenthesized expression is rational. Independence of the $\beta_i$ over $\mathbb{Q}$ makes each expression zero separately.

Fix $b\ge0$. 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 (19), the terms with $j<J$ vanish, leaving

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 (20). For rational-function coefficients, first clear their polynomial denominators in $n$, which preserves annihilation on a tail. □

Proof of Theorem 1.2. Suppose that $L_r=BR$ in $\mathbb{C}(n)[S;\sigma]$ with $0<\operatorname{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 5.3 expresses $U$ as a nonzero complex combination of $A_{r,0},\ldots,A_{r,m_r-1}$. Proposition 5.4 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 5.4 gives $QF_r=0$. Right division by the monic operator $L_r$ writes $Q=HL_r+R$ with $\operatorname{ord}R<m_r$; this is the usual division algorithm in the shift Ore ring [12]. Since $RF_r=0$, minimality forces $R=0$. Finally, a nonzero hypergeometric germ has an annihilator $S-a(n)$ with $a(n)\in\mathbb{C}(n)$, impossible when $r\ge3$ and $m_r\ge 2. □

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.

Proof. After clearing denominators, divide a minimum-order recurrence by its coefficient of $S^{mr}$. Theorem 1.1 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 [14], in the form stated in [4 §4], therefore gives a basis of solutions with successive ratios tending to $\lambda_{r,k}$. The elementary bounds

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 (21). □

Denominators, diagonals and integer solutions

Exact denominator growth

For $x\in\mathbb{Q}$, let $\operatorname{den}(x)$ be its positive denominator in lowest terms, with $\operatorname{den}(0)=1$. Fix an initial index $N_0\ge1$ from which the displayed basis expansion of the rational germ holds, and put

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\le N}\log p$.

Proof. Choose $B$ with $Bc_j\in\mathbb{Z}$ for every $j$. By (17), $B\ell_n^{2J}U(n)$ is integral, which gives the divisibility in (25). Let $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 (19); every lower term has strictly larger valuation. This proves (23).

For $p\notin S$, the divisibility bound gives $v_p(D_U(N))\le2J\lfloor\log_pN\rfloor$. If $p\le N$, choose $\alpha=\lfloor\log_pN\rfloor$. Then $N_0<p\le p^\alpha\le N$, so (23) gives the matching lower bound. If $p>N$, both sides are zero. This proves (24). 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$. □`

For the solution space of $L_r$, Proposition 5.3 shows that the possible nonzero-solution rates in (26) are exactly $0,2,\ldots,2m_r-2$. More precisely, the solutions with rate at most $2J$ form

Equivalently, write the Apéry limit uniquely as $\mathcal{L}(U)=P_U(\pi^2)$, where $P_U\in\mathbb{Q}[X]$ and $\deg P_U<m_r$. For every nonzero $U\in V_r$,

Indeed, (16) gives $P_U(X)=\sum_j c_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éry limit.

The globally bounded direction

Proof of the arithmetic assertions in Theorem 1.3. Write a nonzero rational solution in the basis of Proposition 5.3, 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 (23) 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 $\mathbb{Q}$ regular at the origin is globally bounded. For completeness, write that function as $P(x)/Q(x)$ with integral polynomials and $Q(0)=a\ne0$. The series $H=1-Q/a$ has zero constant term, and

A monomial of total degree $h$ receives terms only from $q\le 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 $\mathbb{Q}F_r$. Conversely,

Indeed, geometric expansion gives $\sum_{k\ge0}(x_1\cdots x_r)^k\prod_i(1-x_i)^{-k-1}$, whose diagonal coefficient is $\sum_{k=0}^n\binom{n}{k}^r$. Rational multiples are again rational diagonals.

It remains to determine the integer lattice for $r\ge2$. For every $N\ge1$,

Pairing the summands with indices $k$ and $n-k$ shows that $F_r(n)$ is even for $n\ge1$: 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}^r$ 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\ge2$. This proves (29). An integer-valued solution germ is already a rational multiple $cF_r$; the gcd says exactly that the denominator of $c$ divides $2$.

Theorem 1.3 has an equivalent interpretation for binomial sums. Bostan, Lairez and Salvy [3 Theorem 3.5] characterize univariate multiple binomial sums over $\mathbb{Q}$ as diagonals of rational power series. Within their class, the solution germs of $L_r$ are therefore exactly $\mathbb{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 $\mathbb{Q}$; these hypotheses specify the class of diagonals used here.

The classical integer-sequence question

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

Proof. The Casoratian $W_n = F_3(n)U(n+1) - F_3(n+1)U(n)$ satisfies

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\mathbb{Z}$; the converse follows from the defining binomial sum. □

Further questions

The minimal orders and the leading characteristic polynomials leave several finer questions. Straub and Zudilin [17 Remark 4.1] record experimental formulas for the degree in $n$ of a primitive minimum-order Franel recurrence, and additional factorization patterns in its certificate. Appendix A 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) = \operatorname{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 [6]. 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.

The summation variable in a minimal certificate

We determine the $k$-dependent denominator and numerator-degree patterns observed in Remark 4.1 of Straub and Zudilin [17]. 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 $\mathbb{Q}(n)$ of the telescoper constructed in Section 4: 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.

Remark A.2. 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.