The Method of Snake Oil
The method of the snake oil is
very useful tool in
evaluating various, frequently
huge combinatorial sums, and in proving combinatorial
identities.
We will use several examples
to give a flavor and illustration of the method.
The general principle is as follows:
Suppose we want to calculate a sum \(S\).
First we want to identify the free variable
on which \(S\) depends. Assume that \(n\) is such a variable
and let \(S=f(n)\). The goal is to find
the generating function \(F(x)\) for the sequence \(\left(f(n)\right)_{n=1}^{\infty}\).
We will multiply \(S\) by \(x^n\) and sum over all \(n\).
At this moment we have (at least) a double summation:
external in \(n\) and internal in \(S\).
Then we interchange the order of summation and
get the value of internal sum in terms of \(n\).
In such a way we get certain coefficients of the
generating function which are in fact the values
of \(S\) in dependence of \(n\).
In solving problems of this type we usually encounter
several sums. Here we will first list some of these sums.
The identity involving \(\sum_n \binom mnx^n\) is
known from before:
\[(1+x)^m=\sum_n \binom mn x^n.\]
Sometimes we will use the identity for
\(\sum_n \binom{n}{k} x^n\) which is already mentioned in the list
of generating functions:
\[\frac1{(1-x)^{k+1}}=\sum_n \binom{n+k}{k}x^n.\]
Among the common sums we will encounter those involving
only even (or odd) indices.
For example we have
\((1+x)^m = \sum_n \binom{m}{n} x^n\), hence
\((1-x)^m = \sum_n \binom{m}{n} (-x)^n\).
Adding and subtracting yields:
\[\sum_n \binom{m}{2n} x^{2n}=\frac
{\left((1+x)^m+(1-x)^m\right)}2,\]
\[\sum_n \binom{m }{2n+1} x^{2n+1}=\frac
{\left((1+x)^m-(1-x)^m\right)}2.\]
In a similar fashion we prove:
\[\sum_n \binom{2n}{m} x^{2n} = \frac {x^m}2 \left(\frac 1{(1-x)^{m+1}} + \frac {(-1)^m}{(1-x)^{m+1}} \right),
\;\;\mbox{and}\]
\[\sum_n \binom{2n+1}{m} x^{2n+1} = \frac {x^m}2 \left(\frac 1{(1-x)^{m+1}} - \frac {(-1)^m}{(1-x)^{m+1}} \right).\]
The following identity is also used quite frequently:
\[\sum_n \frac 1{n+1}\binom{2n}{n} x^n =
\frac 1{2x}(1-\sqrt{1-4x}).\]
Problem 9
Evaluate the sum \[\sum_k \binom{k}{n-k}.\]
Let \(n\) be the free variable and
denote the sum by \[f(n)=\sum_k \binom{k}{n-k}.\]
Let \(F(x)\) be the generating function of the
sequence \(f(n)\), i.e.
\[F(x)=\sum_n x^nf(n)=\sum_n x^n \sum_k
\binom k{n-k}=\sum_n \sum_k \binom k{n-k}x^n.\]
We can rewrite the previous equation as
\[F(x)=\sum_k \sum_n \binom{k}{n-k}x^n =
\sum_k x^k \sum_n \binom{k}{n-k}x^{n-k},\]
which gives \[F(x)=\sum_k x^k(1+x)^k=\sum_k
(x+x^2)^k =\frac 1{1-(x-x^2)}= \frac 1{1-x-x^2}.\]
However this is very similar to the generating
function of a Fibonacci’s sequence,
i.e. \(f(n)=F_{n+1}\) and we arrive to
\[\sum_k \binom{k }{n-k} = F_{n+1}.\]
Problem 10
Evaluate the sum
\[\sum_{k=m}^n (-1)^k \binom nk \binom km.\]
If \(n\) is a fixed number, then \(m\) is a free
variable on which the sum depends. Let
\( f(m)=\sum_{k=m}^n (-1)^k \binom nk \binom km\)
and let \(F(x)\) be the generating function of the
sequence \(f(m)\),
i.e. \(F(x)=\sum_m f(m)x^m\). Then we have
\[F(x) = \sum_m f(m)x^m = \sum_m x^m \sum_{k=m}^n
(-1)^k \binom nk \binom km=\]
\[= \sum_{k\leqslant n} (-1)^k \binom nk
\sum_{m \leqslant k} \binom kmx^m=
\sum_{k\leqslant n}\binom nk (1+x)^k.\]
Here we have used \(\sum_{m \leqslant k} \binom{k}{m}x^m=(1+x)^k\). Dalje je
\[F(x) = (-1)^n \sum_{k\leqslant n} \binom{n}{k} (-1)^{n-k}(1+x)^k = (-1)^n\Big((1+x)-1\Big)^n=(-1)^nx^n\]
Therefore we obtained \(F(x)=(-1)^n x^n\)
and since this is a generating function of the sequence \(f(m)\)
we have
\[f(m)=\left\{\begin{array}{rl}
(-1)^n, & n=m \newline
0, & m < n \mbox{ .} \end{array}
\right.\]
Problem 11 Evaluate the sum
\( \sum_{k=m}^n \binom nk \binom km\).
Let
\( f(m)=\sum_{k=m}^n \binom nk \binom km\) and
\( F(x)=\sum_m x^mf(m)\). Then we have
\[F(x) = \sum_m x^mf(m) = \sum_m x^m \sum_{k=m}^n
\binom nk \binom km =
\sum_{k\leqslant n} \binom nk
\sum_{m\leqslant k} \binom kmx^m=\sum_{k\leqslant n}
\binom nk (1+x)^k,\]
implying \(F(x)=(2+x)^n\). Since \[(2+x)^n=\sum_m \binom nm
2^{n-m}x^m,\] the value of the required sum is
\( f(m)=\binom nm 2^{n-m}\).
Problem 12
Evaluate \[\sum_k \binom{n}{\left[\frac k2\right]} x^k.\]
We can divide this into two sums
\[\sum_k \binom{n}{\left[\frac k2\right]} x^k =
\sum_{k=2k_1} \binom{n}{\left[\frac {2k_1}2\right]}
x^{2k_1} +
\sum_{k=2k_2+1} \binom{n}
{\left[\frac {2k_2+1}2\right]} x^{2k_2+1}=\]
\[=\sum_{k_1} \binom{n}{k_1} (x^2)^{k_1} + x\sum_{k_2}
\binom{n}{k_2} (x^2)^{k_2}=(1+x^2)^n+x(1+x^2)^n,\]
or equivalently
\[\sum_k \binom{n}{\left[\frac k2\right]} x^k = (1+x)(1+x^2)^n.
\]
Problem 13 Determine the elements of the sequence:
\[f(m)=\sum_k \binom{n}{k}\binom{n-k}{\left[\frac
{m-k}2\right]}y^k.\]
Let \(F(x)=\sum_m x^mf(m)\). We then have
\[F(x) = \sum_m x^m \sum_k \binom{n}{k}\binom{n-k}
{\left[\frac {m-k}2\right]}y^k
= \sum_k \binom{n}{k} y^k \sum_m \binom{n-k}
{\left[\frac {m-k}2\right]} x^m=\]
\[=\sum_k \binom{n}{k} y^kx^k \sum_m \binom{n-k}
{\left[\frac {m-k}2\right]}x^{m-k} =
\sum_k \binom{n}{k} y^kx^k (1+x)(1+x^2)^{n-k}.\]
Hence
\[F(x)=(1+x)\sum_k \binom{n}{k}
(1+x^2)^{n-k}(xy)^k=(1+x)(1+x^2+xy)^n.\]
For \(y=2\) we have that \(F(x)=(1+x)^{2n+1}\),
implying that \(F(x)\) is the generating function of the
sequence \(\binom{2n+1}{m}\) and we get the following
combinatorial identity:
\[\sum_k \binom{n}{k}\binom{n-k}
{\left[\frac {m-k}2\right]}2^k = \binom{2n+1}{m}.\]
Setting \(y=-2\) we get
\(F(x)=(1+x)(1-x)^{2n}=(1-x)^{2n}+x(1-x)^{2n}\)
hence the coefficient near \(x^m\) equals
\( \binom{2n}{m} (-1)^m + \binom{2n}{m-1}
(-1)^{m-1} = (-1)^m \left[\binom{2n}{m} -
\binom{2n}{m-1}\right]\) which implies
\[\sum_k \binom nk\binom{n-k}
{\left[\frac {m-k}2\right]}(-2)^k = (-1)^m \left[\binom{2n}m-
\binom{2n}{m-1}\right].\]
Problem 14
Prove that
\[\sum_k \binom nk\binom kjx^k = \binom nj x^j(1+x)^{n-j}\]
for each \(n\geq 0\)
If we fix \(n\) and let \(j\) be the free variable
and
\(f(j)=\sum_k \binom nk\binom kj x^k\),
\(g(j)=\binom nj x^j (1+x)^{n-j}\),
then the corresponding generating functions are
\[F(y)=\sum_j y^j f(j), \quad\quad G(y)=\sum_j y^jg(j).\]
We want to prove that \(F(y)=G(y)\).
We have \[F(y)=\sum_j y^j \sum_k\binom nk\binom kj
x^k =
\sum_k \binom nkx^k \sum_j \binom kj y^j =
\sum_k \binom nk x^k (1+y)^k,\]
hence \(F(y)=(1+x+xy)^n\).
On the other hand we have
\[G(y)= \sum_j y^j \binom nj
x^j(1+x)^{n-j} = \sum_j \binom nj
(1+x)^{n-j} (xy)^j=(1+x+xy)^n,\]
hence \(F(y)=G(y)\).
The real power of the generating functions
method can be seen in the following example.
Problem 15 Evaluate the sum
\[\sum_k \binom{n+k}{m+2k}\binom{2k}{k}\frac {(-1)^k}{k+1}\]
for \(m,n \geq 0\).
Since there are quite a lot of variables
elementary combinatorial methods doesn’t offer
an effective way to treat the sum.
Since \(n\) appears on only one place in the sum,
it is natural to consider the sum as a function on \(n\)
Let
\(F(x)\) be the generating series of such functions. Then
\[F(x)= \sum_n x^n \sum_k \binom{n+k}{m+2k}
\binom{2k}{k}\frac {(-1)^k}{k+1}=
\sum_k \binom{2k}{k} \frac {(-1)^k}{k+1} x^{-k} \sum_n
\binom{n+k}{m+2k}x^{n+k}=\]
\[=\sum_k \binom{2k}{k} \frac {(-1)^k}{k+1} x^{-k} \frac
{x^{m+2k}}{(1-x)^{m+2k+1}}=
\frac {x^{m+2k}}{(1-x)^{m+2k+1}} \sum_k \binom{2k}{k}
\frac 1{k+1}\left\{\frac {-x}{(1-x)^2} \right\}^k=\]
\[=\frac {-x^{m-1}}{2(1-x)^{m-1}}
\left\{ 1-\sqrt{1+\frac {4x}{(1-x)^2}} \right\}=
\frac {-x^{m-1}}{2(1-x)^{m-1}}
\left\{ 1-\frac {1+x}{1-x} \right\}=
\frac {x^m}{(1-x)^m}.\]
This is a generating function of the sequence
\( \binom{n-1}{m-1}\) which establishes
\[\sum_k \binom{n+k}{m+2k}\binom{2k}{k}
\frac {(-1)^k}{k+1} = \binom{n-1}{m-1}.\]
Problem 16 Prove the identity
\[\sum_k \binom{2n+1}{k} \binom{m+k}{2n} = \binom{2m+1}{2n}.\]
Let
\( F(x)=\sum_m x^m\sum_k \binom{2n+1}{k} \binom{m+k}{2n}\) and
\( G(x)=\sum_m x^m\binom{2m+1}{2n}\)
the generating functions of the expressions on the left and right
side of the required equality.
We will prove that \(F(x)=G(x)\).
We have \[F(x)=\sum_m x^m\sum_k \binom{2n+1}{k}\binom{m+k}{2n} =
\sum_k \binom{2n+1}{2k}\sum_m \binom{m+k}{2n}=\]
\[=\sum_k \binom{2n+1}{2k}\sum_m \binom{m+k}{2n} x^m =
\sum_k \binom{2n+1}{2k} x^{-k} \sum_m \binom{m+k}{2n}x^{m+k}=\]
\[=\sum_k\binom{2n+1}{2k} x^{-k}\frac{x^{2n}}{(1-x)^{2n+1}}=
\frac{x^{2n}}{(1-x)^{2n+1}}\sum_k\binom{2n+1}{2k}
\left( x^{-\frac 12} \right)^{2k}.\]
We already know that
\( \sum_k\binom{2n+1}{2k} \left( x^{-\frac 12} \right)^{2k} =
\frac 12 \left( \left(1+\frac 1{\sqrt{x}}\right)^{2n+1}+
\left(1-\frac 1{\sqrt{x}}\right)^{2n+1}\right)\) so
\[F(x)=\frac 12 (\sqrt{x})^{2n-1} \left(
\frac 1{(1-\sqrt{x})^{2n+1}} -
\frac 1{(1+\sqrt{x})^{2n+1}}\right).\]
On the other hand
\[G(x)=\sum_m \binom{2m+1}{2n}x^m =
\left(x^{-1/2}\right)\sum_m\binom{2m+1}{2n}
\left(x^{1/2} \right)^{2m+1},\]
implying \[G(x)=\left(x^{-1/2} \right) \left[
\frac {(x^{1/2})^{2n}}2 \left(\frac 1{(1-x^{1/2})^{2n+1}} -
(-1)^{2n}\frac 1{(1+x^{1/2})^{2n+1}} \right)\right],\] or
\[G(x)=\frac 12 (\sqrt{x})^{2n-1} \left(
\frac 1{(1-\sqrt{x})^{2n+1}} -\frac
1{(1+\sqrt{x})^{2n+1}}\right). \]
Problem 17
Prove that
\[ \sum_{k=0}^n \binom{2n}{2k} \binom{2k }{k}
2^{2n-2k}=\binom{4n}{2n}.\]
Let \(n\) be the free variable
on the left and right side of \(F(x)\) and \(G(x)\).
We want to prove the equality of these generating functions.
\[F(x) = \sum_n x^n \sum_{0\leqslant k\leqslant n}
\binom{2n}{2k} \binom{2k}{k} 2^{2n-2k}
= \sum_{0\leqslant k} \binom{2k}{k}
2^{-2k}\sum_n \binom{2n}{2k} x^n 2^{2n},\]
\[F(x)=\sum_{0\leqslant k} \binom{2k}{k}
2^{-2k}\sum_n \binom{2n}{2k}
(2\sqrt x)^{2n}.\]
Now we use the formula for summation of even powers and get
\[\sum_n \binom{2n}{2k} (2\sqrt x)^{2n} = \frac 12
(2\sqrt x)^{2k}
\left( \frac 1{(1-2\sqrt x)^{2k+1}} +
\frac 1{(1+2\sqrt x)^{2k+1}}\right),\]
and we further get
\[F(x)=\frac 1{2(1-2\sqrt x)} \sum_k
\binom{2k}{k} \left(\frac x{(1-2\sqrt x)^2} \right)^k
+\frac 1{2(1+2\sqrt x)} \sum_k \binom{2k}{k}
\left(\frac x{(1+2\sqrt x)^2} \right)^k.\]
Since \( \sum_n \binom{2n}{n}x^n = \frac 1{\sqrt{1-4x}}\) we get
\[F(x)=\frac 1{2(1-2\sqrt x)}\cdot \frac
1{\sqrt{1-4\frac x{(1-2\sqrt x)^2}}}
+\frac 1{2(1+2\sqrt x)}\cdot
\frac 1{\sqrt{1-4\frac x{(1+2\sqrt x)^2}}},\]
which implies
\[F(x)=\frac 1{2\sqrt{1-4\sqrt x}} +
\frac 1{2\sqrt{1+4\sqrt x}}.\]
On the other hand for \(G(x)\) we would like
to get the sum \( \sum_n \binom{4n}{2n}x^n\).
Since
\( \sum_n
\binom{2n}{n} x^n = \frac 1 {\sqrt {1-4x}}\) we have
\( \sum_n\binom{2n}{n} (-x)^n = \frac 1 {\sqrt {1+4x}}\) hence
\[G(x)=\frac 12 \left( \frac 1{\sqrt{1-4\sqrt x}} +
\frac 1{\sqrt{1+4\sqrt x}}\right)\] and \(F(x)=G(x)\).
The following problem is slightly harder
because the standard idea of snake oil
doesn’t lead to a solution.
Problem 18 (Moriati) For given \(n\) and \(p\)
evaluate \[\sum_k \binom{2n+1}{2p+2k+1}\binom{p+k}{k}.\]
In order to have shorter formulas
let us introduce \(r=p+k\). If we assume that \(n\)
is the free variable then the required sum is equal to
\[f(n)=\sum_r \binom{2n+1}{2r+1}\binom{r}{p}.\]
Take \(F(x)=\sum_n x^{2n+1}f(n)\). This is somehow natural since
the binomial coefficient contains the term \(2n+1\).
Now we have \[F(x)=\sum_n x^{2n+1} \sum_r \binom{2n+1}{2r+1}
\binom{r}{p}=\sum_r \binom{r}{p}
\sum_n\binom{2n+1}{2r+1}x^{2n+1}.\]
Since \[\sum_n \binom{2n+1}{2r+1}x^{2n+1} = \frac {x^{2r+1}}2
\left(\frac 1{(1-x)^{2r+2}} + \frac 1{(1+x)^{2r+2}} \right),\]
we get
\[F(x)=\frac 12\cdot \frac x{(1-x)^2}\sum_r \binom{r}{p}
\left(\frac {x^2}{(1-x)^2}\right)^r
+\frac 12\cdot \frac x{(1+x)^2}\sum_r \binom{r}{p}
\left(\frac {x^2}{(1+x)^2}\right)^r,\]
\[F(x)=\frac 12\frac x{(1-x)^2}\frac {\left(\frac
{x^2}{(1-x)^2}\right)^p}{\left(1-
\frac {x^2}{(1-x)^2}\right)^{p+1}}
+\frac 12\frac x{(1+x)^2}\frac {\left(\frac
{x^2}{(1+x)^2}\right)^p}{\left(1-\frac {x^2}{(1+
x)^2}\right)^{p+1}},\]
\[F(x)=\frac 12 \frac {x^{2p+1}}{(1-
2x)^{p+1}}+\frac 12 \frac {x^{2p+1}}{(1+2x)^{p+1}}=
\frac {x^{2p+1}}2((1+2x)^{-p-1}+(1-2x)^{-p-1}),\]
implying
\[f(n)=\frac 12 \left(\binom{-p-1}{2n-2p}2^{2n-2p}+
\binom{-p-1}{2n-2p}2^{2n-2p} \right),\]
and after simplification
\[f(n)=\binom{2n-p}{2n-2p}2^{2n-2p}.\]
We notice that for most of the problems we didn’t
make a substantial deviation from the method and we used
only a handful of identities. This method can also be
used in writing computer algorithms for symbolic evaluation
of number of sums with binomial coefficients.