Theorem:
(Cojectured and alomost proved by Paul Heideman and Emilie Hogan,
in undergraduate research advised by Jim Propp, at the U. of Wisc.)
Let K be a positive integer
Define an integer sequence a(n) (n>=0) by the non-linear recurrence
a(n - 1) a(n - 2 K) + a(n - K) + a(n - K - 1)
a(n) = ---------------------------------------------
a(n - 2 K - 1)
subject to the initial conditions a(i)=1 for 0<=i<=2K
Then lo-and-behold all the terms are integers
Completion of the proof by Shalosh B. Ekhad
Let b(n) be the sequence annihilated by the linear
recurrence equation with constant coefficients
2 2
-b(n) + (4 + 8 K + 2 K ) b(n + K) + (-4 - 8 K - 2 K ) b(n + 2 K) + b(n + 3 K)
= 0
With the following initial conditions
For n in the discrete interval
[1, 1 + 2 K]
it equals the polynomial
1
For n in the discrete interval
[2 + 2 K, 1 + 3 K]
it equals the polynomial
-1 + 2 n - 4 K
For n in the discrete interval
[2 + 3 K, 1 + 4 K]
it equals the polynomial
2 2
1 - 2 n + 2 n + 8 K - 12 n K + 18 K
For n in the discrete interval
[2 + 4 K, 1 + 5 K]
it equals the polynomial
2 2 2 3
-3 + 2 n + 2 n - 16 K - 4 n K - 18 K + 4 n K - 16 K
For n in the discrete interval
[2 + 5 K, 1 + 6 K]
it equals the polynomial
4 2 2 2 2 3 3
3 - 10 n + 60 K + 100 K + 8 n + 16 n K + 4 n K - 40 n K + 424 K
2 2
- 164 n K + 296 K - 96 n K
Note that b(n) is well-defined and manifestly an integer
(by induction)
I claim that b(n)=a(n).
All we have to prove is that b(n) satisfies the same non-linear
recurrence as a(n), with the same initial conditions
The initial conditions are right, of course, and Paul and Emilie
have already proved that if
b(n) b(n - 2 K - 1) - b(n - 1) b(n - 2 K) - b(n - K) - b(n - K - 1) = 0
is true for n<=6K, then it is true for ever after.
So it only remains to prove this for n<=6K
But this is a routine verification
using the above explicit expressions for b(n), and is indeed true.
QED
The whole thing took, 37.542, seconds of CPU time