# Estimating $\sum\limits_{d\mid n}{d+a\choose b}$

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!).

• 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$. – Unit Apr 21 at 15:27
• Looks like Stirling numbers to me. – marty cohen Apr 21 at 20:32

## 2 Answers

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

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