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

  • $\begingroup$ Looks like a linear, bivariate recursion with starting values. Is there any catch to it? $\endgroup$
    – Sudix
    Sep 3 '19 at 19:15
  • $\begingroup$ @Sudix hopefully no catches - if this falls into a well-known class of equations with solutions - I'd love a link $\endgroup$
    – confucious
    Sep 3 '19 at 19:17
  • $\begingroup$ It's a well known class of recurrence relations. We have a set of tools (generating functions) that give for a subset of this class specific generating functions (it fails when we arrive at a differential/functional equation with no known solution). This we can then try to develop into a concrete formula for the sequence. $\endgroup$
    – Sudix
    Sep 3 '19 at 21:16
  • $\begingroup$ And if I made no mistake, there exists a rational generating function for this recurrence. However, I wouldn't know how to turn this into a formula for the sequence $\endgroup$
    – Sudix
    Sep 3 '19 at 21:33

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.
  • $\begingroup$ Thanks, this does answer my question. Do you think there is some argument for estimating $f(x, x)$ for large $x$ that doesn't go through an explicit solution? I ask because my real equation is a bit more complicated, and I thought I'd gain some insight from this simpler one, but it's hard to gain insight from the generating function. $\endgroup$
    – confucious
    Sep 4 '19 at 14:45
  • $\begingroup$ For an approximation, an explicit solution is rarely needed. The classic methods do a singularity analysis of the generating function, and from that deduce the asymptotic growth. At least in the univariate case there's a lot of theory that you can use (though depending on the type of generating function, the results might be stronger or weaker). $\endgroup$
    – Sudix
    Sep 4 '19 at 18:23
  • 1
    $\begingroup$ A full account on the theory you'll find in e.g. "Analytic Combinatorics" by Sedgewick (focus on univariate case) and "Analytic Combinatorics in Several Variables" (focus on multivariate case). There are methods starting directly from the recursion as well though. The most elementary would be guessing a bound on $f(x,y)$ and then doing an induction. Yet another one would be using the Master-theorem. A short account for the mentioned methods can be found in other books, e.g. "Combinatorics with Applications" . $\endgroup$
    – Sudix
    Sep 4 '19 at 18:35
  • $\begingroup$ Just realized I made a typo in the last book. It's "Foundations of Combinatorics with Applications" by A. Bender $\endgroup$
    – Sudix
    Sep 4 '19 at 22:15

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.