# Sum involving binomial coefficients and falling factorials

I am trying to find a simplified form for this summation:

$$B(k,j) \equiv \sum_{i=1}^k (-1)^{k+i} {i \choose j} (k-1)_{i-1} \quad \quad \quad \text{for } 1 \leqslant j \leqslant k,$$

where the terms $$(k-1)_{i-1} = (k-1) \cdots (k-i+1)$$ are falling factorials (and $$(k-1)_0 = 1$$ by convention). I have done some work on this by generating a matrix of values of this quantity (see below) and I can recognise simplified forms for some of the parts of the matrix, but I have been unable to see a simplified form for the whole thing.

Computing the terms and looking for a pattern: In case it helps to try to recognise a pattern, I have computed a matrix of terms using the R code below. From the matrix of values it is clear that $$B(k,k) = (k-1)!$$ and $$B(k,k-1) = (k-1) (k-1)!$$. I also recognise that $$B(k,1)$$ is A000255. I do not recognise the overall matrix of numbers as any simple form.

#Generate function
B <- function(k,j) { T1 <- (-1)^(k+1:k);
T2 <- choose(1:k, j);
TT <- c(1,(k-1):1);
T3 <- cumprod(TT);

sum(T1*T2*T3); }

#Create matrix of terms
M <- 10;
BBB <- matrix(0, nrow = M, ncol = M);
for (k in 1:M) {
for (j in 1:k) { BBB[k,j] <- B(k,j); }}

BBB;  #k is the row, j is the column

[,1]    [,2]     [,3]     [,4]     [,5]     [,6]     [,7]     [,8]    [,9]  [,10]
[1,]       1       0        0        0        0        0        0        0       0      0
[2,]       1       1        0        0        0        0        0        0       0      0
[3,]       3       4        2        0        0        0        0        0       0      0
[4,]      11      21       18        6        0        0        0        0       0      0
[5,]      53     128      156       96       24        0        0        0       0      0
[6,]     309     905     1420     1260      600      120        0        0       0      0
[7,]    2119    7284    13950    16080    11160     4320      720        0       0      0
[8,]   16687   65821   148638   210210   190680   108360    35280     5040       0      0
[9,]  148329  660064  1715672  2870784  3207120  2392320  1149120   322560   40320      0
[10,] 1468457 7275537 21381624 41278104 54701136 50394960 31872960 13245120 3265920 362880

• $B(k,j)=(k-1)(B(k-1,j)+B(k-1,j-1))$ – user514787 Jan 16 at 15:37
• $B(k,k-n)=(k-1)!P_{n}(k)/n!, [k^0]P_{n}(k)=(-1)^na(n), \sum\limits_{m=0}^{n}(-1)^{n-m}[k^m]P_{n}(k)=b(n)$ where $a(n)$ A000262, $b(n)$ A002720. – user514787 Jan 17 at 2:14
• $B(k,1)=\lfloor{(k+1)(k-1)!+1\over e}\rfloor, B(k,2)=\lfloor{(k^2+k-1)(k-1)!+1\over 2e}\rfloor$ – user514787 Jan 17 at 2:17
• Also $B(k,3)=\lfloor{(k^3-4k+1)(k-1)!+1\over 3!e}\rfloor, B(k,4)=\lfloor{(k^4-2k^3-7k^2+12k+1)(k-1)!+2\over 4!e}\rfloor$ and so on, but it looks like this polynomial is more tricky. – user514787 Jan 17 at 8:12

## 1 Answer

Some Asymptotic Approximations

The AM-GM inequality says $$\frac{k!}{(k-i)!}\le\left(k-\frac{i-1}{2}\right)^i\tag1$$ The fact that $$\frac{k(k-i+1)}{\left(k-\frac{i-1}2\right)^2}=1-\left(\frac{\frac{i-1}2}{k-\frac{i-1}2}\right)^2\tag2$$ allows us to derive $$\frac{k!}{(k-i)!}\ge\left[1-\frac{\frac13\left(\frac{i+1}2\right)^3}{\left(k-\frac{i-1}2\right)^2}\right]\left(k-\frac{i-1}{2}\right)^i\tag3$$ and therefore, $$\frac{k!}{(k-i)!}\sim\left(k-\frac{i-1}{2}\right)^i\tag4$$ from which, we get \begin{align} \frac{\binom{k-j}{i}}{\binom{k}{i}} &\sim\left(\frac{k-j-\frac{i-1}2}{k-\frac{i-1}2}\right)^i\\ &\sim\left(\frac{k-j}{k}\right)^i\left(1-\frac{i(i-1)j}{2k(k-j)}\right)\\[6pt] &=\left(\frac{k-j}{k}\right)^i-i(i-1)\left(\frac{k-j}{k}\right)^{i-2}\frac{j(k-j)}{2k^3}\tag5 \end{align} and therefore, \begin{align} \sum_{i=0}^\infty\frac{(-1)^i}{i!}\frac{\binom{k-j}{i}}{\binom{k}{i}} &\sim\sum_{i=0}^\infty\frac{(-1)^i}{i!}\left[\left(\frac{k-j}{k}\right)^i-i(i-1)\left(\frac{k-j}{k}\right)^{i-2}\frac{j(k-j)}{2k^3}\right]\\ &=e^{-\frac{k-j}k}\left(1-\frac{j(k-j)}{2k^3}\right)\\[3pt] &\sim e^{-\frac{k-j}k-\frac{j(k-j)}{2k^3}}\tag6 \end{align}

Approximation of the Sum

We don't get an exact closed form, but here is a pretty good asymptotic approximation: \begin{align} \sum_{i=1}^k(-1)^{k+i}\binom{i}{j}(k-1)_{i-1} &=\frac1k\sum_{i=1}^k(-1)^{k-i}\binom{i}{j}(k)_i\\ &=\frac1k\sum_{i=0}^{k-1}(-1)^i\binom{k-i}{j}(k)_{k-i}\\ &=(k-1)!\binom{k}{j}\sum_{i=0}^{k-1}\frac{(-1)^i}{i!}\frac{\binom{k-j}{i}}{\binom{k}{i}}\\ &\sim\bbox[5px,border:2px solid #C0A000]{(k-1)!\binom{k}{j}e^{-\frac{k-j}k-\frac{j(k-j)}{2k^3}}}\tag7 \end{align} This is good when $$k$$ is large, exact when $$j=k$$, and extremely close when $$j=0$$. In fact, it looks as if the ratio of the approximation to the actual sum is asymptotically $$1+\frac{(4j+k)j(k-j)}{6k^5}$$. The maximum of this ratio is when $$\frac jk=\frac{3+\sqrt{21}}{12}\approx0.63188$$, where $$\frac{(4j+k)j(k-j)}{6k^5}=\frac{27+7\sqrt{21}}{432k^2}\approx\frac{0.13675}{k^2}$$ .

For example, when $$k=10$$ and $$j=5$$, $$(7)$$ gives $$54775664.104$$, which is about $$0.136\%$$ above the value in the table in the question.