Let $m,n$ be nonnegative integers.
The sequence $\{a_{m,n}\}$ satisfies the following three conditions.
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.
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.
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.)
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.
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.
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?
