binaire som

Lemma: Voor alle $x\in \mathbb{R}^+$ geldt: $$\left\lfloor x+\frac{1}{2}\right \rfloor = \lfloor 2x \rfloor - \lfloor x \rfloor$$

Bewijs: We onderscheiden twee gevallen: het deel achter de komma van $x$ is kleiner of groter dan $\frac{1}{2}$. Door dit onderscheid is niet moeilijk om in te zien dat de gelijkheid klopt, aangezien in het eerste geval $\left\lfloor x+\frac{1}{2} \right\rfloor = \lfloor x \rfloor$ en $\lfloor 2x \rfloor = 2 \lfloor x \rfloor$. Tweede geval is in zekere zin analoog.

Bekijk nu ieder term in het linkerlid van de uitdrukking:
$$\sum_{i=1}^n \left\lfloor \frac{n+2^{i-1}}{2^i}\right \rfloor = \left\lfloor \frac{n}{2^{i-1}} \right\rfloor - \left\lfloor \frac{n}{2^i} \right\rfloor$$

Telescopen geeft dat de te bewijzen gelijkheid equivalent is aan $$ \lfloor n \rfloor - \left\lfloor \frac{n}{2^n} \right\rfloor = n$$
Dit is waar omdat $\lfloor n \rfloor = n$ en $\frac{n}{2^n} < 1$ aangezien $2^n>n$ voor alle $n \ge 1$