Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Los números del $0$ al $2^k-1$ son los números que tienen $k$ o menos cifras en binario, lo que equivale a una sucesión de $k$ dígitos $0$ o $1$ si permitimos ceros a la izquierda. Queremos ver cuántos unos hay de entre todas esas sucesiones, para lo que haremos el siguiente truco: en total hay $k\cdot 2^k$ dígitos entre todas las sucesiones y, como el cero y el uno ocurren el mismo número de veces, habrá $k\cdot 2^{k-1}$ ceros y $k\cdot 2^{k-1}$ unos. En otras palabras, hemos visto que $s(0)+s(1)+\ldots+s(2^k-1)=k\cdot 2^{k-1}$. Si tenemos en cuenta que $s(0)=0$ y $s(2^k)=1$, obtenemos que $\sigma(k)=k\cdot 2^{k-1}+1$.