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)$$
 A: 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.) 
A: 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\}$.
