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)$$



Combinatorics Problem: $\sum _{k=0}^{s-1} \binom{n}{k}=\sum _{k=1}^s 2^{k-1} \binom{n-k}{s-k}$
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\}$.


