# Combinatorial Proof that the Logarithm of a Product is the Sum of the Logarithms

I've been strongly drawn recently to the matter of the fundamental definition of the exponential function, & how it connects with its properties such as the exponential of a sum being the product of the exponentials, and it's being the eigenfunction of simple differentiation, etc. I've seen various posts inwhich clarification or demonstration or proof of such matters as how such & such a property proceeds from its definition as $$e^z\equiv\lim_{k\rightarrow\infty}\left(1+\frac{z}{k}\right)^k .$$ I'm looking at how there is a web of interconnected theorems about this; and I am trying to spin the web as a whole. This is not necessary for proving some particular item to be proven - a path along some one thread or sequence of threads is sufficient for that; but I think the matter becomes 'unified', and by reason of that actually simplified, when the web is perceived as an entirety. This is why I bother with things like combinatorial demonstrations of how the terms in a binomial expansion evolve towards the terms in a Taylor series as some parameter tends to ∞, when the matter at hand is actually susceptible of a simpler proof by taking the logarithm of both sides ... & other seeming redundancies.

To this end, another 'thread' I am looking at is that of showing that the coefficients in the Taylor series for $$\ln(1+z)$$ actually are a consequence of the requirement that the logarithm of a product be the sum of the logarithms, and ... if not quite a combinatorial derivation of them from that requirement, at least a reverse- (or sideways-) engineering equivalent of it - the combinatorially showing that if the coefficients be plugged into the Taylor series, then the property follows

Taking the approach that $$(1+x)(1+y) = 1+x+y+xy ,$$ plugging $$z=x+y+xy$$ into the series for $$\ln(1+z)$$ and hoping that all non-fully-homogeneous terms cancel out, leaving sum of the series for $$\ln(1+x)$$ & that for $$\ln(1+y)$$, we are left with proving that

$$\sum_{k=1}^\infty\left((-1)^k(k-1)!×\sum_{p\inℕ_0,q\inℕ_0,r\inℕ_0,p+q+r=k}\frac{x^{p+r}y^{q+r}}{p!q!r!}\right)$$$$=$$$$\sum_{k=1}^\infty(-1)^k\frac{x^k+y^k}{k} .$$

The inner sum of the LHS of this quite appalling-looking theorem is the trinomial expansion of $$(x+y+xy)^k$$ for arbitrary $$k$$, & the outer sum is simply the logarithm Taylor series expansion (with its $$k$$ in the denominator 'absorbed' into the combinatorial $$k!$$ in the numerator of the inner sum) . This theorem can be quite easily verified by 'brute force' - simply doing the expansions at the first (very!) few terms; but the labour of it escalates extremely rapidly. An algebraic manipulation package would no-doubt verify it at a good few more terms; but what I am looking-for is a showing of the fully general case: but I do not myself have the combinatorial toolage for accomplishing this.

So I am asking whether anyone can show me an outline of what to do ... or even actually do it for me, although that would probably take up a very great deal of space and be an extremely laborious task for the person doing it ... so I'm content to ask for just an outline of doing it, or for some 'signposts' as to how to do it - maybe someone knows some text on this kind of thing that they would recommend.

Your identity is a special case of a well-known binomial coefficient identity called Vandermonde's theorem: $$\sum_{r=0}^m \binom a{m-r}\binom nr = \binom {a+n}{r}.$$ This is an identity of polynomials in $$a$$ and $$n$$, where $$m$$ is a nonnegative integer. (The binomial coefficient $$\binom br$$ is defined for general $$b$$ by $$\binom br = b(b-1)\cdots (b-r+1)/r!$$ where $$r$$ is a nonnegative integer.) You can easily find many proofs of Vandermonde's theorem on the internet, so I won't give a reference here.

We also need $$\binom{b}{r} = (-1)^r \binom{-b+r-1}{r}$$, an identity of polynomials in $$b$$ that follows easily from the definition of binomial coefficients.

Your identity is equivalent to $$\sum_{r=0}^m(-1)^{m-r}\binom{m+n-r-1}{m-r}\binom nr = 0.$$ By the second identity above, the sum is equal to $$\sum_{r=0}^m\binom{-n}{m-r}\binom nr.$$ By Vandermonde's theorem this is $$\binom 0m$$, which is 0 for $$m>0$$.

• I just realized that this proof is essentially the same as Darij's. – Ira Gessel May 11 at 18:24

Maybe it's not too bad actually. What what needs to be shown reduces to is that $$\forall m\in ℕ_1\&n\in ℕ_1$$$$\sum_{p\in ℕ_0,q\in ℕ_0,r\in ℕ_0,p+r=m,q+r=n}\frac{(-1)^{p+q+r}(p+q+r-1)!}{p!q!r!} =0 ,$$ whence that

$$\sum_{r=0}^{\min(m,n)}\frac{(-1)^{m+n-r}(m+n-r-1)!}{(m-r)!(n-r)!r!} =0 .$$

And this can be essentialised yet further: basically it's tantamount to saying that the sum of the alternating (in sign) sequence of binomial numbers of degree $$n$$, which is unweighted well known to be zero, is also zero when weighted by any sequence of consecutive Pochhammer numbers of degree $$n-1$$. If this be proven, then my combinatorial proof of the at-the-outset-mentioned property of logarithms is upheld.

• I haven't proven it, but I've tested numerically using spreadsheets, & it appears to be true. I'm sure it could be quite easily proven. Those slick little tricks that are used for proving identities comprising binomial coefficients and agglomerates of factorials similar to them seem so obvious once you've seen them. But this one isn't any off-the-shelf identity that I recognise. But it's stooden-up to the numetical test by spreadsheet at every m & n I've putten into it so far. But no doubt doing that is anathema & hebdelugma amongst august & purist mathematicians! – AmbretteOrrisey Dec 1 '18 at 20:35
• Your identity is equivalent (via the substitution $k := m+n-r$) to Exercise 4 on UMN Fall 2017 Math 4990 homework set #4. I learnt it from Peter Scholze, who came up with it doing the exact same thing as you. (The proofs given at the two URLs are different.) – darij grinberg Dec 2 '18 at 6:17

Here's another proof that $$\log\bigl((1+x)(1+y)\bigr) = \log(1+x) + \log(1+y)$$ as formal power series. This assumes some facts about derivatives of formal power series that are not difficult to verify (e.g., a special case of the chain rule). It follows directly from the power series for $$\log(1+x)$$ that $$\frac{d\ }{dx} \log(1+x) = \frac{1}{1+x}.$$ Thus by the chain rule $$\frac{\partial\ }{dx} \log\bigl((1+x)(1+y)\bigr) = \frac{(1+y)}{(1+x)(1+y)}=\frac{1}{1+x} =\frac{\partial\ }{dx}\bigl(\log(1+x)+\log(1+y)\bigr).$$ Similarly $$\frac{\partial\ }{dy} \log\bigl((1+x)(1+y)\bigr) = \frac{1}{1+y}=\frac{\partial\ }{dy}\bigl(\log(1+x)+\log(1+y)\bigr).$$ Thus $$\log\bigl((1+x)(1+y)\bigr) - \bigl(\log(1+x)+\log(1+y)\bigr)$$ must be a constant and that constant must be 0.