9
$\begingroup$

What is known about explicit (not necessarily closed-form) solutions to the recurrence $$R^n_k= (\alpha n) R^{n-1}_k + (\alpha' n + \beta' k) R^{n-1} _{k-1},$$ with initial condition $R_0^0 = 1$ and with $R^n_k = 0$ for $n < 0$ or $k < 0$? Special cases of this are closely related to recurrences satisfied by some interesting combinatorial numbers, such as the binomial coefficients and the Stirling numbers.

The more general recurrence $$R^n_k= (\alpha n + \beta k + \gamma) R^{n-1}_k + (\alpha' n + \beta' k + \gamma') R^{n-1} _{k-1},$$

is open Problem 6.94 in Concrete Mathematics (2nd edition, p. 319).

The closest published result I have found thus far is the following formula due to Neuwirth ("Recursively defined combinatorial functions: Extending Galton's board," Discrete Mathematics, 2001) for the case $\alpha' = 0$ of the Concrete Mathematics problem,

$$R^n_k = \prod_{i=1}^k (\beta' i + \gamma') \sum_{i=0}^n \sum_{j=0}^n s^n_i \binom{i}{j} S^j_k \alpha^{n-i} (\gamma - \alpha)^{i-j} \beta^{j-k},$$

which, of course, gives me an answer to my question when $\alpha'=0$. (Here, $s^n_i$ and $S^j_k$ are unsigned Stirling numbers of the first and second kinds, respectively.)

I have tried generating functions without any success thus far. An answer like Neuwirth's that involves sums and binomial coefficients or Stirling numbers would be fine, as would a partial answer or just another idea to try.

$\endgroup$
0

3 Answers 3

5
$\begingroup$

A general solution of the Graham-Knuth-Patashnik 6.94 problem

$$ R^{n}_k=(\alpha \, n + \beta\, k + \gamma)\, R^{n−1}_k+ (\alpha′\, n+ \beta′\, k +\gamma′)\, R^{n−1}_{k−1} + \delta_{n,0}\delta_{k,0}\,, $$

with $R_{n}^k=0$ if $n<0$ or $k<0$, can be found in the paper ``Bivariate generating functions for a class of linear recurrences: General structure'', by J.F. Barbero G., J. Salas, and E.J.S. Villaseñor, published in J. Combin. Theory A 125 (2014) 146-165 (see also arXiv:1307.2010). The solution was obtained by using generating functions.

$\endgroup$
1
$\begingroup$

By now it is not a general answer, but I hope it may help. The method is based on the one used in the Appendix A of arXiv:1009.1031.

To calculate $R^N_K$ one can introduce densities $\rho_k(t)$ accumulating the multiplier of $R^{N-t}_k$ after using the recurrence formula $2^{t}-1$ times. Then $R^N_K$ is just $\rho_0(N)$ for the initial condition $\rho_k(0)=\delta_{Kk}$.

The set of equations of their evolution reads:

$$\rho_k(t+1) = (\alpha n + \beta k + \gamma) \rho_k(t)+(\alpha' n + \beta' (k+1) + \gamma')\rho_{k+1}(t)$$

for integer $k$ and bearing in mind that $n = N-t$.

After introducing a generating function $$G(t,z)=\sum_{k=-\infty}^\infty \rho_k(t)z^k,$$ with the initial condition $G(0,z)=z^K$, the set of equations is transformed into $$G(t+1,z) = \left( \gamma + \alpha n +(\gamma'+\alpha'n)\frac{1}{z}+(\beta z+\beta')\frac{\partial }{\partial z} \right)G(t,z).$$ So in general case $R^N_K$ is the constant term of $$\left[ \prod_{n=1}^N \left( \gamma + \alpha n +(\gamma'+\alpha'n)\frac{1}{z}+(\beta z+\beta')\frac{\partial }{\partial z} \right)\right]z^K.$$ The question is if it is possible to simplify it. As in general at different times (i.e. for different $n$) eigenvectors of the differential operators are different, one cannot use the same approach as in the paper.

However, for some special cases eigenvectors are the same for every $n$, that is for

  • $\alpha' = 0$,
  • $\beta = \beta' = 0$.

If decompose $z^M$ in the eigenfunctions $z^M = \sum_i a_i f_i(z)$, then instead of a product of operators one gets a product of eigenvalues $$R^N_K = \sum_i a_i \times \text{[the constant term of $f_i(z)$]}\times\prod_{n=1}^N \lambda_i(n).$$ I keep writing the constant term of instead of $|_{z=0}$ as when $\gamma'\neq 0$ or $\alpha'\neq 0$ one needs to tackle negative powers of $z$.

$\endgroup$
1
  • $\begingroup$ +1 for the generating function formulation. As you say, the question is whether it is possible to simplify the expression for the constant term of the generating function. $\endgroup$ Dec 1, 2011 at 23:24
0
$\begingroup$

have a look at Migdal(2010), paper on analysis of Mafia game, there is a vey similar problem there with some solution

$\endgroup$
6
  • 1
    $\begingroup$ Could you at least give the full citation for this paper you speak of? $\endgroup$ Nov 6, 2011 at 12:20
  • 1
    $\begingroup$ arxiv.org/pdf/1009.1031 for the paper on Mafia game jstor.org/stable/3215985 for Gani's paper on random allocation model + have a look at refernces to Woodbury and Rutherford hope it helps $\endgroup$ Nov 6, 2011 at 22:44
  • $\begingroup$ Unfortunately, the recurrences in those papers don't quite match up with the one I'm asking about. And with partial difference equations like these, slight changes in the parameters can make a huge difference in the solutions. Thank you for the interesting references, though. $\endgroup$ Nov 7, 2011 at 22:51
  • $\begingroup$ Could you explain what exactly doesn't match up? Also you may want ot have a look at undergrad textbook by Elaydi, An Introduction to Difference Equations, Chapeter 2.4 deals with nonhomogeneous equations, maybe it helps. I asked a similar question here and on MSE, but still pretty vague about what to do. I know it uses GF and determinant of eigenmatrices somehow though. It's strange since the implication is very intuitive, especially in biological/life sciences. mathoverflow.net/questions/80194/… $\endgroup$ Nov 8, 2011 at 2:13
  • $\begingroup$ The recurrence relations in those papers don't have the parameters in the same form as in my question. As I said in my earlier comment, slight changes to the parameters in a partial difference equation can make a huge difference in the solution, so to answer my question I would need a reference in which the parameters are exactly of the same form. $\endgroup$ Nov 24, 2011 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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