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