Linear Recurrence Relations in 2 Variables with Variable Coefficients Consider the following recurrence relation:
$$-2a_{n,m} +a_{n-1,m}+a_{n,m-1}=0,$$
where $a_{n,m} \in \mathbb{C}.$I would like a purely combinatorial way to understand the subspace of solutions to this equation which have tempered growth. There is an obvious solution given by setting all $a_{n,m}=C$ for any constant $C,$ and I have reasons (coming from topology) to believe that these are the only solutions with tempered growth. 
Now consider the similar but probably much harder recurrence relation: 
$$-2a_{n,m} +a_{n-1,m}+e^{2 \pi i n \theta}a_{n,m-1}=0$$
where $\theta$ is a fixed irrational. Note that the relation now depends on $n.$ I haven't even been able to come up with a solution to this that has tempered growth. I am hoping that it also has a 1 dimensional (or at least finite dimensional) space of solutions with tempered growth. 
Is there a general combinatorial method for attacking either of these recurrence relations? Is there a general way to attack any linear recurrence relation like these?
EDIT: Let me also give my "proof" (I think it is correct) that any solution to the first relation with tempered growth must be constant. Consider the 2 dimensional torus thought of as $S^1\times S^1$, where $S^1$ is the unit circle. Now consider the function $z_1+z_2-2,$ thought of as a (finite) Fourier series. This has only 1 zero, at $(1,1).$ 
Now consider distributions $D$ on the torus, also thought of as Fourier series $D=\sum_\mathbb{Z^2} a_{n,m}z_1^nz_2^m$ where the $a_{n,m}$ now have only tempered growth. The first recurrence above is exactly the condition that $(z_1,+z_2 -2)D=0$ as a distribution. Since $z_1+z_2-2$ has only a single zero, the only solution with tempered growth should be a multiple of the Dirac distribution which is given by $a_{n,m}=1.$ I want a combinatorial proof or understanding of this phenomenon, since the second relation does not have this kind of topological interpretation. Ideally I would like to prove that the vector space of solutions to the second relation is also dimension 1, or is at least in some way related to the first relation.
2nd EDIT: WillSawin's answer shows that my initial proof is wrong. The space of tempered growth solutions to the first recurrence relation should be spanned (as a vector space) by the delta function and some linear combinations of its partial derivatives. Does the second recurrence have the same property? I.e. is there one "basic solution" $B$ to the second recurrence such that all other solutions can be expressed as linear combinations of the formal derivatives of $B?$
 A: Polynomial growth is tempered growth, right?
I think you're failing to consider Dirac delta deriviative distributions, like the one that sends a smooth function $f(x)$ to $\frac{df}{dx} (0)$. Their Fourier series will be polynomials, like the ones that satisfy your recurrence:
$a_{n,m}=n-m$
$a_{n,m}=(n-m)^2 + (n+m)$
$a_{n,m}= (n-m)^3 + 3( n^2-m^2)$ 
etc.
Because the operation $a_{n,m} \to 2a_{n,m} - a_{n-1,m} - a_{n,m-1}$ sends polynomials of degree $\leq d$ to polynomials of degree $\leq d-1$, its kernel among the polynomials of degree $\leq d$ must be at least the dimension of the space of polynomials of degree $\leq d$ minus the dimension of the space of polynomials of degree $\leq d-1$, or $d+1$. Moreover, it is clear that the leading term of anything in the kernel must have the form $k (n-m)^d$. This gives a basis for the polynomial solutions.

I'm pretty sure one can show any solution to the second equation with $\theta\neq 0$ must have exponential growth, and explicitly find how large the exponential growth can be. First reparameterize:
\[a_{n,m} = \frac{ a_{n-1,m-1}+a_{n,m-1} e^{2 \pi i n \theta} }{2}\] 
Now we can think of this as the dynamics of an operator from functions on $\mathbb Z$ to functions on $\mathbb Z$:
\[Ta_{n} = \frac{ a_{n-1}+a_{n} e^{2 \pi i n \theta} }{2}\] 
Consider the Hilbert space of functions $a_n$ that satisfy $\sum_n |a_n|^2 e^{ - 2\alpha |n|} <\infty$. $T$ is a bounded operator on this Hilbert space. Let $\rho$ be its spectral radius. Since $\rho= \lim\sup_k |T^k|^{1/k}$ We have:
\[ \lim\sup_k  \left(\sum_n ||a_{n,m-k}||^2 e^{ - 2\alpha |n|} \right)^{1/k} \geq 1/\rho\]
so $a_{n,m}$ has exponential growth of at least $e^{\alpha |n|}$ or $\rho^{-|m|}$ in some direction. We will show that for $\alpha$ sufficiently small, $\rho<1$, so there is always exponential growth.
Suppose $\lambda$ is in the spectrum. Then $T- \lambda$ is not invertible in the Hilbert space. But we can explicitly write an inverse: 
\[ ((T-\lambda)^{-1} a )n = \sum_{m=n}^\infty a_m \prod_{k=n}^m \frac{1}{2\lambda - e^{2 \pi i n \theta}}  \]
$\prod_{k=n}^m \frac{1}{2\lambda - e^{2 \pi i n \theta}}$ decreases rapidly. It's bounded by a multiple of $e^{-(m-n)\int_0^{1} \ln |2 \lambda - e^{2\pi i x}|dx} $ . Since $\ln | \cdot | $ is harmonic, this is just $e^{-\ln |2\lambda|}=1/2\lambda$. As long a $\alpha <  \ln |2 \lambda|$, this inverse is a bounded operator, so $\lambda$ is not in the spectrum. Thus $\rho \leq e^{\alpha}/2$. 
So it either has growth of at least $e^{\alpha |n|}$ or $e^{(\ln 2 - \alpha)|m|}$.
We can easily show that this is in fact exactly the spectral radius by finding an eigenvalue with $\alpha > 2 \ln |\lambda|$. By continuing the product in the opposite direction we get an eigenvalue, and by the same estimate the growth rate is less than $e^{\alpha |n|}$. Thus, there are solutions with exponential growth.
One can do a similar argument for $\theta$ a rational number, using a finite sum instead of an integral. This will give a slightly different spectral radius that is still less than $1$ for $\alpha$ small enough.
A: I don't think constant is the only tempered growth solution to your 2d recurrence. Essentially the recurrence needs a 1-dimensional subspace in $\mathbb{Z}^2$ of boundary conditions. Then your recurrence is saying the value at any point $(x,y)$ is the average of values at $(x-1,y)$ and $(x,y-1)$, which has the effect of smoothing things out as we move to the upper right corner of the 2d lattice.
For instance, take the subspace $S = \{(i,-i): i \in \mathbb{Z}\}$. Then you can prescribe any values on points in $S$ and get a consistent solution first on the part of the integer lattice to the up-left of $S$. If you choose the values on $S$ to be say bounded, then the solution on the upper left side of $S$ will also be bounded, hence certainly "tempered". Now to extend this solution below and to the left of $S$, just assign $0$ to all points in $T =\{(i,i): i < 0\}$ and all the other points in the bottom left corner of the lattice are uniquely determined. Again it's easy to see they are all bounded. 
Your second recurrence can be treated in the same way. One trivial solution is to assign all points constant at $0$. On the other hand I imagine it can be quite interesting to consider 2d recurrences where the coefficients do not add up to 0 (or cannot be arranged on the right and left of the equality so that the moduli of two sides add up to the same number) hence can exhibit exponential growth. But maybe that case can be reduced to 1d recurrence. 
A: This recurrence brings to mind the wave equation.    Denote by $L$ the lattice $\newcommand{\bZ}{\mathbb{Z}}$ $L=\bZ^2$ and  $t:L\to\bZ$ the "time" function
$$  t(x,y)=x+y,\;\; (x,y)\in L. $$
The "initial  hypersurface" $S_0$  is defined by the equation $T=0$.     A point $p=(x,y)\in L$, $t(p)>0$,  is uniquely determined by its time $t(p)=x+y$ and its position $u(p)=x-y$. $\newcommand{\bC}{\mathbb{C}}$
Consider a function  $a:L\to\bC$  satisfying your recurrence relation.   Its value at the point $(x,y)$ with time $t=(x_0,y_0)$ is only affected by its  values   in the region $|x-x_0|\leq t$ on   initial  hypersurface $S_0$. 
For any $R>0$ define 
$$S_0(R,t)= \lbrace (x,y)\in  L;\;\;x+y=t,\;\;|x|\leq R\rbrace, $$
and
$$ m(R, t) :=\max_{(x,y)\in S(R, t)}|a(x,y)|. $$
Your recurrence implies  
$$ |a(x,y|\leq \frac{1}{2}\bigl(\; |a(x-1,y)|+|a(x,y)|\;\bigr),\;\;\forall (x,y)\in R. $$
This implies immediately that
$$ m(R,t) \leq  m(R+1, t-1). $$
In particular, for $t>0$ we have
$$ m(R,t)\leq  m(R+t,0). $$
This controls the size of the "future" values of $a$, i.e., the values  of $a$ in the region  $t\geq 0$.  If we assume  that
$$ m(R,0)\leq  Ma^R,  $$
for some $c\geq 1$, $M>0$ then we deduce that
$$ M(R,t)\leq  M a^{R+t},\;\;\forall t\geq 0. $$
In particular, if $a$ is bounded along $S_0$, it will stay bounded in the future. The past values seem a bit more difficult to control.   I  have to think more about this.
I thought more  about this  and    I reached  a conclusion: the past cannot be  determined from the  initial conditions  at $t=0$.
Suppose that we have a function $a: \bZ\to \bC$ satisfying your recurrence conditions  and such that, at $t=0$ is zero. What could be the values on the time slice $t=-1$?.  Denote by  $A$  the restriction of $a$ to the slice $t=-1$. We set $\newcommand{\ii}{\boldsymbol{i}}$
$$ A_n = a(n,-n-1),\;\;n\in\bZ. $$
Set $c:=e^{\ii\theta}$. The   recurrence relation implies
$$A_n +c^n A_{n-1}= 0,\forall n\in\bZ $$
so that 
$$ A_n =  A_0 (-c)^{\ell(n)},\;\;\ell(0)=0,\;\;\ell(n+1)-\ell(n)=n,\;\;\forall n\in\bZ $$
This  shows that we can generate solutions  of your recurrence that  are far from temperate   for  $t<0$.  Here is how you do it.
Fix a function $f_0 :\bZ\to\bC$. This is the initial condition
$$ a(x,-x)=f_0(x),\;\;\forall  x\in \bZ. $$
Define  $g_{-1}:\bZ\to \bC$  by requiring
$$ g_{-1}(0)=0,\;\;g_{-1}(x)+cg_{-1}(x-1) = 2f_0(x),\;\;\forall x\in \bZ. $$
Pick a constant $M_1>0$ and then set
$$ f_{-1}(x) = M_1 (-c)^{\ell(x)} +g_{-1}(x),\;\;\forall x\in \bZ. $$
Observe that $f_{-1}(0)= M_1+1$ and
$$ f_{-1}(x)+c^xf_{-1}(x-1)=2f_0(x). $$
Proceed inductively. Suppose we have produced functions $f_{-1},\dotsc,  f_{-k}:\bZ\to \bC$,
$$ f_{-j}(0)= M_j+1,\;\;j=1,\dotsc, k. $$
We determine $g_{-k-1}:\bZ\to \bC$ by requiring that
$$ g_{-k-1}(0)=0,\;\; g_{-k-1}(x)+c^xg_{-k-1}(x-1)= 2f_{-k}(x),\;\;\forall x\in \bZ. $$
Pick a positive constant $M_{k+1}$ and then set
$$ f_{-k-1}(x) := M_{k+1}(-c)^{\ell(x)}+ g_{-k-1}(x),\;\;\forall x\in\bZ. $$
For $k>0$  we define inductively   $f_k:\bZ\to \bC$
$$ f_k(x)=\frac{1}{2}\bigl(\; f_{k-1}(x)+c^xf_{k-1}(x-1)\;\bigr). $$
Finally  define  $ a:\bZ^2\to\bC $ by setting
$$ a(x,y)= f_{x+y}(x),\;\;\forall  (x,y)\in\bZ^2. $$
The function $a$ satisfies the recurrence relation and
$$ a(0, -k) = M_k+1,\;\;\forall k\in \bZ_{>0}. $$
By choosing the  sequence $M_k$    suitably, e.g. $M_k = k^{k!}$,  your guaranteed  a non-temperate behavior for $a$.
Remark 1. Suppose  we are given a function $f_0:S_0\to\bC$,   a sequence of points $p_n=(x_n,y_n)$, $n>0$,  so that $t(p_n)=x_n+y_n)=-n$ and a sequence of complex numbers $C_n$, $n>0$. Then there exists  a unique solution $a$ of the recurrence  equation satisfying the "initial conditions" 
$$ a(p_n)= C_n,\;\;\forall n>0, $$
$$ a(x,y)= f_0(x,y),\;\;\forall (x,y)=S_0. $$
Remark 2. To obtain estimates for the growth of this solutions in the past one needs  to understand    the growth of   the solution of the following initial value problem. Given $f:\bZ\to \bC$ let $u:\bZ\to\bC$ be the solution of the initial value problem
$$ u(x)+c^xu(x-1) = 2f(x),\;\; x\in \bZ, $$
$$u(0) =0. $$
Note that
$$ u(1)= 2f(1),\;\; u(2)= -c^2 u(1) + 2f(2)=-2c^{\ell(2)} f(1)+2f(2), $$
$$ u(3)= -c^3u(2)+2f(3)= 2f(3) -2c^3f(2) +2c^{\ell(3)}  f(1) $$
$$ = 2(-c)^{\ell(3)}\bigl(\; (-c)^{-\ell(3)} f(3)+(-c)^{-\ell(2)}f(2)+(-c)^{-\ell(1)} f(1)\;\bigr). \tag{1} $$
The pattern is now clear and one can see  that 
$$ u(n)\leq 2\bigl( |f(1)|+ \cdots +2|f(n)|\;\bigr). $$
This is an optimal bound which is achieved.  Suppose for example that
$$ f(n)= (-c)^{-\ell(n)} r_n,\;\; r_n>0 $$
Then
$$u(n)= 2(-c)^n (r_1+\cdots + r_n), \;\; n>0. $$
The solution with the temperate initial condition 
$$ a(n,-n)= (-c)^{\ell(n)}  ,\;\;n\in\bZ, $$
$$ a(0,-n)=0,\;\; n>0, $$
is  non-temperate  because $|a(1,1-t)|=2^t$, $\forall t\geq 0$.
In general is  satisfies an estimate of  of the type 
$$ a(n,n-t)\sim  2^t \frac{n^t}{t!},\;\; t>0,\;\; n>n(t). $$
Remark 3.    If the "initial" condition for $a$ is the $\delta$ function concentrated at the orgin, then $a$  has exponential growth in the past. 
More precisely, if $a$ satisfies the recurrence and the initial conditions
$$a(x,-x)=0,\;\;\forall x\in\bZ\setminus 0,\;\;a(0,0)=1, $$
$$ a(0,-t)=0,\;\;\forall t<0, $$
then $$|a(1,1-t)|=2^t. $$
