Solving a 2 independent variables (2nd degree) recurrence relation

Question

Changes to the recurrences and definition are changed! See here: $f(n, 1) = 2n^2 $ and $f (n, k) = 0$ for $k \geq 2n$ and for $k < 0$ and $f(n, 2n-1) = 1$ for all $n$.

Question: Is it possible to solve the following recurrence? If so in what manner should I approach it?

Conditions Let $f(n,k)$ be the 2-independent-variable function, where $f(n, 0) = 1$, $f(n, 1) = 2 n^2 $ and $f (n, k) = 0$ for $k \geq 2n$ and for $k < 0$ and $f(n, 2n-1) = 1$ for all $n$. All $n, k$ are positive integers.

Solve the recurrence (giving either a generating function, hopefully also an explicit formula):

$f(n,k) = f(n-1, k) + 2(2n-k) \cdot f(n-1, k-1) + (2n-k+1)(2n-k) \cdot f(n-1, k-2).$

I read the following link on gen. functions and tried to come up with something as follows:

Multiplying throughout by $x^k$ and summing the RHS over $k\geq 0$, define the generating function $B_n(x) = \sum_{k\geq0} f(n,k)x^k$, with $n \geq 1, B_0(x) = 0$.

Let the notation $[x^k]g(x)$ denote the $k^{\text{th}}$ coefficients of the function $g(x)$.

Then if we do the above for the LHS too and equate both sides, we yield:

$ B_n(x) = B_{n-1}(x) + \sum_{k\geq0} 2(2n-k) \cdot [x^k](xB_{n-1}(x)) + \sum_{k\geq0} (2n-k+1)(2n-k) \cdot [x^k](x^2 B_{n-1}(x)) $

where the notation $\sum_{k\geq0} 2(2n-k) \cdot [x^k](xB_{n-1}(x))$ means $2(2n-k)$ multiplied by the $k^{th}$ coefficient of the function $(xB_{n-1}(x))$.

Notice this simplifies to:

$ B_n(x) = B_{n-1}(x) + \sum_{k\geq0} 2(n-k) \cdot [x^{k-1}](B_{n-1}(x)) + \sum_{k\geq0} (n-k+1)(n-k) \cdot [x^{k-2}](B_{n-1}(x)) $

Is the above workings correct/logical? If it is, is there a way to simplify the $\sum_{k\geq0} (2n-k+1)(2n-k)$ expression (which is something multiply by the $k^{th}$ coefficient)? Any other ideas to go about solving this recurrence function? Thanks!

Answer 1

In what follows I don't provide a closed formula, but at least I can show how an approach with generating functions transforms the recurrence into a corresponding partial differential equation.

Problem: Let $f(n,k)$ be defined by the recurrence

\begin{align*} f(n,k)&=f(n-1,k)+2(2n-k)f(n-1,k-1)\\ &+(2n-k+1)(2n-k)f(n-1,k-2)\qquad\qquad n\geq 1, k \geq 2 \end{align*} with \begin{array}{ll} f(n,0)=1,f(n,1)=n,&\quad n\geq 0\\ f(n,k)=0,&\quad k>n, k<0\\ f(n,n)=1, &\quad n\geq 0 \end{array}

We use the bivariate formal power series \begin{align*} F(x,y)=\sum_{n\geq 0}\sum_{k\geq 0}f(n,k)x^ny^k \end{align*} to get \begin{align*} \sum_{n\geq 1}\sum_{k\geq 2}&f(n,k)x^ny^k\tag{1}\\ &=\sum_{n\geq 1}\sum_{k\geq 2}f(n-1,k)x^ny^k\tag{2}\\ &+2\sum_{n\geq 1}\sum_{k\geq 2}(2n-k)f(n-1,k-1)x^ny^k\tag{3}\\ &+\sum_{n\geq 1}\sum_{k\geq 2}(2n-k+1)(2n-k)f(n-1,k-2)x^ny^k\tag{4}\\ \end{align*}

Note: Observe the index range: $n\geq 1$ and $k\geq 2$. In the following calculations we want to collect the contributions of $f(n,k), f(n-1,k-1)$ and $f(n-1,k-2)$ by transforming all to $f(n,k)$. In order to do so we have to do some index shifting. Since we have to cope with $f(n-1,.)$ the index $n$ starts beginning from $1$ and since we have to cope with $f(.,k-1)$ and $f(.,k-2)$ the index $k$ starts from $2$. This way we won't have conflicts with the definition of $F(x,y)$.

We will consider each sum separately:

• sum of LHS: (1)

\begin{align*} \sum_{n\geq 1}\sum_{k\geq 2}&f(n,k)x^ny^k\\ &=F(x,y)-\sum_{k\geq 0}f(0,k)y^k-\sum_{n\geq 1}f(n,0)x^n-\sum_{n\geq 1}f(n,1)x^ny\\ &=F(x,y)-1-\sum_{n\geq 1}x^n-y\sum_{n\geq 1}nx^n\\ &=F(x,y)-1-\left(\frac{1}{1-x}-1\right)-xy\sum_{n \geq 1}nx^{n-1}\\ &=F(x,y)-\frac{1}{1-x}-xyD_x\sum_{n\geq 1}x^n\\ &=F(x,y)-\frac{1}{1-x}-xyD_x\left(\frac{1}{1-x}-1\right)\\ &=F(x,y)-\frac{1}{1-x}-\frac{xy}{(1-x)^2} \end{align*}

• first sum of RHS: (2)

\begin{align*} \sum_{n\geq 1}\sum_{k\geq 2}&f(n-1,k)x^ny^k\\ &=\sum_{n\geq 0}\sum_{k\geq 2}f(n,k)x^{n+1}y^k\\ &=x\left(F(x,y)-\sum_{n\geq 0}f(n,0)x^n-\sum_{n\geq 0}f(n,1)x^ny\right)\\ &=x\left(F(x,y)-\frac{1}{1-x}-xy\sum_{n \geq 0}nx^{n-1}\right)\\ &=x\left(F(x,y)-\frac{1}{1-x}-xyD_x\sum_{n\geq 0}x^n\right)\\ &=x\left(F(x,y)-\frac{1}{1-x}-xyD_x\frac{1}{1-x}\right)\\ &=x\left(F(x,y)-\frac{1}{1-x}-\frac{xy}{(1-x)^2}\right)\\ \end{align*}

• second sum of RHS: (3)

\begin{align*} 2\sum_{n\geq 1}\sum_{k\geq 2}&(2n-k)f(n-1,k-1)x^ny^k\\ &=2\sum_{n\geq 0}\sum_{k\geq 1}(2n-k+1)f(n,k)x^{n+1}y^{k+1}\\ &=4xy\sum_{n\geq 0}\sum_{k\geq 1}nf(n,k)x^ny^k-2xy\sum_{n \geq 0}\sum_{k \geq 1}kf(n,k)x^ny^k\\ &\qquad+2xy\sum_{n \geq 0}\sum_{k \geq 1}f(n,k)x^ny^k\\ &=4x^2yD_x\sum_{n\geq 0}\sum_{k\geq 1}f(n,k)x^ny^k-2xy^2D_y\sum_{n \geq 0}\sum_{k \geq 1}f(n,k)x^ny^k\\ &\qquad+2xy\left(F(x,y)-\sum_{n \geq 0}x^n\right)\\ &=4x^2yD_x\left(F(x,y)-\sum_{n\geq 0}x^n\right)-2xy^2D_y\left(F(x,y)-\sum_{n\geq 0}x^n\right)\\ &\qquad+2xy\left(F(x,y)-\sum_{n \geq 0}x^n\right)\\ &=4x^2yD_x\left(F(x,y)-\frac{1}{1-x}\right)-2xy^2D_y\left(F(x,y)-\frac{1}{1-x}\right)\\ &\qquad+2xy\left(F(x,y)-\frac{1}{1-x}\right)\\ &=(4x^2yD_x-2xy^2D_y+2xy)F(x,y)\\ &\qquad-\frac{4x^2y}{(1-x)^2}-\frac{2xy}{1-x} \end{align*}

• third sum of RHS: (4)

\begin{align*} \sum_{n\geq 1}\sum_{k\geq 2}&(2n-k+1)(2n-k)f(n-1,k-2)x^ny^k\\ &=\sum_{n\geq 0}\sum_{k\geq 0}(2n-k+1)(2n-k)f(n,k)x^{n+1}y^{k+2}\\ &=xy^2\sum_{n\geq 0}\sum_{k\geq 0}\left(4n(n-1)-4nk+6n+k(k-1)\right)f(n,k)x^ny^k\\ &=4x^3y^2\sum_{n\geq 0}\sum_{k\geq 0}n(n-1)f(n,k)x^{n-2}y^k\\ &\qquad-4x^2y^3\sum_{n\geq 0}\sum_{k\geq 0}nkf(n,k)x^{n-1}y^{k-1}\\ &\qquad+6x^2y^2\sum_{n\geq 0}\sum_{k\geq 0}nf(n,k)x^{n-1}y^{k}\\ &\qquad+xy^4\sum_{n\geq 0}\sum_{k\geq 0}k(k-1)f(n,k)x^{n}y^{k-2}\\ &=\left(4x^3y^2D_x^2-4x^2y^3D_xD_y+6x^2y^2D_x+xy^4D_y^2\right)F(x,y) \end{align*}

Putting all of (1) - (4) together we get

\begin{align*} F(x,y)-\frac{1}{1-x}-&\frac{xy}{(1-x)^2}\\ &=x\left(F(x,y)-\frac{1}{1-x}-\frac{xy}{(1-x)^2}\right)\\ &+(4x^2yD_x-2xy^2D_y+2xyI)F(x,y)\\ &\qquad-\frac{4x^2y}{(1-x)^2}-\frac{2xy}{1-x}\\ &+\left(4x^3y^2D_x^2-4x^2y^3D_xD_y+6x^2y^2D_x+xy^4D_y^2\right)F(x,y) \end{align*}

This can be simplified to

\begin{align*} \left(1-x\right.&-2xy-2x^2y(2+3y)D_x+2xy^2D_y\\ &-xy^2(4x^2D_x^2-4xyD_xD_y+y^2D_y^2))F(x,y)\\ &=1-\frac{2xy}{1-x}+xy\frac{1-5x}{(1-x)^2} \end{align*}

Conclusion: At the time it's not quite clear to me how to proceed with this partial differential equation. But at least we have another representation of the problem we can think about it.

Answer 2

For any fixed $k>1$ $f(n,k)$ as a function of $n$ (for $n\ge k$) is some polynomial $P_{2k-1}(n)$ оf order $2k-1$. Indeed, for $k=2$ we have $$ f(n,2) = f(n-1, 2) + 2(2n-2) + (2n-k+1)(2n-k). $$ Every next value is obtained by adding a polynomial of the second order. Summing up will give some polynomial $P_3(n)$. By induction $$ f(n,k) = f(n-1, k) + 2(2n-k) P_{2k-1}(n-1) + (2n-k+1)(2n-k) P_{2k-3}(n-1). $$ The poly in the rhs is of order $2k$. Summing it up gives a $2k+1$ order polynomial.

The first several $P_{2k-1}$ are $$ \small \begin{eqnarray} f[n,2]&=&\frac{1}{3} \left(4 n^3+3 n^2-7 n-27\right), \\ f[n,3]&=& \frac{1}{15} \left(16 n^5-35 n^4-20 n^3-190 n^2+499 n-285\right), \\ f[n,4]&=&\frac{1}{630} \left(384 n^7-2212 n^6+3948 n^5-11305 n^4+52206 n^3-110593 n^2+104112 n-367290\right), \\ f[n,5]&=&\frac{1}{1890} \left(512 n^9-5478 n^8+22824 n^7-66276 n^6+249438 n^5-873747 n^4+\right.\\ &&\left. 1907296 n^3-4371069 n^2+9532260 n-17915310\right). \end{eqnarray} $$

It seems quite a possibility that there is no closed form for $f(n,k)$.

As for generating function of the form $\sum_{n,k}f(n,k)x^ny^k$ it probably has a convergence radius zero, because the polynomials coefficients probably grow fast enough.

One can consider, of course, an exponential generating function $$ B[x,y]=\sum_{n,k}f(n,k)\frac{x^ny^k}{n!k!}= \ldots+\sum_{k=2}^\infty \frac{y^k}{k!}\sum_{n=k}^\infty P_{2k-1}(n)\frac{x^n}{n!}, $$ but, given the expressions for $P_{2k-1}$, it seems to be at least not evident that it has a closed form.