How to compute the coefficients of this generating function

Question

Working on some combinatorial problem, I arrived at the following generating function

$$K_m(x) = \sum_{n\geq 0}K_{mn}x^n =\frac{x}{1-\sqrt{1+x^2}\cdot\frac{\displaystyle{y_+(x)^{m+1}+y_-(x)^{m+1}}}{\displaystyle{y_+(x)^{m+1}-y_-(x)^{m+1}}}}$$ with $$y_\pm(x) =x\pm\sqrt{1+x^2}.$$

I aim to compute the coefficients $K_{mn}$ in a closed form. I solved many problems with generating functions, but this one I tried for days, and I'm not sure if it is impossible at all, or if I lack an important skill. For comparison I give the first coefficients, which I computed by hand

$$K_1(x) = -2x^2-4x^3-4x^4+8x^6+16x^7+O(x^8) \\ K_2(x) = x+3x^2+9x^3+19x^4+33x^5+59x^6+121x^7+O(x^8)\\ K_3(x) = -4x^2-16x^3-40x^4-64x^5-32x^6+192x^7+O(x^8)\\ K_4(x) = x+5x^2+25x^3+85x^4+225x^5+541x^6+1385x^7+O(x^8)$$

also the dependence of the first coefficients on $m$ for the first orders $n$ is given here for odd $m$

$$K_m(x) = (-m-1)x^2-(m+1)^2x^3-\frac{2}{3}m(m+2)(m+1)x^4-\frac{1}{3}(m+1)^2(m-1)(m+3)x^5-\frac{1}{15}(2m^4+8m^3-13m^2-42m-15)(m+1)x^6-\frac{2}{45}m(m+2)(m^2+2m-33)(m+1)^2x^7+O(x^8)$$

and here for even $m$

$$K_m(x) = x+(m+1)x^2+(m+1)^2x^3+\frac{1}{3}(m+1)(2m^2+4m+3)x^4+\frac{1}{3}(3+m^2+2m)(m+1)^2x^5+\frac{1}{15}(m+1)(2m^4+8m^3+27m^2+38m+15)x^6+\frac{1}{45}(2m^4+8m^3+62m^2+108m+45)(m+1)^2x^7+O(x^8)$$

I decided to not post the underlying combinatorial problem, as the point of my question is really to see, if a generating function approach is possible here.

One idea, which I did not finish, however, would be to use the substitution $$x=i\sin(u)$$ which transforms the generator into

$$K_m(u) = \frac{\sin(u)}{\cos(u)\tan((m+1)u)-i}$$

which looks much simpler. Possibly, one could compute the coefficients $$K_m(u)=\sum_{n\geq0}R_{mn}u^n$$ and then transform the $R_{mn}$ into the $K_{mn}$ somehow, but I'm not sure if any of these two steps is possible, and even simpler than directly computing $K_{mn}$.

Any suggestions are highly appreciated.

Answer 1

I would prefer $x=\sinh(u)$ (I had problems with $x=\sin(u)$ since some coefficients appear to be complex in the corresponding expansions).

So, using $x=\sinh(u)$ and working up to the $8^{th}$ as you did, what I obtained is $$K_0=u+u^2+\frac{7 u^3}{6}+\frac{4 u^4}{3}+\frac{181 u^5}{120}+\frac{77 u^6}{45}+\frac{9787 u^7}{5040}+O\left(u^8\right) $$ $$K_1=-2 u^2-4 u^3-\frac{14 u^4}{3}-2 u^5+\frac{236 u^6}{45}+\frac{467 u^7}{30}++O\left(u^8\right)$$ $$K_2=u+3 u^2+\frac{55 u^3}{6}+20 u^4+\frac{4501 u^5}{120}+\frac{359 u^6}{5}+\frac{150671 u^7}{1008}+O\left(u^8\right)$$ $$K_3=-4 u^2-16 u^3-\frac{124 u^4}{3}-72 u^5-\frac{2648 u^6}{45}+\frac{2054 u^7}{15}+O\left(u^8\right)$$ $$K_4=u+5 u^2+\frac{151 u^3}{6}+\frac{260 u^4}{3}+\frac{28501 u^5}{120}+\frac{5381 u^6}{9}+\frac{7939051 u^7}{5040}+O\left(u^8\right)$$ $$K_5=-6 u^2-36 u^3-142 u^4-402 u^5-\frac{3868 u^6}{5}-\frac{4359 u^7}{10}+O\left(u^8\right)$$ $$K_6=u+7 u^2+\frac{295 u^3}{6}+\frac{700 u^4}{3}+\frac{102901 u^5}{120}+\frac{123179 u^6}{45}+\frac{8657183 u^7}{1008}+O\left(u^8\right)$$ $$K_7=-8 u^2-64 u^3-\frac{1016 u^4}{3}-1312 u^5-\frac{168496 u^6}{45}-\frac{32248 u^7}{5}+O\left(u^8\right)$$ $$K_8=u+9 u^2+\frac{487 u^3}{6}+492 u^4+\frac{273781 u^5}{120}+\frac{44637 u^6}{5}+\frac{165177307 u^7}{5040}+O\left(u^8\right)$$ $$K_9=-10 u^2-100 u^3-\frac{1990 u^4}{3}-3250 u^5-\frac{109012 u^6}{9}-\frac{63435 u^7}{2}+O\left(u^8\right)$$ $$K_{10}=u+11 u^2+\frac{727 u^3}{6}+\frac{2684 u^4}{3}+\frac{602581 u^5}{120}+\frac{1052887 u^6}{45}+\frac{499626667 u^7}{5040}+O\left(u^8\right)$$

I suppose that you could run polynomial regression to get the patterns (what was nice in your work was all these integer coefficients).

If you need more, let me know.

Answer 2

In terms of Lucas sequences with the parameters $(P,Q)=(2x,-1)$, we have $$y_+(x)^{m+1} + y_-(x)^{m+1} = V_{m+1},$$ $$\frac{y_+(x)^{m+1} - y_-(x)^{m+1}}{\sqrt{1+x^2}} = 2U_{m+1}.$$ It follows that $$K_m(x) = \frac{x}{1-\frac{V_{m+1}}{2U_{m+1}}} = \frac{xU_{m+1}}{U_{m+1}-\frac12V_{m+1}}.$$

Since the denominator value at $x=0$ is (-1)^m, we have the following expansion: $$K_m(x) = (-1)^m xU_{m+1} \sum_{k=0}^\infty (1+(-1)^{m+1}U_{m+1}+(-1)^m\frac12V_{m+1})^k.$$ Correspondingly, the coefficient of $x^n$ in $K_m(x)$ (i.e. $K_{m,n}$) equals the coefficient of $x^{n-1}$ in $$(-1)^m\sum_{i+j\leq n-1} \binom{i+j}{i} \binom{n}{i+j+1} \frac{(-1)^{(m+1)i+mj}}{2^j} U_{m+1}^{i+1} V_{m+1}^j.$$

To get an explicit formula for $K_{m,n}$, we will need the power expansions: $$V_{m+1}^{k} = \frac12 \sum_{t=0}^{k} \binom{k}t (-1)^{(m+1)t} V_{(m+1)(k-2t)}$$ and $$U_{m+1}^{k} = \frac1{2(4+4x^2)^{\lfloor k/2\rfloor}} \sum_{t=0}^{k} \binom{k}t (-1)^{mt} \begin{cases} V_{(m+1)(k-2t)} & \text{if $k$ is even},\\ U_{(m+1)(k-2t)} & \text{if $k$ is odd}, \end{cases} $$ and the product formulae: $V_kV_\ell = V_{k+\ell} + (-1)^\ell V_{k-\ell}$ and $V_kU_\ell = U_{k+\ell} + (-1)^\ell U_{k-\ell}$.

---

Putting all together and letting $u_{k,n}$ and $v_{k,n}$ denote the coefficient of $x^n$ in $U_k$ and $V_k$ respectively, we obtain the following explicit formula: $$K_{m,n} = (-1)^m\sum_{i+j\leq n-1} \binom{i+j}{i} \binom{n}{i+j+1} \frac{(-1)^{(m+1)i+mj}}{2^{j+2}} \sum_{t=0}^j \binom{j}t (-1)^{(m+1)t}$$ $$\times\frac{1}{4^{\lfloor (i+1)/2\rfloor}} \sum_{\ell=0}^{\lfloor (n-1)/2\rfloor}\binom{-\lfloor (i+1)/2\rfloor}{\ell} \sum_{z=0}^{i+1}\binom{i+1}z (-1)^{mz}$$ $$\times\begin{cases} v_{(m+1)(i+j+1-2t-2z,n-1-2\ell} + (-1)^{(m+1)j} v_{(m+1)(i+1-j+2t-2z),n-1-2\ell} & \text{if $i$ is odd},\\ u_{(m+1)(i+j+1-2t-2z,n-1-2\ell} + (-1)^{(m+1)j} u_{(m+1)(i+1-j+2t-2z),n-1-2\ell} & \text{if $i$ is even}. \end{cases} $$

---

P.S. It is worth to notice that our Lucas sequences can be also expressed in terms of Chebyshev polynomials as $U_k = (-I)^{k-1} {\mathcal U}_{k-1}(Ix)$ and $V_k = 2(-I)^k {\mathcal T}_k(Ix)$, where $I$ is the imaginary unit, which give handy formulas for $u_{k,n}$ and $v_{k,n}$.

---

Here is a Sage code that implements the above explicit formula for $K_{m,n}$.