How do I compute this recursive function efficiently?

Question

Let $f(x,y) = xy + f(x-1,y-1) $ where $f$ equals $0$ if either $x$ or $y$ is $0$.

Also $x,y$ belong to $\mathbb{N}$.

Describe an efficient (less then $O(n)$) algorithm for computing $f(x,y)$.

Answer 1

$f(x, y)$ is symmetric so consider case when $y \geq x$. Let $k = y - x \geq 0$. $$\begin{aligned} f(x, x + k) &= \\ &= x(x+k) + f(x-1, x+k-1) = \\ &= x(x+k) + (x-1)(x+k-1) + f(x-2, x+k-2) = \dots \\ \dots &= x(x+k) + (x-1)(x+k-1) + \dots + 1\cdot k + f(0, k) = \\ &= \sum_{m=1}^{x} m(m+k)\end{aligned} $$ So $$ f(x, y) = \sum_{m=1}^x m(m+k) = \sum_{m=1}^x m^2 + k\sum_{m=1}^x m = \frac{x(x+1)(2x+1)}{6} + k\frac{x(x+1)}{2} = \frac{x(x+1)(2x+1+3k)}{6} = \\ = \frac{x(x+1)(3y+1 - x)}{6}. $$

$$ f(x,y) = \begin{cases} \dfrac{x(x+1)(3y+1 - x)}{6}, &y \geq x\\ \dfrac{y(y+1)(3x+1 - y)}{6}, &y < x\end{cases} $$

Answer 2

Proposition. If $x\ge y\ge 0$ then $$\tag1 f(x,y)=\frac{y(y+1)(3x-y+1)}6.$$ Proof. The case $y=0$ is clear. For $y>0$ we have by induction $$\begin{align}f(x,y)&=xy+f(x-1,y-1) \\&=xy+\frac{(y-1)y(3x-y-1)}{6}\\&=\frac{y(y+1)(3x-y+1)}6\end{align} $$ as was to be shown. $_\square$