# Solving a two dimensional non-homogenous linear recurrence

How one can solve the following recurrence: \begin{align} X[i,0] &=0 \quad \forall i =1,\ldots, m\\ X[m,n] &= a_n X[m,n-1]+b_n \sum_{i=k_m}^{m-1}X[i,i] +c_n \end{align}

Where $a_i\ge 1 ,~ 0 \le c_i , b_i <1, k_i \ge 1$ are constants for all $i = 1,\ldots, n$.

• The expression after the dots is surely mistyped. I edited it, but maybe i misunderstood your intentions. – Daniel Soltész Nov 10 '13 at 1:49
• Where did this arise? – Gerry Myerson Nov 10 '13 at 4:41
• It arises in a problem called "online dynamic TCP acknowledgement". There is an algorithm proposed by Buchbinder that uses a special case of this update rule. Namely, $a_i = a_k, b_i = b_k$ and $c_i=c_k$ for all $i \neq k$. This is a generalization for the weighted dynamic TCP ack problem, where each packet has a weight that can define the delay penalty. – Majid Khonji Nov 10 '13 at 13:52

I assume that $n$ is a nonnegative integer although this should be clearly stated in the question. Even in simplest cases this recurrence is indeterminate, because it does not say anying about the terms $X[m,n]$, $m-n\neq 0,1$.

Suppose that $a_n=1$, $k_n=n-1$, $c_n=0$. The recurrence then reads

$$X[n,n]-X[n-1,n-1]=X[n,n-1].$$

This implies

$$X[n,n]= X[0,0]+ X[1,0]+X[2,1]+\cdots + X[n,n-1].$$

The terms $X[m,n]$, $m-n\neq 0$ can be chosen arbitrarily. I believe there is some typo in the recurrence relation.

• Thank you for the clarification. I'll try to fix it now. – Majid Khonji Nov 10 '13 at 15:59