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

Question

La cuestión es si lo que sigue es cierto.

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

Mathematica puede simplificar de la siguiente manera, pero no puede reducir[] o resolver[].

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

Answer 1

Un método algo menos computacional es observar que ambos lados de la identidad cuentan el número de subconjuntos de $\{1,\dots,n\}$ con menos de $s$ elementos. Esto es obvio para el lado izquierdo. Es cierto para el lado derecho porque $2^{k-1}\pmatrix{n-k\\s-k}$ es el número de tales subconjuntos $S$ para lo cual $k$ es mínima, tal que $|S\cup\{1,\dots,k\}|\geq s$ ya que dicho subconjunto $S$ es la unión de un subconjunto arbitrario de $\{1,\dots,k-1\}$ y un subconjunto de tamaño $s-k$ de $\{k+1,\dots,n\}$ .

Answer 2

Una forma es por inducción en $n$ . Tenemos una serie de ecuaciones donde la primera ecuación es la identidad del triángulo de Pascal y la tercera utiliza la hipótesis inductiva, y el resto es básicamente por reindexación de sumas:

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

(No estoy seguro de que esto se considere "nivel de investigación", pero como la identidad del OP es tan bonita, no he podido resistirme).