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!