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$.

  • $\begingroup$ The expression after the dots is surely mistyped. I edited it, but maybe i misunderstood your intentions. $\endgroup$ – Daniel Soltész Nov 10 '13 at 1:49
  • 3
    $\begingroup$ Where did this arise? $\endgroup$ – Gerry Myerson Nov 10 '13 at 4:41
  • $\begingroup$ 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. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.