# Proving that every term of the sequence is an integer

Let $m,n$ be nonnegative integers.

The sequence $\{a_{m,n}\}$ satisfies the following three conditions.

1. For any $m$, $a_{m,0}=a_{m,1}=1$
2. For any $n$, $a_{0,n}=1$
3. For any $m\ge0, n\ge1$, $a_{m+1,n+1}a_{m,n-1}=a_{m+1,n-1}a_{m,n+1}+a_{m+1,n}a_{m,n}$

Prove that $a_{m,n}$ is an integer for any $m\ge0, n\ge0$.

I don't have any good idea. I need your help.

-
I think it's worth commenting that this question has been asked previously on math.SE without receiving any answers: math.stackexchange.com/questions/399337/… – J. J. May 29 '13 at 7:13
I write $a(m,n)$ for $a_{m,n}$. We have $a(1,n+1)=a(1,n)+a(1,n-1)$ with $a(1.0)=a(1,1)=1$. This is the usual Fibonacci sequence. Now try induction over $m$. – Dietrich Burde May 29 '13 at 8:13
We also have $a_{m,2} = m+1$, $a_{m,3} = \frac{m(m+1)(m+2)}{3} + 1$ and $a_{m,4} = n+1 + \sum_{j=1}^n \frac{(j^3 - j + 3)(j^3 + 3j^2 + 2j + 3)(n+1)}{9j(j+1)}$. One might be able to simplify the formula for $a_{m,4}$. – J. J. May 29 '13 at 9:08
Where does the problem come from? – Gerry Myerson May 29 '13 at 11:27
In the comments of the MSE question, mathlove states: @J.J. One of my friends made this. None of us can prove this and no one can get a counterexample even by using a computer. He, who made this, whose major is math, was interested in 'Somos sequence'. That's why the idea I showed on May 23th came from the proof of this sequence. – mathlove 8 hours ago – j.c. May 29 '13 at 12:50

## 5 Answers

This is the knight recurrence (Example 4.1) in Fomin and Zelevinsky's paper on the Laurent phenomenon. They show more generally that if you replace the boundary entries with indeterminates, then all matrix entries are Laurent polynomials.

-
@Timothy Chow: Thank you very much for great information. Please give me time to understand. – mathlove May 29 '13 at 14:51

This looks like it might be a "rank two elliptic divisibility sequence", i.e., let $E$ be an elliptic curve, let $P$ and $Q$ be independent points in $E(\mathbb{Q})$, and write $$x(mP+nQ) = A(m,n)/D(m,n)^2.$$ Then the doubly-indexed sequence $D(m,n)$ is a rank two elliptic divisibility sequence, or as they were named by Kate Stange, an elliptic divisibility net. Kate made a detailed study of these sequences in her thesis (Algebra and Number Theory, 5-2 (2011), 197-229; it's also available on the ArXiv at http://arxiv.org/abs/0710.1316), including a description of the recurrence relation(s) that they satisfy.

Anyway, I don't know for sure if your rank two sequence fits into Kate's elliptic net framework, but it's quite possible that it does.

(I'm actually cheating a little bit here, one really needs to use division polynomials instead of writing $x(mP+nQ)$ as a fraction in case there's cancellation between the numerator and the denominator. But this will only affect primes of bad reduction.)

-
@Joe Silverman: Thank you very much. – mathlove May 30 '13 at 14:46

If I haven't made a mistake then the first few values of your sequence look like this:

$$(a_{m,n})=\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & ... \newline 1 & 1 & 2 & 3 & 5 & 8 & ... \newline 1 & 1 & 3 & 9 & 21 & 59 & \newline 1 & 1 & 4 & 21 & 91 & ... & \newline 1 & 1 & 5 & 41 & 329 & ... & \newline 1 & 1 & \vdots & \vdots & \vdots & & \newline \vdots & \vdots & & & & & \end{pmatrix}$$

Maybe the proposed induction gets easier if you look at the columns: It holds that $a(m,2)=a(m-1,2)+1$ for $m\geq 1$ and $a(0,2)=1$, thus $a(m,2)=m+1$, which is technically easier to deal with then Fibonacci, I guess.

-
But $(a_{1,n})=(1,1,2,3,5,8,...)$ should be the Fibonacci sequence, or not ? – Dietrich Burde May 29 '13 at 8:43
@MHMertens: Unfortunately, you did make a calculation mistake. The row $1, 4, 39/2, \dots$ should be $1, 5, 21, 91, \dots$. – Tom De Medts May 29 '13 at 8:59
(By the way, it's also a little bit confusing that you interchanged rows and columns.) – Tom De Medts May 29 '13 at 9:00
Arrggh, sorry about that! I didn't see the Fibonacci sequence in there at first and so the two 4s in the matrix didn't disturb me. It was still early this morning... – MHMertens May 29 '13 at 10:24
@Barry: I've checked the first $400 \times 400$ entries by computer, and they are all integers. – Tom De Medts May 29 '13 at 13:46

This is probably of limited help in general, but if you write the second and third row of the matrix in MHMertens's answer as

$$\begin{pmatrix}{f_0}&{f_1}&{f_2}&{\cdots}\cr {g_0}&{g_1}&{g_2}&{\cdots}\cr\end{pmatrix}$$

where the second row is clearly the Fibonacci sequence, then the third row satisfies the recursion

$$g_{n+1} = 2f_{n+1}f_n - g_n$$

and therefore consists of all integers.

The real thing to prove is that $g_n+g_{n-1}=2f_nf_{n-1}$ implies $g_{n+1}+g_n = 2f_{n+1}f_n$, and this is easy since the Fibonacci recursion $f_n+f_{n-1}=f_n$ gives

$$g_{n+1}+g_n = {f_{n+1}g_{n-1}+f_ng_n\over f_{n-1}}+g_n = {f_{n+1}(g_{n-1}+g_n)\over f_{n-1}}.$$

Added later: In a comment to MHMertens's answer, Abhinav Kumar says that the entries in the third row, which I'm calling $g_0,g_1,g_2,\ldots$, satisfy a 4-term linear recurrence. (He actually says much more than this, but I'm only looking at the third row for now.) However, he doesn't say how he gets this, so I thought I'd just add a quick proof here.

From the actual entries, $1,1,3,9,21,59,149,397,\ldots$, it's not hard to find the candidate recurrence

$$g_{n+1} = g_n + 4g_{n-1}+g_{n-2}-g_{n-3}.$$

Rewriting this as

$$g_{n+1}+g_n = 2(g_n+g_{n-1})+2(g_{n-1}+g_{n-2})-(g_{n-2}+g_{n-3}),$$

you can reduce this to verifying a Fibonacci identity,

$$f_{n+1}f_n = 2f_nf_{n-1}+2f_{n-1}f_{n-2}-f_{n-2}f_{n-3},$$

which is a little tedious, but doable.

Finally, note that the characteristic polynomial for the recurrence factors into fairly small pieces, as Kumar says happens in general:

$$x^4-x^3-4x^2-x+1 = (x+1)^2(x^2-3x+1).$$

Whether any of this helps, even for the next row of numbers, is unclear.

-
@Barry Cipra:Thank you very much. – mathlove May 30 '13 at 14:47

This might help. Let $${b}_{m,n}=\begin{pmatrix} {a}_{m,n} &{a}_{m,n+1} &{a}_{m,n+2} \\ {a}_{m+1,n} &{a}_{m+1,n+1} &{a}_{m+1,n+2} \end{pmatrix}$$

Your iteration formula says that if you multiply the top left and bottom right corner numbers of ${b}_{m,n}$, subtract the product of the top right and bottom left corner numbers, then you get the product of the top and bottom middle numbers. The first two rows of your numbers are known to be integers (Dietrich), as are the first three columns (J.J). Hence ${b}_{0,n}$ and ${b}_{m,0}$ contain integers. Now consider the sequence of matrices ${b}_{0,0}$, ${b}_{0,1}$, ${b}_{1,0}$, ${b}_{0,2}$, ${b}_{1,1}$, ${b}_{2,0}$ etc. The only unknown number in ${b}_{1,1}$ is the bottom right hand number and this is true of each of these $2 \times 3$ matrices when we leave the first two rows or first 3 columns. Could that form the basis of a proof by induction?

-
@PRobinson: Thank you very much. – mathlove May 30 '13 at 14:47