6
$\begingroup$

I have the following multivariate recurrence relations all from the same system: First, suppose that $0\le k\le j\le m$, and let $N$ be an independent integer. Then we have for expressions $a(k,~ m,~ j)$

$$\begin{align} a(0,~ m,~ j) &= m\cdot a(0,~ m-1,~ j-1)+(j-mN)\cdot a(0,~ m-1,~ j) \quad \text{ for } 1 \le j < m \\ \\ a(k,~ m,~ j)&=m\cdot a(k,~ m-1,~ j-1)+(j-mN)\cdot a(k,~ m-1,~ j)+a(k-1,~ m-1,~ j-1) \\ \\ a(0,~ m,~ m) &= m\cdot a(0,~ m-1,~ m-1) \\ \end{align}$$

There are a few explicit closed forms within this recurrence, such as

$$\begin{align} a(0,~ m,~ 0) &= (-1)^m ~ m! ~ N^m \\ a(0,~ m,~ 1) &= \sum_{n=0}^{m-2}\sum_{k=0}^n s(m,m-k)(-N)^k\\ a(0,~ m,~ m) &= m! \\ a(1,~ m,~ 1) &=(1-N)(1-2N)...(1-mN)-m!N^m\\ &=\sum_{i=0}^{m-2}s(m,m-i)N^i\\ a(m-1,~ m,~ m-1) &= (1+2+\dots+m-1)+(1+2+\dots+m) ~ N \\ a(m-1,~ m,~ m) &= (1+2+\dots+m) \\ a(m,~ m,~ m) &= 1 \end{align}$$

Note above that $s(m,k)$ are Stirling numbers of the first kind.

Something that is true is the degree of the polynomial $a(k,m,j)=m-j$. The last restriction is if the above conditions of $0\le k\le j\le m$ is not met, then $a(k,m,j)=0$.

Using this recursively, I can generate polynomials. Below is an example. I want to solve this and find an explicit formula, but the problem is, I've never solved multivariate recurrences. I first tried to do this simply by taking the recurrence deeper and deeper by substitution, but it gets messy very quickly.

First, is this recurrence even solvable? Is there an explicit form or are there too many variables to give me a unique expression? There is so much here and it seems overwhelming. Can anyone help me make this managable? (if possible?)

EDIT: As for the motivation and where this is coming from, $$B(x)=\frac{x^N/N!}{e^x-1-x-...-\frac{x^{N-1}}{(N-1)!}}=\sum_{n=0}^\infty B_n(N)\frac{x^n}{n!}$$ satisfies the following differential equation $$-NB(x)^2=(x-N)B(x)+xB'(x)$$ Taking the derivative on both sides, rewriting and substituting yields the similar higher order differential equation $$2N^2B(x)^3=[2N^2+(1-4N)x+2x^2]B(x)+[(1-3N)x+3x^2]B'(x)+x^2B''(x)$$ You can use that generating techniques to find higher order differential equations for $B(x)^n$. Notice that in front of each derivative of $B$ is a polynomial in $x$ and each term in the polynomial of $x$ is comprised of polynomials in $N$ (originally in the post as $x$, I've changed them throughout to $N$ now, sorry for the confusion). It is these terms I'm trying to find a closed form for. For example, $$a(0,2,0)=2N^2, ~ a(0,2,1)=1-4N, ~ a(0,2,2)=2$$ $$a(1,2,0)=0, ~ a(1,2,1)=1-3N, ~ a(1,2,2)=3$$ $$a(2,2,0)=0, ~ a(2,2,1)=0, ~ a(2,2,2)=1$$ Notice that $$a(0,2,1)=2\cdot a(0,1,0)+(1-2N)\cdot a(0,1,1)=2(-N)+(1-2N)=1-4N$$

There are a lot of specific rules for particular $a(k,m,j)$. This makes me somewhat positive that a closed form exists...

EDIT 2: I added two explicit forms above involving unsigned Stirling Numbers of the first kind. I am also going to upload a list of the polynomials $a(k,m,j)$ that I generated recursively using Mathematica and perhaps others, as I have done, can see patterns within the data.

$\endgroup$
  • 2
    $\begingroup$ I recommend the word "complicated", rather than "complex", which has a different meaning in mathematics. $\endgroup$ – DanielV Mar 30 '15 at 22:18
  • $\begingroup$ I will change. Thanks $\endgroup$ – Iceman Mar 30 '15 at 22:21
  • 1
    $\begingroup$ Sometimes math problems are easier to solve conceptually than algebraically. If it's not too complicated, editing the post to contain the original problem (at the end or so) may lead to other approaches besides recursion solvers to this, such as combinatorial counting techniques. $\endgroup$ – DanielV Mar 30 '15 at 23:58
  • 1
    $\begingroup$ I think you have a typo with your $k$, $n$, $N$, and $X$ in your new material. $\endgroup$ – DanielV Mar 31 '15 at 2:38
  • 1
    $\begingroup$ I'm guessing your sum should be $\sum_{n \ge 0}$ rather than $\sum_{k \ge 0}$ $\endgroup$ – DanielV Mar 31 '15 at 5:11
3
+200
$\begingroup$

I think, you have no chance to get explicit formulas for a(k,i,j).

From your differential equation you get $$ (-1)^k k! N^k B^{k+1} = p_{0,k} B +p_{1,k} B'+p_{2,k} B''+p_{3,k} B'''+...+p_{k,k} B^{(k)} $$ where $p_{j,k}=\sum_r a(j,k,r)x^r$. The recurrence relation is $$ p_{j,k+1}=(k+1) A p_{j,k}+B p_{j-1,k}+B p_{j,k}' $$ where $A=x-N$, $B=x$ and the initial values are $p_{0,1}=A$ and $p_{1,1}=B$.

Note that $A'=B'=1$.

Using the relation one obtains easily the lower cases: For example

$ p_{0,2}=2A^2+B, $

$ p_{1,2}=3AB+B,$

$ p_{2,2}=B^2$,

which coincides with the values given before, and furthermore

$p_{0,3}=6A^3+7AB+B,$

$p_{1,3}=11 A^2 B+6AB+4B^2+B$,

$p_{2,3}=6AB^2+3B^2$,

$ p_{3,3}=B^3$,

and one can go on. From these values one obtains the a(j,k,i)'s.

One can construct something like an Pascal triangle, each two entries generate the lower entry between them, but you have three different (noncommuting) operator on polynomials:

  1. Multiplying by (k+1)A
  2. Derivating (and then multiplying by B)
  3. Multiplying by B

The two first operate down-left and the third operates down-right in the triangle.

Clearly the closed simple formulas found correspond to the far left and the far right edges (of the triangle), hence to some pure power of one of the operators. For example, the third operator raised to $m$ yields directly $a(m,m,m)=1$, and the first one gives $a(0,m,m)=m!$ and $a(0,m,0)=(−1)^m m! N^m$ The more complicated formulas found correspond to the inmediately next entries and involve some pure power of one operator and only one of the others.

So a closed formula for all of them, if it exists, will require probably the definition of new (recurrently defined) series of numbers.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. I"ve actually been generating triangles as you mention above in an effort to find something. Perhaps future research will pay off. I appreciate the effort and I like how you broke down the problem using operators. $\endgroup$ – Iceman Apr 8 '15 at 23:07
  • $\begingroup$ If make any progress, please tell me. One should try matching the resulting integer sequences in OEIS. $\endgroup$ – san May 20 '15 at 0:47
  • $\begingroup$ Actually, that's how I found some of the explicit forms above, especially the ones involving Stirling numbers of the first kind. $\endgroup$ – Iceman May 20 '15 at 12:40

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.