Two dimensional recursion $f(x,y) = 0.5 f(x-1,y) + 0.5 f(x, y-1)$ solution or asymptotics

Question

I have the following recursion relation and boundary conditions:

$$f(x,y) = \frac{1}2 f(x-1,y) + \frac{1}2 f(x,y-1)$$ $$f(x,0) = x$$ $$f(0,y) = 0$$

Where $x$ and $y$ are non-negative integers. Does this have an exact solution? If not, is there an asymptotic solution for large $x$ and $y$?

Answer 1

We have $$ f(n + 1, k) = \frac{\displaystyle\sum_{i=0}^n(i + 2)·\binom{n - i + k}{ n - i}\cdot \frac 1{2^{n - i + k - 3}}}{16} $$

This has no closed formula (with elementary functions) as far as I know.

The derivation is lengthy, so I'll only give a rough sketch:

• Model the recursion with generating functions. You'll arrive at the bivariate generating function

$$ F(x,y) = \frac{x·(x - 2)}{(x - 1)^2·(x + y - 2)} $$

• Factorize the generating function and write it as a product of rational fractions so that you can solve each of them individually.
  In this case this is via the factorization

$$ F(x,y) = \frac{x·(x - 2)}{(x - 1)^2} ·\frac 1{x + y - 2} $$

• Solve each factor of the product (i.e. develop it into its series), then apply convolution.