Sum involving binomial coefficients and falling factorials

Question

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

Answer 1

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.

Answer 2

\begin{equation} \sum_{i=1}^k (-1)^{k+i}\binom{i}{j}(k-1)_{i-1} = \frac{\Gamma(k)}{\Gamma(1+j)}(-1)^k \sum_{i=1}^k (-1)^{i}\frac{\Gamma(i+1)}{\Gamma(i-j+1)\Gamma(k-i+1)} \end{equation} substitute $i'=k-i$ and use $(.)_n$ for the risign factorial (Pochhammer's symbol) \begin{equation} = \frac{\Gamma(k)}{\Gamma(1+j)}(-1)^k \sum_{i'=k-1}^0 (-1)^{k-i'}\frac{\Gamma(k-i'+1)}{\Gamma(k-i'-j+1)\Gamma(i'+1)} \end{equation} \begin{equation} = \frac{\Gamma(k)}{\Gamma(1+j)} \sum_{i=0}^{k-1} \frac{\Gamma(k+1)(j-k)_i}{(-k)_i\Gamma(k-j+1)\Gamma(i+1)}(-1)^i \end{equation} \begin{equation} = \frac{\Gamma(k)\Gamma(k+1)}{\Gamma(1+j)\Gamma(k-j+1)} % \sum_{i=0}^{k-1} % \frac{(j-k)_i}{(-k)_i\Gamma(i+1)}(-1)^i {}_1F_1(j-k;-k;-1) \end{equation} \begin{equation} = \Gamma(k) \binom{k}{j} {}_1F_1(j-k;-k;-1) \end{equation} \begin{equation} = \Gamma(k) \binom{k}{j} \sum_{i=0}^{k-j} \frac{(j-k)_i}{(-k)_i}\frac{(-1)^i}{i!} \end{equation} \begin{equation} = \Gamma(k) \binom{k}{j} \sum_{i=0}^{k-j} \frac{(j-k)(j-k+1)\cdots (j-k+i-1)}{(-k)(-k+1)\cdots (-k+i-1)}\frac{(-1)^i}{i!} \end{equation} \begin{equation} = \Gamma(k) \binom{k}{j} \sum_{i=0}^{k-j} \frac{(k-j)(k-j-1)\cdots (k-j-i+1)}{(k)(k-1)\cdots (k-i+1)}\frac{(-1)^i}{i!} \end{equation} \begin{equation} = \Gamma(k) \frac{k!}{(k-j)!j!} \sum_{i=0}^{k-j} \frac{(k-j)!(k-i)!}{(k-j-i)!k!}\frac{(-1)^i}{i!} \end{equation} \begin{equation} = \Gamma(k) \frac{1}{j!} \sum_{i=0}^{k-j} \frac{(k-i)!}{(k-j-i)!}\frac{(-1)^i}{i!} \end{equation} \begin{equation} =(k-1)! \sum_{i=0}^{k-j} \binom{k-i}{j}\frac{(-1)^i}{i!} \end{equation}