strano ma vero...

[matthewtrager]

Dato un intero postivo t, dimostrare che per qualsiasi n>1:

$ \sum_{k=1,k\ne0mod(n)}^{t-1}\lceil{log_n} (\frac{t}{k})\rceil = t-1 $


Ciao!

[Simo_the_wolf]

Vogliamo dimostrare che, fissato n, la relazione valga per ogni t. Dimostriamolo per induzione:

Innanzitutto dimostriamolo per $ t<n $. Abbiamo che $ 1<t/k<n $ e quindi $ 0< log_n (\frac tk ) <1 $ e quindi $ \lceil log_n (\frac tk ) \rceil =1 $ per ogni $ k $ e quindi:

$ \displaystyle \sum_{k=1} ^{t-1} \lceil log_n (\frac tk ) \rceil =\sum_{k=1} ^{t-1} 1 = t-1 $

Ora il passo induttivo: supponiamo di averlo dimostrato per $ t $ e vogliamo dimostrarlo per $ nt-r $ dove $ r $ può variare da $ 0 $ a $ n-1 $. In questo modo avremmo dimostrato tutto.

Innanzitutto facciamo a parte il caso r=0. Notiamo che $ \lceil log_n (\frac {nt}k ) \rceil =\lceil log_n (n) + log_n (\frac tk ) \rceil = 1+ \lceil log_n (\frac tk ) \rceil $.

Quindi, sostituendo abbiamo che:

$ \displaystyle \sum_{k=1,n \nmid k} ^{nt-1} \lceil log_n (\frac {nt}k ) \rceil =\sum_{k=1, n\nmid k} ^{nt-1} 1 + \sum_{k=1,n \nmid k} ^{nt-1} \lceil log_n (\frac tk ) \rceil $.

Ora, i multipli di n tra $ 1 $ e $ nt-1 $ sono $ t-1 $ e la seconda sommatoria ha termini nulli per $ nt-1 \geq k\geq t $ poichè con questa condizione $ \frac 1n < \frac tk \leq 1 $ e, prendendo il logaritmo abbiamo $ -1 < log _n (\frac tk) \leq 0 $ e quindi $ \lceil log_n (\frac tk ) \rceil =0 $. quindi la sommatoria si riduce a $ k $ che va da $ 1 $ a $ t-1 $ che, per ipotesi induttiva sappiamo essere uguale a $ t-1 $. Quindi abbiamo:

$ \displaystyle \sum_{k=1,n \nmid k} ^{nt-1} \lceil log_n (\frac {nt}k ) \rceil =\sum_{k=1, n\nmid k} ^{nt-1} 1 + \sum_{k=1,n \nmid k} ^{nt-1} \lceil log_n (\frac tk ) \rceil $ $ \displaystyle= nt-1 -(t-1)+(t-1)=nt-1 $

e quindi va bene.

Ora bisogna dimostrarlo per $ r>0 $. Lo proviamo un'altra volta perchè adesso è ora di andare a fare la nanna

Ciaociao!

[Simo_the_wolf]

Ora, per il caso $ r>0 $ non ci resta che osservare che $ \lceil log_n \frac {nt-r}{nk} \rceil = \lceil log_n \frac tk \rceil $ per ogni $ k $ infatti avremo che , fissato $ k $ allora preso $ a $ che verifica $ kn^a < nt \leq kn^{a+1} $ abbiamo che $ nt-r >kn^a $ infatti se $ kn^a< nt $ allora $ kn^a \leq nt-n < nt-r $ poichè $ 0<r<n $. Quindi abbiamo che:

$ kn^a < nt-r < nt\leq kn^{a+1} $
$ n^{a-1} <\frac {nt-r}{kn} < \frac tk \leq n^a $
$ a-1< log_n \frac {nt-r}{nk} < log_n \frac tk \leq a $

e quindi $ \lceil log_n \frac {nt-r}{nk} \rceil = \lceil log_n \frac tk \rceil = a $ come volevamo dimostare. A questo punto abbiamo che:

$ \displaystyle \sum_{k=1,n \nmid k} ^{nt-r-1} \lceil log_n (\frac {nt-r}k ) \rceil =\sum_{k=1, n\nmid k} ^{nt-r-1} 1 + \sum_{k=1,n \nmid k} ^{nt-r-1} \lceil log_n (\frac {nt-r}{nk} ) \rceil= $
$ =\displaystyle \sum_{k=1, n\nmid k} ^{nt-r-1} 1 + \sum_{k=1,n \nmid k} ^{nt-r-1} \lceil log_n (\frac tk )\rceil $

Per le osservazioni del post precedente abbiamo che la prima sommatoria è uguale a $ nt-r-1 - (t-1) $ e la seconda sommatoria è $ t-1 $ quindi in totale la sommatoria è uguale a $ nt-r-1 $, come volevasi dimostrare.

Questo è quanto! Alla proxima

P.S.: nice exercise!!!