Valutare una sommatoria con parti intere (IMO 1968 es 6)

[dario2994]

Valutare per ogni $ $n\in\mathbb{N} $ la sommatoria:
$ $\sum_{i=0}^{\infty}\left\lfloor\frac{n+2^i}{2^{i+1}}\right\rfloor $

[jordan]

Staffetta tdn, problema 9

Soluzione problema 9. $ \displaystyle \sum_{i=0}^{+\infty}{\left\lfloor \frac{n}{2^{i+1}}+\frac{1}{2}\right\rfloor} $ $ \displaystyle =\sum_{i=0}^{+\infty}{\left\lfloor\frac{n}{2^i}\right\rfloor-\left\lfloor\frac{n}{2^{i+1}}\right\rfloor}=\lfloor n\rfloor $. []

[dario2994]

Uff... mi hai bruciato il problema... ma non capisco la soluzione :| Potrei sprecare un poco di parole almeno xD

[Haile]

Uff... mi hai bruciato il problema... ma non capisco la soluzione Potrei sprecare un poco di parole almeno xD

È una telescopic sum

[jordan]

Basta considerare l'identità $ \lfloor x\rfloor +\lfloor x+\frac{1}{2}\rfloor =\lfloor 2x\rfloor $.Per dimostrarlo in maniera grezza è sufficiente farsi i due casi $ 0\le \{x\}<\frac{1}{2} $ e $ \frac{1}{2}\le \{x\}<1 $..
Adesso divertitevi a generalizzare questa identità

[dario2994]

Davvero figo :)
La mia dimostrazione è diversa... lavora per induzione sfruttando il fatto che al variare di n verso n+1 solo una di quelle parti intere cambia per il lemma:
$ n=2^a(2b+1) $ per un solo a intero... che è banale ;)

Per il lemma postato da te... immagino che la generalizzazione sia:
$ $ \sum_{i=0}^{n-1}\left\lfloor x+\frac{i}{n}\right\rfloor=\lfloor nx\rfloor $
Che mi pare di aver dimostrato in modo carino ponendo $ x=a+\frac{b}{n}+k $ con a,b naturali, b<n, k reale minore di 1/n.

[jordan]

Si, è l'identità di Hermite.. a riguardo può essere utile darsi una bella letta a questo

[dario2994]

Uhm alla fine tranne quest'identità che è proprio bella ci sono solo un ammasso di teoremi più o meno ovvi se non sbaglio... questo lemma invece è figo, e può tornare utile :)