Derivative of the binomial $\binom x n$ with respect to $x$

Question

My background is not mathematics and I need to implement (in C++) the derivative of a binomial, with wxMaxima and wolfram.alpha as a helper. So far, the binomial can be written as: $$\binom x n = \frac 1 {n!}\prod_{k=1}^n (x-k+1)$$ This reduces to a continued convolution. For my specific needs, the binomial needs to be of the form: $$\binom{\frac{n+1}{2}x+\frac{n-1}{2}}{n}$$ But I also need the derivative of it, which wxMaxima solves as $$-\frac{1}{2}(n+1) \,\left( \psi_0\left( \frac{(n+1) x-n+1} 2 \right) -\psi_0 \left( \frac{(n+1) \,(x+1) }{2}\right) \right) \,\begin{pmatrix}\frac{( n+1) x+n-1}{2}\\ n \end{pmatrix}$$

while wolfram goes a bit further and, instead of $\psi_0$ gives $H_n$, which they call harmonic number. (this link). That $\psi$ seems to have quite an involved formula, but $H_n$,as functions.wolfram has it, is a simple $\sum_{k=1}^n 1/k$, which is a lot simpler in terms of C++.

Now, because I have trust issues, I went on to verify the answer given by wolfram, in wxMaxima, for $n=4$. Here's the code:

n:4$
g:diff(binomial((n+1)/2*(x+1)-1,n),x),expand,numer$
h:-(n+1)/2*binomial((n+1)/2*(x+1)-1,n)*(sum(1/k,k,1,(n+1)/2*(x-1))-sum(1/k,k,1,1/2*(n*(x+1)+x-1)));
wxplot2d([g,h],[x,0,1]);

and here's the output of it:

plot

As you can see, they don't match; plotting wxMaxima's derivation is a match, but that involves $\psi$ as an infinite sum. So I'm left wondering what's wrong: is the implementation of the harmonic number? Is the derivation formula? Is it the way I transcribed it?

TL;DR: I need a derivation formula (not the actual code, that's up to me) for the binomial that is (fairly) simple to implement and doesn't take ages to compute, in C++, as the whole function will be called in a bracketed root-finding algorithm. And I'm also using GMP from gmplib dot org (need 10 rep to post more than 2 links).

---

Following G Cab's excellent post, and modifying the formulas according to my needs, I managed to come up (with a bit of hammering) to this formula:

$$\frac{d}{dx}\binom{\frac{n+1}{2}x+\frac{n-1}{2}}{n}=(-1)^n \frac{n+1}{2} \binom{\frac{n+1}{2}x + \frac{n-1}{2}}{n} \sum_{k=0}^{n-1} \frac{1}{\frac{n+1}{2}x +\frac{n-1}{2}-k}$$

The $(-1)^n$ takes care of odd $n$. Thank you very much everyone that answered.

Answer 1

For the purpose of computing the derivatives, you can also profitably make use of the expression of the binomials via the Stirling Numbers of 1st kind $$ \binom y n = \frac{y^{\,\underline {\,n\,} }}{n!} = \frac{1}{n!} \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} (-1)^{n - k} \left[ \begin{gathered} n \\ k \end{gathered} \right]y^k $$ Now, to explain about the alternative formulas with $\psi$ and $H$, consider the binomial expressed in terms of the Gamma function $$ \binom y n = \frac{\Gamma (y + 1)}{\Gamma (n + 1)\Gamma (y - n + 1)} = \frac 1 {n!} \frac{\Gamma (y + 1)} {\Gamma (y - n + 1)} $$ then $$ \begin{gathered} \frac d {dy} \binom y n = - \frac 1 {n!} \frac{\Gamma '(y + 1)\Gamma (y - n + 1) - \Gamma (y + 1)\Gamma '(y - n + 1)} {\Gamma (y - n + 1)^2} = \hfill \\ = \frac 1 {n!} \left( {\frac{\Gamma (y + 1)}{{\Gamma (y - n + 1)}} \frac{{\Gamma '(y - n + 1)}} {\Gamma (y - n + 1)} - \frac{{\Gamma (y + 1)}} {\Gamma (y - n + 1)}\frac{\Gamma '(y + 1)} {\Gamma (y + 1)}} \right) = \hfill \\ = \binom y n (\psi _0 (y - n + 1) - \psi _0 (y + 1)) \hfill \\ \end{gathered} $$

Consider instead the binomial expressed in terms of the product,

$$ \binom y n = \frac{y^{\,\underline {\,n\,} }}{n!} = \frac 1 {n!} \prod\limits_{j = 0}^{n - 1} (y - j) $$ then for the derivative you have $$ \begin{gathered} \frac d {dy} \binom y n = \frac 1 {n!} \sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\prod\limits_{\begin{array}{*{20}c} {j \ne k} \\ {j = 0} \\ \end{array} }^{n - 1} {(y - j)} } = \frac 1 {n!} \sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\frac{1}{y - k} \prod\limits_{j = 0}^{n - 1} {\left( {y - j} \right)} = } \hfill \\ = \binom y n \sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\frac{1} {{y - k}}} = \binom y n \sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} \frac 1 {y - n + k} \hfill \\ \end{gathered} $$ and for computational purposes, this formula is already quite viable, and I think you do not need to consider the further expansion leading to: $$ \frac d {dy} \binom y n = \binom y n \sum\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} \frac 1 {y - n + k} = \binom y n \sum_{y - n + 1\, \leqslant \,k\, \leqslant \,y} \frac 1 k = \binom y n (H_y - H_{y - n}) $$

Answer 2

We can start with the product representation \begin{align*} \binom{\frac{n+1}{2}x+\frac{n-1}{2}}{n}&=\frac{1}{n!}\prod_{k=1}^n\left(\frac{n+1}{2}x+\frac{n-1}{2}-k+1\right)\\ &=\frac{1}{2^nn!}\prod_{k=1}^n\left((n+1)x+n+1-2k\right) \end{align*} and recall that \begin{align*}\frac{d}{dx}\prod_{k=1}^nf_k(x) =\sum_{j=1}^nf_j^\prime(x)\prod_{{k=1}\atop{k\neq j}}^nf_k(x) \end{align*}

We obtain \begin{align*} \frac{d}{dx}\binom{\frac{n+1}{2}x+\frac{n-1}{2}}{n} &=\frac{d}{dx}\left(\frac{1}{2^nn!}\prod_{k=1}^n\left((n+1)x+n+1-2k\right)\right)\\ &=\frac{1}{2^nn!}\sum_{j=1}^n \left(\frac{d}{dx}\left((n+1)x+n+1-2j\right)\right) \prod_{{k=1}\atop{k\neq j}}^n\left((n+1)x+n+1-2k\right)\\ &=\frac{n+1}{2^nn!}\sum_{j=1}^n\prod_{{k=1}\atop{k\neq j}}^n \left((n+1)x+n+1-2k\right) \end{align*}

Answer 3

As we know, the series of the binomial coefficients is the binomial series, $$ F(x,z)=\sum_{n=0}^\infty\binom xn z^n=(1+z)^x $$ This has the $x$ derivative $$ \frac{\partial}{\partial x}F(x,z) =\ln(1+z)\,(1+z)^x =\sum_{k=1}^\infty\frac{(-1)^{k-1}}{k}z^k\sum_{m=0}^\infty\binom xm z^m =\sum_{n=1}^\infty\sum_{k=1}^n\frac{(-1)^{k-1}}{k}\binom x{n-k} z^n $$ so that $$ \frac{d}{dx}\binom xn = \sum_{k=1}^n\frac{(-1)^{k-1}}{k}\binom x{n-k}. $$

Answer 4

Here is a different way to prove the same result as @LutzL:

Theorem 1. Let $n\in\mathbb{N}$. Then, the derivative of the polynomial $\dbinom{x}{n}\in\mathbb{Q}\left[ x\right] $ is \begin{equation} \dfrac{d}{dx}\dbinom{x}{n}=\sum_{k=1}^{n}\dfrac{\left( -1\right) ^{k-1}} {k}\dbinom{x}{n-k}. \end{equation}

My proof relies on three identities for binomial coefficients. The first is the famous Chu-Vandermonde identity:

Theorem 2. Let $n\in\mathbb{N}$. Then, in the polynomial ring $\mathbb{Q}\left[ x,y\right] $ (in two indeterminates $x$ and $y$), we have \begin{equation} \dbinom{x+y}{n}=\sum_{k=0}^{n}\dbinom{x}{k}\dbinom{y}{n-k}. \end{equation}

For a direct proof of Theorem 2, see Theorem 3.30 in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, 10 January 2019 (where I denote the indeterminates $x$ and $y$ by $X$ and $Y$ to visually keep them apart from two numbers $x$ and $y$). That said, if you know any proof of the classical Vandermonde convolution identity \begin{equation} \dbinom{a+b}{n}=\sum_{k=0}^{n}\dbinom{a}{k}\dbinom{b}{n-k}\qquad\text{for }a\in\mathbb{N}\text{ and }b\in\mathbb{N} \end{equation} (see also the Cut-the-Knot page), then you can easily leverage it to obtain a proof of Theorem 2 by applying the standard polynomial identity trick (if two univariate polynomials agree on $\mathbb{N}$, then they are identical) twice (since there are two indeterminates).

The next identity I need is a simple one (one of the forms of the absorption identity):

Proposition 3. Let $k$ be a positive integer. Then, in the polynomial ring $\mathbb{Q}\left[ y\right] $ (in one indeterminate $y$), we have \begin{equation} \dbinom{y}{k}=\dfrac{y}{k}\dbinom{y-1}{k-1}. \end{equation}

Proof of Proposition 3. The definition of $\dbinom{y-1}{k-1}$ yields \begin{align*} \dbinom{y-1}{k-1} & =\dfrac{\left( y-1\right) \left( y-2\right) \cdots\left( \left( y-1\right) -\left( k-1\right) +1\right) }{\left( k-1\right) !}\\ & =\dfrac{\left( y-1\right) \left( y-2\right) \cdots\left( y-k+1\right) }{\left( k-1\right) !}. \end{align*} Multiplying this equality by $\dfrac{y}{k}$, we find \begin{align*} \dfrac{y}{k}\dbinom{y-1}{k-1} & =\dfrac{y}{k}\cdot\dfrac{\left( y-1\right) \left( y-2\right) \cdots\left( y-k+1\right) }{\left( k-1\right) !}=\dfrac{y\cdot\left( y-1\right) \left( y-2\right) \cdots\left( y-k+1\right) }{k\cdot\left( k-1\right) !}\\ & =\dfrac{y\left( y-1\right) \cdots\left( y-k+1\right) }{k!} \end{align*} (since $y\cdot\left( y-1\right) \left( y-2\right) \cdots\left( y-k+1\right) =y\left( y-1\right) \cdots\left( y-k+1\right) $ and $k\cdot\left( k-1\right) !=k!$). Comparing this with \begin{equation} \dbinom{y}{k}=\dfrac{y\left( y-1\right) \cdots\left( y-k+1\right) } {k!}\qquad\left( \text{by the definition of }\dbinom{y}{k}\right) , \end{equation} we obtain $\dbinom{y}{k}=\dfrac{y}{k}\dbinom{y-1}{k-1}$. This proves Proposition 3. $\blacksquare$

The final identity I need is so simple even I am leaving it as an exercise:

Proposition 4. Let $m\in\mathbb{N}$. Then, $\dbinom{-1}{m}=\left( -1\right) ^{m}$.

(Just in case: Proposition 4 is Corollary 3.17 in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, 10 January 2019.)

Now, we define a weird notation:

Definition. Let $R\in\mathbb{Q}\left[ x,y\right] $ be a polynomial in two indeterminates $x$ and $y$. Let $a\in\mathbb{Q}$. Then, $\operatorname*{ev}\limits_{y\to a}R$ shall denote the result of substituting $a$ for $y$ in $R$. This is a polynomial in $\mathbb{Q}\left[ x\right] $.

For example, $\operatorname*{ev}\limits_{y\to 3}\left( x+y\right) ^{2}=\left( x+3\right) ^{2}$.

For the algebraists in the room: If we fix $a\in\mathbb{Q}$, then the map $\operatorname*{ev}\limits_{y\to a}$ (sending each $R\in \mathbb{Q}\left[ x,y\right] $ to $\operatorname*{ev}\limits_{y\to a}R\in\mathbb{Q}\left[ x\right] $) is a $\mathbb{Q}\left[ x\right] $-algebra homomorphism, called an evaluation homomorphism. This is why I am using "ev" as its name. The symbol "$\operatorname*{ev}\limits_{y\to a}$" should you remind you of "$\lim\limits_{y\to a}$" from calculus, and that similarity is substantial: For example, \begin{equation} \operatorname*{ev}\limits_{y\to 1}\underbrace{\dfrac{y^{3}-1}{y-1} }_{=y^{2}+y+1}=\operatorname*{ev}\limits_{y\to 1}\left( y^{2} +y+1\right) =1^{2}+1+1=3, \end{equation} although you cannot simply substitute $1$ into the expression $\dfrac{y^{3}-1}{y-1}$. So, when $R$ is a fraction of two polynomials that happens to itself be a polynomial, then $\operatorname*{ev}\limits_{y\to a}R$ really is something like "the limit of $R$ as $y$ approaches $a$", because in order to compute $\operatorname*{ev}\limits_{y\to a}R$, we must first rewrite the fraction as an actual polynomial and only then substitute $a$ for $y$.

Finally, we shall need the following formula for the derivative of a polynomial, which is the algebraic counterpart to the classical analytical definition of the derivative:

Theorem 5. Let $P\in\mathbb{Q}\left[ x\right] $ be a polynomial. Consider the polynomial $P\left( x+y\right) \in\mathbb{Q}\left[ x,y\right] $ in two indeterminates $x$ and $y$. Then, the polynomial $P\left( x+y\right) -P\left( x\right) \in\mathbb{Q}\left[ x,y\right] $ is divisible by $y$, and we have \begin{equation} \dfrac{d}{dx}P=\operatorname*{ev}\limits_{y\to 0}\dfrac{P\left( x+y\right) -P\left( x\right) }{y}. \end{equation}

Proof of Theorem 5. Write the polynomial $P$ in the form $P = \sum\limits_{i=0}^{n}a_{i}x^{i}$ for some $n\in\mathbb{N}$ and $a_{0},a_{1},\ldots,a_{n} \in\mathbb{Q}$. We WLOG assume that $n\geq 1$ (since otherwise, we can increase $n$ by adding zero coefficients to $P$).

From $P = \sum\limits_{i=0}^{n}a_{i}x^{i}$, we obtain \begin{equation} \dfrac{d}{dx}P=\sum_{i=1}^{n}a_{i}ix^{i-1} \label{darij.pf.t4.der} \tag{1} \end{equation} (by the definition of $\dfrac{d}{dx}P$). On the other hand, from $P = \sum\limits_{i=0}^{n}a_{i}x^{i}$, we obtain \begin{align*} P\left( x+y\right) & =\sum_{i=0}^{n}a_{i}\underbrace{\left( x+y\right) ^{i}}_{\substack{=\left( y+x\right) ^{i}\\= \sum\limits_{j=0}^{i}\dbinom{i}{j} y^{j}x^{i-j}\\\text{(by the binomial formula)}}} =\sum_{i=0}^{n}a_{i} \underbrace{\sum\limits_{j=0}^{i}\dbinom{i}{j}y^{j}x^{i-j} }_{\substack{=\dbinom{i}{0}y^{0}x^{i-0} +\sum\limits_{j=1}^{i}\dbinom{i}{j}y^{j}x^{i-j}\\\text{(here, we have split off the}\\\text{addend for }j=0\text{ from the sum)}}}\\ & =\sum_{i=0}^{n}a_{i}\left( \underbrace{\dbinom{i}{0}}_{=1} \underbrace{y^{0}}_{=1}\underbrace{x^{i-0}}_{=x^{i}}+\sum_{j=1}^{i}\dbinom {i}{j}y^{j}x^{i-j}\right) \\ & =\sum_{i=0}^{n}a_{i}\left( x^{i}+\sum_{j=1}^{i}\dbinom{i}{j}y^{j} x^{i-j}\right) =\underbrace{\sum_{i=0}^{n}a_{i}x^{i}}_{=P=P\left( x\right) }+\sum_{i=0}^{n}a_{i}\sum_{j=1}^{i}\dbinom{i}{j}y^{j}x^{i-j}\\ & =P\left( x\right) +\sum_{i=0}^{n}a_{i}\sum_{j=1}^{i}\dbinom{i}{j} y^{j}x^{i-j}. \end{align*} Subtracting $P\left( x\right) $ from this equality, we find \begin{align} & P\left( x+y\right) -P\left( x\right) \nonumber\\ & =\sum_{i=0}^{n}a_{i}\sum_{j=1}^{i}\dbinom{i}{j}y^{j}x^{i-j} =\underbrace{\sum\limits_{i=0}^{n}\sum\limits_{j=1}^{i} }_{=\sum\limits_{j=1}^{n}\sum\limits_{i=j}^{n} }a_{i}\dbinom{i}{j}y^{j}x^{i-j}=\sum_{j=1}^{n}\sum_{i=j}^{n}a_{i}\dbinom{i} {j}y^{j}x^{i-j}\nonumber\\ & =\sum_{j=1}^{n}\underbrace{y^{j}}_{\substack{=yy^{j-1}\\\text{(since } j\geq1\text{)}}}\sum_{i=j}^{n}a_{i}\dbinom{i}{j}x^{i-j}=\sum_{j=1}^{n} yy^{j-1}\sum_{i=j}^{n}a_{i}\dbinom{i}{j}x^{i-j}\nonumber\\ & =y\sum_{j=1}^{n}y^{j-1}\sum_{i=j}^{n}a_{i}\dbinom{i}{j}x^{i-j} . \label{darij.pf.t4.1} \tag{2} \end{align} Hence, this polynomial $P\left( x+y\right) -P\left( x\right) $ is divisible by $y$. Moreover, dividing the equality \eqref{darij.pf.t4.1} by $y$, we obtain \begin{equation} \dfrac{P\left( x+y\right) -P\left( x\right) }{y}=\sum_{j=1}^{n}y^{j-1} \sum_{i=j}^{n}a_{i}\dbinom{i}{j}x^{i-j}. \end{equation} Hence, \begin{align*} \operatorname*{ev}\limits_{y\to 0}\dfrac{P\left( x+y\right) -P\left( x\right) }{y} & =\operatorname*{ev}\limits_{y\to 0}\sum_{j=1} ^{n}y^{j-1}\sum_{i=j}^{n}a_{i}\dbinom{i}{j}x^{i-j}=\sum_{j=1}^{n}0^{j-1} \sum_{i=j}^{n}a_{i}\dbinom{i}{j}x^{i-j}\\ & \qquad\left( \begin{array} [c]{c} \text{by the definition of }\operatorname*{ev}\limits_{y\to 0}\text{, because the }y^{j-1}\\ \text{are genuine polynomials in }y \end{array} \right) \\ & =\underbrace{0^{1-1}}_{=1}\sum_{i=1}^{n}a_{i}\underbrace{\dbinom{i}{1}} _{=i}x^{i-1}+\sum_{j=2}^{n}\underbrace{0^{j-1}}_{\substack{=0\\\text{(since }j-1>0\\\text{(because }j\geq2\text{))}}}\sum_{i=j}^{n}a_{i}\dbinom{i} {j}x^{i-j}\\ & \qquad\left( \text{here, we have split off the addend for }j=1\text{ from the sum}\right) \\ & =\underbrace{\sum_{i=1}^{n}a_{i}ix^{i-1}}_{\substack{=\dfrac{d} {dx}P\\\text{(by \eqref{darij.pf.t4.der})}}}+\underbrace{\sum_{j=2}^{n} 0\sum_{i=j}^{n}a_{i}\dbinom{i}{j}x^{i-j}}_{=0}=\dfrac{d}{dx}P. \end{align*} In other words, $\dfrac{d}{dx}P=\operatorname*{ev}\limits_{y\to 0}\dfrac{P\left( x+y\right) -P\left( x\right) }{y}$. This completes the proof of Theorem 5. $\blacksquare$

Now, we can prove Theorem 1:

Proof of Theorem 1. Theorem 5 (applied to $P=\dbinom{x}{n}$) shows that the polynomial $\dbinom{x+y}{n}-\dbinom{x}{n}\in\mathbb{Q} \left[ x,y\right] $ is divisible by $y$, and that we have \begin{equation} \dfrac{d}{dx}\dbinom{x}{n}=\operatorname*{ev}\limits_{y\to 0} \dfrac{\dbinom{x+y}{n}-\dbinom{x}{n}}{y}. \label{darij.pf.t1.1} \tag{3} \end{equation}

Now, \begin{align*} \dbinom{x+y}{n} & =\dbinom{y+x}{n}=\sum_{k=0}^{n}\dbinom{y}{k}\dbinom{x} {n-k}\qquad\left( \begin{array} [c]{c} \text{by Theorem 2, applied to }y\text{ and }x\\ \text{instead of }x\text{ and }y \end{array} \right) \\ & =\underbrace{\dbinom{y}{0}}_{=1}\underbrace{\dbinom{x}{n-0}}_{=\dbinom{x} {n}}+\sum_{k=1}^{n}\dbinom{y}{k}\dbinom{x}{n-k}\\ & \qquad\left( \text{here, we have split off the addend for }k=0\text{ from the sum}\right) \\ & =\dbinom{x}{n}+\sum_{k=1}^{n}\dbinom{y}{k}\dbinom{x}{n-k}. \end{align*} Subtracting $\dbinom{x}{n}$ from this equality, we find \begin{align*} \dbinom{x+y}{n}-\dbinom{x}{n} & =\sum_{k=1}^{n}\underbrace{\dbinom{y}{k} }_{\substack{=\dfrac{y}{k}\dbinom{y-1}{k-1}\\\text{(by Proposition 3)} }}\dbinom{x}{n-k}\\ & =\sum_{k=1}^{n}\dfrac{y}{k}\dbinom{y-1}{k-1}\dbinom{x}{n-k}=y\sum_{k=1} ^{n}\dfrac{1}{k}\dbinom{y-1}{k-1}\dbinom{x}{n-k}. \end{align*} Dividing this equality by $y$, we find \begin{equation} \dfrac{\dbinom{x+y}{n}-\dbinom{x}{n}}{y}=\sum_{k=1}^{n}\dfrac{1}{k} \dbinom{y-1}{k-1}\dbinom{x}{n-k}. \end{equation} Now, \eqref{darij.pf.t1.1} becomes \begin{align*} \dfrac{d}{dx}\dbinom{x}{n} & =\operatorname*{ev}\limits_{y\to 0}\underbrace{\dfrac{\dbinom{x+y}{n}-\dbinom{x}{n}}{y}}_{ =\sum\limits_{k=1}^{n} \dfrac{1}{k}\dbinom{y-1}{k-1}\dbinom{x}{n-k}}\\ & =\operatorname*{ev}\limits_{y\to 0}\sum_{k=1}^{n}\dfrac{1}{k} \dbinom{y-1}{k-1}\dbinom{x}{n-k} \\ & =\sum_{k=1}^{n}\dfrac{1}{k}\underbrace{\dbinom {0-1}{k-1}}_{\substack{=\dbinom{-1}{k-1}=\left( -1\right) ^{k-1}\\\text{(by Proposition 4, applied to }m=k-1\\\text{(since }k-1\in\mathbb{N}\text{))} }}\dbinom{x}{n-k}\\ & \qquad \left(\begin{array}{c} \text{by the definition of } \operatorname*{ev}\limits_{y\to 0}\text{,} \\ \text{since the } \dbinom{y-1}{k-1} \text{ are genuine polynomials in } y \end{array} \right) \\ & =\sum_{k=1}^{n}\dfrac{1}{k}\left( -1\right) ^{k-1}\dbinom{x}{n-k} =\sum_{k=1}^{n}\dfrac{\left( -1\right) ^{k-1}}{k}\dbinom{x}{n-k}. \end{align*} This proves Theorem 1. $\blacksquare$