3
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ $B(k,j)=(k-1)(B(k-1,j)+B(k-1,j-1))$ $\endgroup$ – user514787 Jan 16 at 15:37
  • $\begingroup$ $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. $\endgroup$ – user514787 Jan 17 at 2:14
  • $\begingroup$ $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$ $\endgroup$ – user514787 Jan 17 at 2:17
  • $\begingroup$ 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. $\endgroup$ – user514787 Jan 17 at 8:12
2
$\begingroup$

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.

$\endgroup$

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.