TOPICS
Search

Schmidt's Problem

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Schmidt's problem (Schmidt 1993) asks whether, for any integer r>=2, the sequence {c_k^((r))}_(k=0)^infty defined for all nonnegative integers n by the binomial sums

sum_(k=0)^n(n; k)^r(n+k; k)^r=sum_(k=0)^n(n; k)(n+k; k)c_k^((r))
(1)

consists entirely of integers. In particular, c_0^((r))=1. In the formulas below, a binomial coefficient with a nonnegative upper argument and a lower argument outside its usual range is taken to be 0.

The following table gives the first few values of sum_(k=0)^(n)(n; k)^r(n+k; k)^r for small r.

rOEISvalues
1A0018501, 3, 13, 63, 321, 1683, 8989, 48639, ...
2A0052591, 5, 73, 1445, 33001, 819005, ...
3A0928131, 9, 433, 36729, 3824001, 450954009, ...
4A0928141, 17, 2593, 990737, 473940001, ...
5A0928151, 33, 15553, 27748833, 61371200001, ...

This was proved by Strehl (1993, 1994) and Schmidt (1995) for the case r=2, corresponding to the Franel numbers. Strehl (1994) also found an explicit expression for the case r=3. The resulting identities for r=2,3 are therefore known as the Strehl identities. The problem was restated in Graham et al. (1994, pp. 256 and 549), who indicated that H. S. Wilf had shown c_n^((r)) to be an integer for any r>=2 and 0<=n<=9 (Zudilin 2004).

The problem was answered in the affirmative by Zudilin (2004), who found explicit expressions for all c_n^((r)). Particular cases include

c_n^((2))=sum_(j=0)^(n)(n; j)^3
(2)
=sum_(j=0)^(n)(n; j)^2(2j; n)
(3)
c_n^((3))=sum_(j=0)^(n)(2j; j)^2(2j; n-j)(n; j)^2
(4)
c_n^((4))=sum_(j=0)^(n)(2j; j)^3(n; j)sum_(k=0)^(n)(k+j; k-j)(j; n-k)(k; j)(2j; k-j)
(5)
c_n^((5))=sum_(j=0)^(n)(2j; j)^4(n; j)^2sum_(k=0)^(n)(k+j; k-j)^2(2j; n-k)(2j; k-j),
(6)

with values for r>5 given by

c_n^((2s))=sum_(j=0)^(n)(2j; j)^(2s-1)(n; j)sum_(k_1=0)^(n)(j; n-k_1)(k_1; j)(k_1+j; k_1-j)sum_(k_2=0)^(n)(2j; k_1-k_2)(k_2+j; k_2-j)^2...sum_(k_(s-1)=0)^(n)(2j; k_(s-2)-k_(s-1))(k_(s-1)+j; k_(s-1)-j)^2(2j; k_(s-1)-j)
(7)
c_n^((2s+1))=sum_(j=0)^(n)(2j; j)^(2s)(n; j)^2sum_(k_1=0)^(n)(2j; n-k_1)(k_1+j; k_1-j)^2sum_(k_2=0)^(n)(2j; k_1-k_2)(k_2+j; k_2-j)^2...sum_(k_(s-1)=0)^(n)(2j; k_(s-2)-k_(s-1))(k_(s-1)+j; k_(s-1)-j)^2(2j; k_(s-1)-j)
(8)

(Zudilin 2004).

The following table summarizes the sequence of c_n^((r)) for small r. Note that c_n^((2)) are precisely the Franel numbers.

rOEIS{c_n^((r))}
2A0001721, 2, 10, 56, 346, 2252, 15184, 104960, ...
3A0006581, 4, 68, 1732, 51076, 1657904, 57793316, ...
4A0928681, 8, 424, 48896, 6672232, 1022309408, ...

See also

Apéry Number, Binomial Sums, Franel Number, Strehl Identities

Explore with Wolfram|Alpha

References

Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Schmidt, A. L. "Generalized q-Legendre Polynomials." J. Comput. Appl. Math. 49, 243-249, 1993. https://doi.org/10.1016/0377-0427(93)90156-6.Schmidt, A. L. "Legendre Transforms and Apéry's Sequences." J. Austral. Math. Soc. Ser. A 58, 358-375, 1995. https://doi.org/10.1017/S1446788700038350.Sloane, N. J. A. Sequences A000172/M1971, A000658, A001850/M2942, A005259/M4020, A092813, A092814, A092815, and A092868 in "The On-Line Encyclopedia of Integer Sequences."Strehl, V. "Binomial Sums and Identities." Maple Technical Newsletter 10, 37-49, 1993.Strehl, V. "Binomial Identities--Combinatorial and Algorithmic Aspects." Disc. Math. 136, 309-346, 1994. https://doi.org/10.1016/0012-365X(94)00118-3.Zudilin, W. "On a Combinatorial Problem of Asmus Schmidt." Elec. J. Combin. 11, No. 1, R22, 2004. https://doi.org/10.37236/1775.

Referenced on Wolfram|Alpha

Schmidt's Problem

Cite this as:

Weisstein, Eric W. "Schmidt's Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SchmidtsProblem.html

Subject classifications