11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A completely different path could be by using Horner's method that besides its optimal efficiency for evaluating polynomials gives also, as a by-product, evaluation of their derivatives (physics.utah.edu/~detar/lessons/c++/array/node1.html) and node2, node3, node4. $\endgroup$ – Jean Marie Sep 26 '16 at 10:19
  • $\begingroup$ @JeanMarie That would imply first expanding the binomial (=repeated convolution: $x*(x-1)=x^2-x$ then $(x^2-x)*(x-2)$, etc) to find out the coefficients. In that case, differentiation is quite simple, but in terms of my goals, that would add another step in computing, which, itself, would imply one multiplication and one summation per each coefficient (minus one). It does count as a solution, unfortunately it's costly in terms of cycles. $\endgroup$ – a concerned citizen Sep 26 '16 at 10:32
  • $\begingroup$ Take care of my comment below in defining $H$ as a summation: that is valid for n natural integer (>1) only! . Its extension to real (and complex) indices can be done only via the $\psi$ function, so the "complexity" remains. $\endgroup$ – G Cab Sep 26 '16 at 15:16
  • $\begingroup$ apart from the typo in the summation bounds of the formula I gave, which I corrected from $n$ to $n-1$, then doing $d/dx\; C(y(x),n)\; =\; d/dy \; C(y(x),n)\; d/dx\; y(x)$, where does the (-1)^n come from? $\endgroup$ – G Cab Sep 26 '16 at 15:42
  • $\begingroup$ @GCab That was a bit I unintentionally left out: the binomial is expressed, in my case, as the product (simpler to compute), and there is an extra $(-1)^n$ there that I forgot about. I only realized now, that you said, that I hadn't included it in the OP. Sorry for the omission, I simply forgot about it. The thing is, I need the derivative in order to calculate a single variable, with which I compute the full polynomial, from which I then extract the roots (I know I could do it with a table for the variable, instead). So, minus or not, the roots are eventually sorted as the negative ones. $\endgroup$ – a concerned citizen Sep 26 '16 at 15:50
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the answer, but please don't forget my background is not mathematics. I just checked functions.wolfram to see what this is about, and I see that the specific values of $S_k^n$ for increasing $n$ get higher and higher. Frankly, I find that scary. Unless the derivatives reduce them, I'm afraid this seems to get exponentially more computational. Of course, this is certainly more than meets the eye, so I'd rather wait for more answers before trying to reach a conclusion. $\endgroup$ – a concerned citizen Sep 26 '16 at 13:02
  • $\begingroup$ It depends from what it is exactly your goal, computing binomial and derivative for high values of $n$? In any case, my answer was to clear the mathematical framework. Also consider that the Stirling numbers obey a simple recursive definition, easy to compute, and since they come with alternate sign, the formula can be somehow "reduced". $\endgroup$ – G Cab Sep 26 '16 at 14:08
  • $\begingroup$ Your formulas are not only very simple to implement, but they also agree with wxMaxima! Thank you very much! However, if I try to replace $y$ with my particular need, $\frac{n+1){2}x+\frac{n-1}{2}$, I end up with different (but close) graphs. Now, since the "default" implementation works perfectly, I will first try and, using your derivation, I will try to adapt it to my needs. One question, though: is the harmonic number you're using the one from the 2nd formula here: functions.wolfram.com/GammaBetaErf/HarmonicNumber/02 (the summation)? $\endgroup$ – a concerned citizen Sep 26 '16 at 14:38
  • $\begingroup$ @aconcernedcitizen, a) of course, when replacing $y=ax+b$ remember you still have to do a furter step in the differentiation $d/dx C(y(x),n)=d/dy C(y(x),n) d/dx y(x)$, which I did not include to keep the presentation more neat. b) yes, the definition of the $H$ is as in the link you cite, but take care that the "summation" definition is valid only for natural integers indices as marked aside there, while for real indices the first definition only holds, which matches with the given expression in $\psi$ $\endgroup$ – G Cab Sep 26 '16 at 15:10
  • $\begingroup$ sorry to all, there was a typo in the summation bounds in the last two equations: should have been $n-1$ instead of $n$. Corrected $\endgroup$ – G Cab Sep 26 '16 at 15:33
4
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ The answer looks very nice mathematically, wxMaxima agrees in totality, but that would mean calling $f(x)$ $n$ times for summation (minus one term each iteration). In this case, I'm afraid I'm better off with the previously mentioned Horner's method. $\endgroup$ – a concerned citizen Sep 26 '16 at 10:55
  • $\begingroup$ @aconcernedcitizen: You may be right. In fact I just thought about a rather easy to follow mathematical derivation. $\endgroup$ – Markus Scheuer Sep 26 '16 at 11:00
  • 1
    $\begingroup$ My first, brutish thought was $f(x)-f(x-10^{-p})$, where $p$ would have to be small enough. But this would necessitate a multiplication by $10^{p}$, afterwards, imagine the loss of precision. $\endgroup$ – a concerned citizen Sep 26 '16 at 11:07
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

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