Ho postato questo problema prendendo spunto da un recente Topic di Simo the wolf...viva l'originalità
Sia definita la seguente funzione $ \forall n\in \mathbb{N}\displaystyle $,:
$ \displaystyle \tau(n)=\sum_{i=1}^{n}{mcm(n,i)} $
dove mcm(x,y) è il minimo comune multiplo tra x e y.
Dimostrare che, posto $ n=p^k $, con $ p $ primo e $ k $ intero positivo, allora:
$ \displaystyle \tau(n)=\frac{p^{3k+1}+p^{k+1}+2p^{k}}{2p+2}\displaystyle $
mcm e funzioni aritmetiche
Se $ k = 1 $, la tesi è banale, ché $ \displaystyle \tau(p) := \sum_{i=1}^p \mbox{mcm}(i,p) = \sum_{i=1}^{p-1} ip + p = $ $ \displaystyle\frac{p^2(p-1)}{2}+p=\left(\frac{p^{3k+1}+p^{k+1}+2p^k}{2(p+1)}\right)_{k=1} $. Assumendone quindi la consistenza per un generico $ k\in\mathbb{N}_0 $, osserviamo che: $ \displaystyle \tau(p^{k+1}) := \sum_{i=1}^{p^{k+1}} \mbox{mcm}(i,p^{k+1}) = $ $ \displaystyle\sum_{t=0}^{p^k-1} \sum_{i=1}^{p-1} \mbox{mcm}(pt + i,p^{k+1}) $ $ \displaystyle + \sum_{i=1}^{p^k} \mbox{mcm}(pi, p^{k+1}) = $ $ \displaystyle p^{k+1}\cdot \sum_{t=0}^{p^k-1} \sum_{i=1}^{p-1} (pt + i) + p \cdot \tau(p^k) $. Di qui, per l'ipotesi di induzione: $ \displaystyle \tau(p^{k+1}) = p^{k+1}\cdot p(p-1)\cdot \frac{(p^k-1)p^k}{2} + $ $ \displaystyle p^{2k+1}\cdot \frac{p(p-1)}{2} + p \cdot \frac{p^{3k+1} + p^{k+1} + 2p^k}{2(p+1)} = $ $ \displaystyle p^{3k+1}\cdot \frac{p(p-1)}{2} + \frac{p^{3k+2} + p^{k+2} + 2p^{k+1}}{2(p+1)} $ $ = \displaystyle\frac{p^{3(k+1) + 1} + p^{(k+1)+1} + 2p^{k+1}}{2(p+1)} $. Ne seguita l'asserto, q.e.d.
Scrivo anche la mia sol che non utilizza l'induzione... Ragiono su un generico p^k... osserviamo che (k,p^k) =k*p^k se p non divide k.... Quindi inizio con il sommare:
p^k * Si= p^2k(p^k+1)/2
Così però abbiamo aumentato l'mcm reale dei numeri che dividono p... Per eliminare quest'eccesso seguiamo questo algoritmo: contiamo i multipli di p e li dividiamo ognuno per p. Per ogni numero la differenza tra tra il numero orignario e quello dopo la divisione rappresenta un eccesso di p^k contati nella sommatoria iniziale (si provi con k=2 e p=3 e si capisce perchè funzia). Si esegue lo stesso per i multipli di p che si sono ottenuti (che prima della divisione erano multipli di p^2) e così via, fino a p^k. Matematicamente, togliamo:
(p-1)/2*p^k * p^(k-1)*(p^(k-1)+1)+
(p-1)/2*p^k * p^(k-2)*(p^(k-2)+1)+
...
(p-1)/2*p^k * p^(0)*(p^(0)+1)
esprimendo il tutto come sommatoria:
(p-1)/2*p^k *S[p^(i-1)*(p^(i-1)+1)]
che riconosciute le dovute serie geometriche
(p-1)/2*p^k*[(p^2k-1)/(p^2-1)+(p^k-1)/(p-1)]
questo è il fattore da togliere alla somma fatta inizialmente. Eseguendo la differenza sbuca fuori, dopo svariati errori di calcolo, proprio la formula di Igor... dato che ho saltato vari passaggi, se qualcosa non è chiaro, chiedete pure, eh!
p^k * Si= p^2k(p^k+1)/2
Così però abbiamo aumentato l'mcm reale dei numeri che dividono p... Per eliminare quest'eccesso seguiamo questo algoritmo: contiamo i multipli di p e li dividiamo ognuno per p. Per ogni numero la differenza tra tra il numero orignario e quello dopo la divisione rappresenta un eccesso di p^k contati nella sommatoria iniziale (si provi con k=2 e p=3 e si capisce perchè funzia). Si esegue lo stesso per i multipli di p che si sono ottenuti (che prima della divisione erano multipli di p^2) e così via, fino a p^k. Matematicamente, togliamo:
(p-1)/2*p^k * p^(k-1)*(p^(k-1)+1)+
(p-1)/2*p^k * p^(k-2)*(p^(k-2)+1)+
...
(p-1)/2*p^k * p^(0)*(p^(0)+1)
esprimendo il tutto come sommatoria:
(p-1)/2*p^k *S[p^(i-1)*(p^(i-1)+1)]
che riconosciute le dovute serie geometriche
(p-1)/2*p^k*[(p^2k-1)/(p^2-1)+(p^k-1)/(p-1)]
questo è il fattore da togliere alla somma fatta inizialmente. Eseguendo la differenza sbuca fuori, dopo svariati errori di calcolo, proprio la formula di Igor... dato che ho saltato vari passaggi, se qualcosa non è chiaro, chiedete pure, eh!