Solving a general two-term combinatorial recurrence relation - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T09:39:34Z http://mathoverflow.net/feeds/question/41284 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41284/solving-a-general-two-term-combinatorial-recurrence-relation Solving a general two-term combinatorial recurrence relation Mike Spivey 2010-10-06T15:48:00Z 2011-11-25T16:58:44Z <p>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 &lt; 0$ or $k &lt; 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.</p> <p>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},$$</p> <p>is open Problem 6.94 in <em>Concrete Mathematics</em> (2nd edition, p. 319).</p> <p>The closest published result I have found thus far is the following formula due to Neuwirth ("<a href="http://homepage.univie.ac.at/erich.neuwirth/papers/TechRep99-05.pdf" rel="nofollow">Recursively defined combinatorial functions: Extending Galton's board</a>," <em>Discrete Mathematics</em>, 2001) for the case $\alpha' = 0$ of the <em>Concrete Mathematics</em> problem,</p> <p>$$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},$$</p> <p>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.)</p> <p>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.</p> http://mathoverflow.net/questions/41284/solving-a-general-two-term-combinatorial-recurrence-relation/80195#80195 Answer by sigma_z_1980 for Solving a general two-term combinatorial recurrence relation sigma_z_1980 2011-11-06T06:46:39Z 2011-11-06T06:46:39Z <p>have a look at Migdal(2010), paper on analysis of Mafia game, there is a vey similar problem there with some solution</p> http://mathoverflow.net/questions/41284/solving-a-general-two-term-combinatorial-recurrence-relation/81904#81904 Answer by Piotr Migdal for Solving a general two-term combinatorial recurrence relation Piotr Migdal 2011-11-25T16:53:17Z 2011-11-25T16:58:44Z <p>By now it is not a general answer, but I hope it may help. The method is based on the one used in the <em>Appendix A</em> of <a href="http://arxiv.org/pdf/1009.1031" rel="nofollow">arXiv:1009.1031</a>.</p> <p>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}$.</p> <p>The set of equations of their evolution reads:</p> <p>$$\rho_k(t+1) = (\alpha n + \beta k + \gamma) \rho_k(t)+(\alpha' n + \beta' (k+1) + \gamma')\rho_{k+1}(t)$$</p> <p>for integer $k$ and bearing in mind that $n = N-t$.</p> <p>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.</p> <p>However, for some special cases eigenvectors are the same for every $n$, that is for</p> <ul> <li>$\alpha' = 0$,</li> <li>$\beta = \beta' = 0$.</li> </ul> <p>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 <em>the constant term of</em> instead of $|_{z=0}$ as when $\gamma'\neq 0$ or $\alpha'\neq 0$ one needs to tackle negative powers of $z$. </p>