mcm e funzioni aritmetiche

[Igor]

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 $

[HiTLeuLeR]

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.

[HiTLeuLeR]

Per inciso, si osservi che la tesi resta valida pure per $ k = 0 $.

[info]

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!

[Igor]

Molto buone entrambe le soluzioni.Io ho seguito un ragionamento simile a quello di
info, anche perchè, non conoscendo a priori la formula, non potevo dimostrarla per
induzione.