# Complete sequence of sequences

Who can continue (complete) the following sequence:

$$1,n-1,\frac{(n-2)(n-1)}{2},\frac{(n-4)(n-3)(n+1)}{6},\frac{(n-7)(n-4)(n-2)(n+3)}{24},\dots$$

This was emerging in the course of this question as crucial coefficients in the transformation of Fibonacci polynomials.

I am pretty sure I have seen this before in another context, but I cannot remember it exactly, I have the vague memory that it contains some more complicated structure than factorials, maybe something like rising factorials/Pochhammer-symbols.

Edit

The next sequence of this row is numerically $$a_6 = \{-4,12,-21,-24,-9,42,154,360,702,1232\dots\}$$

This is no 5$^{th}$ degree polynomial anymore and I am unable to detect the law.. If fact it is one, this can be seen from the fifth difference sequence which gets constant (when calculated correctly).

By interpolation and factorisation I finally got the law (see below).

Edit-2

Meanwhile I found an alternative way to generate these series, but however still got stuck at the 6$^{th}$ one.

They can be expressed as the coefficients of the series expansion of polynomial fractions $f_i(x)$ at $x=0$, the functions are in detail:

\begin{array}{c|c|c|c|c|c|c} i& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline a_i&1 & n-1 & \frac{(n-2)(n-1)}{2}& \frac{(n-4)(n-3)(n+1)}{6}&\frac{(n-7)(n-4)(n-2)(n+3)}{24}&v.i.&v.i.\\ \hline f_i(x)&\frac{1}{x-1}& \frac{1}{(x-1)^2}&\frac{1}{(x-1)^3}&\frac{(x-2)x}{(x-1)^4}&\frac{(x-2)(1+x(x-3))}{(x-1)^5}&?&\\ \end{array}

Edit-3

So, the expression for the next sequences are:

$$a_6 = \frac{(n-5)(n-4)(n-1)(n^2-5n-54)}{120}$$

$$a_7 = \frac{(n-6)(n-3)(n^4-12n^3-71n^2+642n+160)}{720}$$

I am still unable to guess a general law for $f_i(x)$ or $a_i$.

Edit-4

I will try to get some recursion relation now from the consideration of the difference series.

## 1 Answer

As you reference in another question, $$F_n(x) = \sum_{k=0}^n \binom{\frac{n+k-1}{2}}{k} x^k$$

If we consider $F_n(x+1)$ directly we get $$\begin{eqnarray} F_n(x+1) & = & \sum_{k=0}^n \binom{\frac{n+k-1}{2}}{k} (x+1)^k \\ & = & \sum_{k=0}^n \binom{\frac{n+k-1}{2}}{k} \sum_{i=0}^k \binom{k}{i} x^i \\ & = & \sum_{i=0}^n x^i \sum_{k=i}^n \binom{\frac{n+k-1}{2}}{k} \binom{k}{i} \\ \end{eqnarray}$$

If we consider $F_n(x+1)$ as a sum of weighted $F_m(x)$ we get $$\begin{eqnarray} F_n(x+1) & = & \sum_{m=0}^n \lambda_m \sum_{k=0}^m \binom{\frac{m+k-1}{2}}{k} x^k \\ & = & \sum_{k=0}^n x^k \sum_{m=k}^n \binom{\frac{m+k-1}{2}}{k} \lambda_m \\ \end{eqnarray}$$

By equating coefficients in $x^i$ we get

$$\sum_{m=i}^n \binom{\frac{m+i-1}{2}}{i} \lambda_m = \sum_{k=i}^n \binom{\frac{n+k-1}{2}}{k} \binom{k}{i}$$

On the left-hand side, discard the term $m=i$ (since $2i-1$ is odd) and extract the term $m=i+1$ from the sum, and the sum can be passed to the right:

$$\lambda_{i+1} = \left(\sum_{k=i}^n \binom{\frac{n+k-1}{2}}{k} \binom{k}{i}\right) - \sum_{m=i+2}^n \binom{\frac{m+i-1}{2}}{i} \lambda_m$$

And voilà: one recurrence.

NB your $a_j$ is $\lambda_{n-j+1}$, so

$$a_j = \left(\sum_{k=n-j}^n \binom{\frac{n+k-1}{2}}{k} \binom{k}{n-j}\right) - \sum_{m=n-j+2}^n \binom{\frac{n+m-j-1}{2}}{n-j} a_{n-m+1}$$

and it makes sense to reindex at least the second sum as

$$a_j = \left(\sum_{k=n-j}^n \binom{\frac{n+k-1}{2}}{k} \binom{k}{n-j}\right) - \sum_{m=1}^{j-1} \binom{n-\frac{m+j}{2}}{n-j} a_{m}$$

• Using your expression directly after the line "by equating coefficients in $x^i$", I receive for $k=n$ that $\lambda_n=1$, which is fine. But for $k=n-1$, I get $\lambda_{n-1}=2n-1$ but correct would be $\lambda_{n-1}=n-1$. I suspect somewhere must be an error. – Rudi_Birnbaum Apr 12 '18 at 7:28
• @R_Berger, assuming that you mean for $i=n$, you should get empty sums on both sides. For $i=n-1$ it gives $\binom{n-1}{n-1} \lambda_{n} = \binom{n-1}{n-1} \binom{n-1}{n-1}$ ; for $i=n-2$ it gives $\binom{n-2}{n-2} \lambda_{n-1} = \binom{n-1}{n-1} \binom{n-1}{n-2}$. I suspect that you're not taking into account that $\binom{a+\tfrac12}{b} = 0$ for $a,b\in\mathbb{N}$. – Peter Taylor Apr 12 '18 at 7:53
• I always thought ${1/2 \choose 1}=\frac{(1/2)!}{(-1/2)!1!}=\frac{\sqrt{\pi}/2}{\sqrt{\pi}1}=1/2$, no? – Rudi_Birnbaum Apr 12 '18 at 8:10
• @R_Berger, if you want to work with the analytic continuation of the binomial function rather than the one which is defined only for integer arguments, it's a case of reworking the algebra starting from $F_n(x)=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k-1}{k}x^{n-2k-1}$ – Peter Taylor Apr 12 '18 at 8:17
• I am indeed saying that. – Peter Taylor Apr 12 '18 at 8:39