Somme di parti intere..

[Sisifo]

A dir la veritá non so se é il posto giusto. Spero che non l'abbia giá fatto troppa gente..

Per ogni numero naturale n calcolare il valore della somma
$ \displaystyle \sum_{i=0}^{\infty} \left \lfloor \frac{n+2^i}{2^{i+1}} \right \rfloor $

[darkcrystal]

Non ho molto tempo (ne' voglia ) di formalizzarlo.
Scriviamo n in base 2.
Sia d la lunghezza della sua rappresentazione in base 2.
E' facile accorgersi che se la j-esima cifra è 1, allora l'aggiunta di $ 2^j $ fa diventare zero la j-esima cifra e aumenta di 1 il numero formato dalle cifre alla sua sinistra, pertanto la parte intera aumenta di 1.
Detto questo, è anche facile vedere che la sommatoria è equivalente alla somma dei numeri (binari) formati prendendo le prime d-1, d-2, d-3... cifre
Ma allora la j-esima cifra, se è zero non contribuisce alla sommatoria, se è 1 conta come: $ 2^j+2^{j-1}+2^{j-2}+...+2^0+1=2^{j+1}-1+1 $ dove il +1 è giustificato dal fatto che, come detto, quando si arriva a i=j, questo causa un'aggiunta di 1 alla parte intera.
Pertanto ogni cifra 1 conta esattamente $ 2^{j+1} $, il suo valore posizionale. Perciò la sommatoria è sempre uguale ad n.

Ciao!