Το άθροισμα του Euler

Tolaso J Kos · #1

Έστω $\varphi$ η συνάρτηση φι του Euler. Να δειχθεί ότι:

$\displaystyle{\sum_{k=1}^{\infty} \varphi(k) \left \lfloor \frac{n}{k} \right \rfloor = \frac{n \left ( n+1 \right )}{2}}$

#2

Θέτουμε $\displaystyle f(n) = \sum_{k=1}^{\infty} \varphi(k) \left \lfloor \frac{n}{k} \right \rfloor.$ Προφανώς f(1) = 1

. Επίσης

$\displaystyle f(n) - f(n-1) = \sum_{k=1}^{\infty} \varphi(k) \left(\left \lfloor \frac{n}{k} \right \rfloor - \left \lfloor \frac{n-1}{k} \right \rfloor \right) = \sum_{k|n} \varphi(k)$

Η τελευταία ισότητα ισχύει αφού το $\displaystyle \left \lfloor \frac{n}{k} \right \rfloor - \left \lfloor \frac{n-1}{k} \right \rfloor$ ισούται με

αν

και

αν $k \nmid n$ .

Αρκεί να δείξουμε ότι $\displaystyle \sum_{k=1}^{n} \varphi(k) = n$ αφού τότε το ζητούμενο προκύπτει εύκολα επαγωγικά.

Αν $m \in \{1,2,\ldots,n\}$ τότε προφανώς $\gcd(n,m)=d$ για κάποιο d|n

. Για

έστω

το σύνολο όλων των $m \in \{1,2,\ldots,n\}$ ώστε $\gcd(n,m)=k$ . Κάθε στοιχείο του A_d

είναι της μορφής

με $\gcd(r,n/d)=1$ . Επομένως $|A_d| = \varphi(n/d)$ .

Άρα έχουμε $\displaystyle \sum_{k=1}^{n} = \sum_{k|n} \varphi(k) = \sum_{d|n} \varphi(n/d) = \sum_{d|n} |A_d| = n$

όπως θέλαμε να δείξουμε.

Tolaso J Kos · #3

Μία άλλη λύση....

$\displaystyle{\begin{aligned} \sum_{k=1}^{\infty} \varphi(k) \left \lfloor \frac{n}{k} \right \rfloor &= \sum_{k=1}^{\infty} \varphi(k) \sum_{\substack{m \leq n \\ k \mid n}} 1 \\ &= \sum_{k=1}^{\infty} \sum_{\substack{m \leq n \\ k \mid n}} \varphi(k) \\ &= \sum_{m=1}^{n} \sum_{k \mid m} \varphi(k) \\ &= \sum_{m=1}^{n} m \\ &= \frac{n \left ( n+1 \right )}{2} \end{aligned}}$

Το άθροισμα του Euler

Το άθροισμα του Euler

Re: Το άθροισμα του Euler

Re: Το άθροισμα του Euler

Μέλη σε σύνδεση