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 the generating function \( F(x) \) for the sequence \( f(n) \). 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}.\]
Problem 10
 
Evaluate the sum \[ \sum_{k=m}^n (-1)^k \binom nk \binom km.\]
Problem 11
 
Evaluate the sum \( \sum_{k=m}^n \binom nk \binom km \).
Problem 12
 
Evaluate \[ \sum_k \binom{n}{\left[\frac k2\right]} x^k.\]
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.\]
Problem 14
 
Prove that \[ \sum_k \binom nk\binom kjx^k = \binom nj x^j(1+x)^{n-j}\] for each \( n\geq 0 \)

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 \).
Problem 16
 
Prove the identity \[ \sum_k \binom{2n+1}{k} \binom{m+k}{2n} = \binom{2m+1}{2n}.\]
Problem 17
 
Prove that \[ \sum_{k=0}^n \binom{2n}{2k} \binom{2k }{k} 2^{2n-2k}=\binom{4n}{2n}.\]

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}.\]

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.


2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax
Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us