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.