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!

  • $\begingroup$ Any comments to the above? It doesn't have to be a proper answer (like an explicit to the relations) but maybe some ideas (elaborated ones) on how to tackle the recurrence? $\endgroup$
    – Happytreat
    Nov 17 '14 at 14:30
  • 1
    $\begingroup$ You are missing some powers of $x$. For example $\sum_{k\geq0} 2(2n-k) \cdot [x^k](xB_{n-1}(x))$ should be $\sum_{k\geq0} 2(2n-k) \cdot x^k[x^k](xB_{n-1}(x))$. $\endgroup$ Nov 18 '14 at 8:02
  • $\begingroup$ The recurrence looks quite tough to solve in this manner. Where did you find this problem? $\endgroup$ Nov 18 '14 at 8:11
  • $\begingroup$ It is part of my research project currently... Am faced with this recurrence as part of a bigger problem... $\endgroup$
    – Happytreat
    Nov 18 '14 at 17:07

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.

  • $\begingroup$ Sorry I've made a mistake... See above heading for all changes. (recurrence relations remains the same though) $\endgroup$
    – Happytreat
    Nov 18 '14 at 14:49
  • $\begingroup$ @Happytreat: Ok, I'll check your changes and update my answer accordingly. Regards, $\endgroup$
    – epi163sqrt
    Nov 18 '14 at 16:15
  • 1
    $\begingroup$ @Happytreat: You should check your boundary conditions again. $f(n,k)=0$ for $k\geq n$ and $f(n,2n-1)=1$ for all $n$ are contradictory. Regards, $\endgroup$
    – epi163sqrt
    Nov 18 '14 at 16:37
  • $\begingroup$ for $k \geq 2n$ * yes, I'll change it. Sorry for the inconvenience $\endgroup$
    – Happytreat
    Nov 18 '14 at 16:38
  • 1
    $\begingroup$ @Happytreat: Don't worry and don't be in a hurry. Better to check it thoughtfully and correct it afterwards! :-) $\endgroup$
    – epi163sqrt
    Nov 18 '14 at 16:44

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.

  • $\begingroup$ Sorry I've made a mistake... See above heading for all changes. (recurrence relations remains the same though) $\endgroup$
    – Happytreat
    Nov 18 '14 at 14:51
  • $\begingroup$ btw, how did you manage to solve the recurrence (seemingly easily) for $k = 2,3,4,5$? By brute? $\endgroup$
    – Happytreat
    Nov 18 '14 at 15:11

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.