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.