# Combinatorics Problem: $\sum _{k=0}^{s-1} \binom{n}{k}=\sum _{k=1}^s 2^{k-1} \binom{n-k}{s-k}$

The question is whether the below is true.

$$\sum _{k=0}^{s-1} \binom{n}{k}=\sum _{k=1}^s 2^{k-1} \binom{n-k}{s-k}$$

Mathematica can simplify as follows, but it fails to Reduce[] or Solve[].

$$2^n=\binom{n}{s} \, _2F_1(1,s-n;s+1;-1)+\binom{n-1}{s-1} \, _2F_1(1,1-s;1-n;2)$$

• I guess the easiest way is to check that both sides satisfy the same recurrence relation (as sequences in s), i.e., $-(s + 2)f(s + 2) + (n + 1)f(s + 1) + (s - n + 1)f(s)= 0$. – Martin Rubey Jun 28 '14 at 15:58
• MJK, you now have two answers to your question. If you find one or the other satisfactory, then you should consider accepting one of them as a solution: mathoverflow.net/help/accepted-answer – Todd Trimble Jun 30 '14 at 10:43

A slightly less computational method is to note that both sides of the identity count the number of subsets of $\{1,\dots,n\}$ with fewer than $s$ elements. This is obvious for the left hand side. It's true for the right hand side because $2^{k-1}\pmatrix{n-k\\s-k}$ is the number of such subsets $S$ for which $k$ is minimal such that $|S\cup\{1,\dots,k\}|\geq s$, since such a subset $S$ is the union of an arbitrary subset of $\{1,\dots,k-1\}$ and a subset of size $s-k$ of $\{k+1,\dots,n\}$.

• @MarcvanLeeuwen: $S$ does not contain $k$. – Timothy Chow Jun 29 '14 at 13:51
• @TimothyChow: Right. I somehow read that union sign as an intersection though admittedly that makes no sense. I'll leave my silly comment for now, but I'll make it self-destruct in some time. – Marc van Leeuwen Jun 29 '14 at 14:22

One way is by induction on $n$. We have a series of equations where the first equation is Pascal's triangle identity and the third uses the inductive hypothesis, and the rest is basically by re-indexing sums:

$$\begin{array}{lll} \sum_{k=0}^{s-1} \binom{n}{k} & = & \sum_{k=0}^{s-1} \binom{n-1}{k-1} + \sum_{k=0}^{s-1} \binom{n-1}{k} \\ & = & \binom{n-1}{s-1} + 2\sum_{k=0}^{s-2}\binom{n-1}{k} \\ & = & \binom{n-1}{s-1} + \sum_{k=1}^{s-1} 2^k\binom{n-1-k}{s-1-k} \\ & = & \binom{n-1}{s-1} + \sum_{k=2}^s 2^{k-1}\binom{n-k}{s-k} \\ & = & \sum_{k=1}^s 2^{k-1} \binom{n-k}{s-k}. \end{array}$$

(Not sure this is quite considered "research level", but since the identity of the OP is so cute, I couldn't resist.)

• I spent a puzzled couple of minutes wondering what was so cute about who the OP is, until I realized that's not what you meant by his/her identity ... – Jeremy Rickard Jun 28 '14 at 19:57
• @JeremyRickard lol... I use OP interchangeably for "Original Poster" and "Original Post". Nice bijective proof by the way (although it took me probably about as long puzzling through it as my remark took you). – Todd Trimble Jun 28 '14 at 20:08