4
$\begingroup$

Is there any way of estimating a sum like $$\sum_{d\mid n}{d+a\choose b},$$ for positive integers $a$ and $b$? For example, in the OEIS we find that

$$\begin{align*} \sum_{d\mid n}{d+1\choose 2} &=\frac{1}{2}(\sigma_1(n)+\sigma_2(n)),\\ \sum_{d\mid n}{d+2\choose 3} &=\frac{1}{6}(2\sigma_1(n)+3\sigma_2(n)+\sigma_3(n)),\\ \sum_{d\mid n}{d+3\choose 4} &=\frac{1}{24}(6\sigma_1(n)+11\sigma_2(n)+6\sigma_3(n)+\sigma_4(n)). \end{align*}$$

I fail to spot the pattern for $d+4$. Anyway, what I'm looking for is more of a simple asymptotic expression (even though the above examples are kinda cute!).

$\endgroup$
  • 1
    $\begingroup$ The coefficients for $(a, b) = (k, k+1)$ seem to be like those of $x(x+1)(x+2)...(x+k)$ divided by $(k+1)!$. For $(a, b) = (4, 5)$ I might guess your sum equals $(\sigma_5(n) + 10\sigma_4(n) + 35\sigma_3(n) + 50\sigma_2(n) + 24\sigma_1(n))/120$. $\endgroup$ – Unit Apr 21 at 15:27
  • $\begingroup$ Looks like Stirling numbers to me. $\endgroup$ – marty cohen Apr 21 at 20:32
4
$\begingroup$

$\sum_{d\mid n}{d+a\choose b} $

The unsigned Stirling numbers of the first kind, $c(n, k)$ are defined by $\prod_{k=0}^{n-1} (x+k) =\sum_{k=0}^n c(n, k)x^k $. (see https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind)

Therefore

$\begin{array}\\ \rho_{a, b}(n) &=\sum_{d\mid n}{d+a\choose b}\\ &=\sum_{d\mid n}{d+a\choose b}\\ &=\dfrac1{b!}\sum_{d\mid n}\dfrac{(d+a)!}{(d+a-b)!}\\ &=\dfrac1{b!}\sum_{d\mid n}\prod_{k=a-b+1}^a (d+k)\\ &=\dfrac1{b!}\sum_{d\mid n}\prod_{k=0}^{b-1} (d+a-b+1+k)\\ &=\dfrac1{b!}\sum_{d\mid n}\sum_{k=0}^{b}(d+a-b+1)^kc(b, k)\\ &=\dfrac1{b!}\sum_{d\mid n}\sum_{k=0}^{b}c(b, k)\sum_{j=0}^k\binom{k}{j}d^j(a-b+1)^{k-j}\\ &=\dfrac1{b!}\sum_{d\mid n}\sum_{k=0}^{b}c(b, k)\sum_{j=0}^k\binom{k}{j}d^jr^{k-j} \quad r = a-b+1\\ &=\dfrac1{b!}\sum_{k=0}^{b}c(b, k)\sum_{j=0}^k\binom{k}{j}r^{k-j}\sum_{d\mid n}d^j\\ &=\dfrac1{b!}\sum_{k=0}^{b}c(b, k)\sum_{j=0}^k\binom{k}{j}r^{k-j}\sigma_j(n)\\ &=\dfrac1{b!}\sum_{j=0}^n\sigma_j(n)\sum_{k=j}^{b}c(b, k)\binom{k}{j}r^{k-j}\\ &=\dfrac1{b!}\sum_{j=0}^n\sigma_j(n)\sum_{k=0}^{b-j}c(b, k+j)\binom{k+j}{j}r^{k}\\ &=\dfrac1{b!}\sum_{j=0}^n\sigma_j(n)u(a, b, j)\quad\text{where } u(a, b, j)=\sum_{k=0}^{b-j}c(b, k+j)\binom{k+j}{j}r^{k}\\ \end{array} $

If $b=a+1$, as in the examples, $r=0$ so $u(a, a+1, j) =\sum_{k=0}^{b-j}c(a+1, k+j)\binom{k+j}{j}r^{k} =c(a+1, j)\binom{j}{j} =c(a+1, j) $ so that $\rho(a, a+1, n) =\dfrac1{(a+1)!}\sum_{j=0}^n\sigma_j(n)u(a, a+1, j) =\dfrac1{(a+1)!}\sum_{j=0}^n\sigma_j(n)c(a+1, j) $.

$\endgroup$
1
$\begingroup$

This is a complement to @marty cohen answer. We can also give an identity for the case $a=-1$.

With the notation ${n\brack k}=c(n,k)$, we have $$ \sum_{d\mid n}{d-1\choose b} = \frac{1}{b!}\sum_{j=0}^b{b+1\brack j+1}(-1)^{b-j}\sigma_j(n). $$

$\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.