Suma interesante

[Fedex]

Para un entero positivo $n$, sea $s(n)$ la suma de los dígitos de $n$ en representación binaria.
Encontrar el valor de:$$s(1)+s(2)+s(3)+\ldots +s\left (2^k\right )$$Para todo entero positivo $k$.

[¿hola?]

Spoiler: mostrar

Los números menores a $2^k$ tendrán $k$ dígitos (si tienen menos rellenamos con $0$ a la izquierda hasta que tengan $k$), es fácil ver que para cualquier posición habrá $2^{k-1}$ números con un $1$ en esa posición y $2^{k-1}$ números con un $0$, por lo que la suma de las sumas de dígitos sera $1*2^{k-1}*k+0*2^{k-1}*k$ mas $s(2^k)=1$, o sea $2^{k-1}k+1$ para todo $k$.

[Matías V5]

Para un entero positivo $n$, sea $s(n)$ la suma de los dígitos de $n$ en representación binaria.
Encontrar el valor de:$$s(1)+s(2)+\ldots +s\left (2^k\right )$$Para todo entero positivo $k$.

Si sólo ponés esos términos de la suma no se entiende si es todos los naturales hasta $2^k$ o sólo las potencias de $2$!
(Claro que si fuera el segundo caso sería bastante aburrido...)

[Fedex]

Corregido y dejo una solución .

Spoiler: mostrar

Llamamos $S_k = s(1) + ... + s(2^k)$
Para fabricar una relacion entre $S_k$ y $S_{k+1}$ usamos estas $2$ cosas:
- $s(2^a) = 1$
- Para todo $x < 2^a$ tenemos que $s(2^a+x) = s(x) + 1$
Entonces:
$S_{k+1} = \sum_{i=1}^{2^{k+1}} s(i) = \sum_{i=1}^{2^k} s(i) + \sum_{i=1}^{2^k-1}s(2^k+i) \; + \; s(2^{k+1}) = S_k + \sum_{i=1}^{2^k-1}[s(i)+1] \; + \; 1 = S_k + S_k - s(2^k) + 2^k - 1 +1 = 2S_k + 2^k - 1$
Esto nos queda definido como:
$S_1= s(1) + s(2) = 2$
$S_{k+1} = 2S_k + 2^k - 1$
Después de jugar un poco conjeturamos que $S_k = 2^{k-1}k +1$
Y lo vamos a probar por inducción:
Para el caso base $k=1$ y $S_1 = 2^{0}1+1 = 2$ cierto.
Luego si $S_k = 2^{k-1}k +1$ entonces $S_{k+1} = 2S_k + 2^k - 1 = 2^{k}k + 2 + 2^k - 1 = 2^{k}(k+1) + 1$
Concluimos con el paso inductivo y estamos.
Luego $s(1) + ... + s(2^k) = 2^{k-1}k + 1$

[Sandy]

Spoiler: mostrar

Hagamos algo más divertido y emparejemos cada número con su "opuesto". Está claro que queremos la suma de los dígitos de los números con $k$ o menos dígitos $+s\left (2^k\right )$.
Digamos que cada número con $k$ dígitos o menos en binario tiene $k$ dígitos (rellenando con $0$s a la izquierda).

Sea $n$ un número y $n'$ ese número tras intercambiar los $0$ por $1$ y los $1$ por $0$.
Es fácil ver que $n+n'=2^k-1=\underbrace{11\ldots 11}_{k}$ y $s(n)+s(n')=s(n+n')$, ya que al sumarlos no hay ningún acarreo de dígitos (donde $n$ tiene $1$, $n'$ tiene $0$ y viceversa).
Sumando también el $0$, ya que $s(0)=0$ tenemos los números del intervalo $\left [0, 2^k-1\right ]$, en $2^{k-1}$ parejas tales que $s(n)+s(n')=k$.
Luego $\sum \limits _{i=1}^{2^k} s(i)=k2^{k-1}+s\left (2^k\right )=k2^{k-1}+1$.