2

I am seeking an explicit solution to this 2D recurrence equation: \begin{eqnarray} f(0,b) & = & b\\ f(a,0) & = & a\\ f(a,b) & = & f(a-1,b) - f(a,b-1) \end{eqnarray} So, for example, for $a=3$, $$f(3,0)=3 \;,$$ $$f(3,1)=f(2,1)-f(3,0)=-2-3=-5 \;,$$ etc. Here is $f(3,b)$ for $b=0,\ldots,10$: $$ 3, -5, 9, -12, 18, -22, 30, -35, 45, -51, 63 \;. $$ Note the sums of adjacent terms of this list follow a clear pattern: $$ -2, 4, -3, 6, -4, 8, -5, 10, -6, 12 \;. $$

          Rec2D
          Plot cropped above and below. $f(10,10)=146760$.
Can anyone see or calculate an explicit solution as a function of $(a,b)$?
Joseph O'Rourke
  • 30,327

1 Answers1

2

Consider the generating function $g_n(x) = \sum_{k=0}^n f(k,n-k) x^k$. Thus $g_0(x) = f(0,0) = 0$ and $$g_n(x) = n + n x^n + \sum_{k=1}^{n-1} (f(k-1,n-k) - f(k,n-1-k)) x^k = 2n-1 + x^n + (x-1) g_{n-1}(x)$$ which has solution (according to Maple) $$ g_n(x) = -2\,{\frac {n+1}{x-2}}-{\frac {-x+4}{ \left( x-2 \right) ^{2}}}+{x}^{ n+1}-{\frac {x \left( -3+x \right) \left( x-1 \right) ^{n+1}}{ \left( x-2 \right) ^{2}}} $$ Despite appearances, this is in fact a polynomial in $x$, i.e. the singularity at $x=2$ is removable. Then $f(k,m)$ is the coefficient of $x^k$ in $g_{m+k}(x)$.

Robert Israel
  • 448,999
  • I checked $f(3,1)=-5$. $m+k=n=4$, and $g_4(x) = 4x^4-5x^3+4x^2+x+4$, and indeed the coefficient of $x^3$ is $-5$. Impressive! – Joseph O'Rourke May 13 '16 at 11:16
  • Another instance: $n=10$, $g_{10}(x)=10 x^{10}-44 x^9+114 x^8-193 x^7+224 x^6-180 x^5+100 x^4-35 x^3+10 x^2+4 x+10$, and one can check that, e.g., $f(6,4)=224$, which is the coefficient of $x^6$, or $f(7,3)=-193$, which is the coefficient of $x^7$. – Joseph O'Rourke May 13 '16 at 12:20