Замечательное тождество из ТЧ

[Whitaker]

Здравствуйте уважаемые друзья!
Нашел такую задачку, но решить ее я не могу уже несколько дней. Признаюсь никаких идей нет у меня и нуждаюсь в Вашей помощи. Доказать, что:

$$\tau(1)+\tau(2)+\cdots+\tau(n)=\Big[\dfrac{n}{1}\Big]+\Big[\dfrac{n}{2}\Big]+\cdots+\Big[\dfrac{n}{n}\Big],$$

где $\tau(k)$ - число всех натуральных делителей числа $k$.

С уважением, Whitaker.

[nnosipov]

Подсчитайте двумя способами количество целых точек под гиперболой $xy=n$ ($x>0$, $y>0$).

[venco]

Whitaker, сколько всего раз у чисел от $1$ до $n$ встречается делитель $1$?
А делитель $3$?

[arseniiv]

Да, красивая формула.

[Whitaker]

nnosipov признаюсь я сначала подумал, что это тождество доказывается путем подсчета целых точек в некоторой области. А откуда здесь берется функция $\tau(k)$?

venco
Среди чисел $1, 2, \dots, n$ делитель $1$ встречается $n$ раз, а делитель $3$ встречается только $\Big[\dfrac{n}{3}\Big]+\Big[\dfrac{n}{3^2}\Big]+\Big[\dfrac{n}{3^3}\Big]+\cdots;$ Здесь на самом деле конечная сумма. На каком-то шаге все последующие члены становятся нулями.

[venco]

Whitaker в сообщении #539437 писал(а):

venco
Среди чисел $1, 2, \dots, n$ делитель $1$ встречается $n$ раз, а делитель $3$ встречается только $\Big[\dfrac{n}{3}\Big]+\Big[\dfrac{n}{3^2}\Big]+\Big[\dfrac{n}{3^3}\Big]+\cdots;$.

Неправильно. Ну или вы не так поняли вопрос. Например, у числа 9 есть 3 делителя - 1, 3 и 9. Делитель 3 встречается один раз.

-- Чт фев 16, 2012 10:35:57 --

Whitaker в сообщении #539437 писал(а):

venco
Среди чисел $1, 2, \dots, n$ делитель $1$ встречается $n$ раз, а делитель $3$ встречается только $\Big[\dfrac{n}{3}\Big]+\Big[\dfrac{n}{3^2}\Big]+\Big[\dfrac{n}{3^3}\Big]+\cdots;$

Кстати вы сами себе противоречите. Если так воспринимать вопрос, то делитель 1 должен встречаться $\Big[\dfrac{n}{1}\Big]+\Big[\dfrac{n}{1^2}\Big]+\Big[\dfrac{n}{1^3}\Big]+\cdots$ раз.

[Dave]

$$\sum_{m=1}^n {\tau(m)}=\sum_{m=1}^n \; {\sum_{(p,q) \mid p \in \mathbb N, q \in \mathbb N, pq=m} 1}=\sum_{m=1}^n \; {\sum_{(p,q) \mid p \in \mathbb N, p \leqslant n, q \in \mathbb N, pq=m} 1}=$$

$$=\sum_{p=1}^n \; {\sum_{(m,q) \mid m \in \mathbb N, m \leqslant n, q \in \mathbb N, pq=m} 1}=\sum_{p=1}^n {\sum_{q \mid q \in \mathbb N, pq \leqslant n} 1}=\sum_{p=1}^n {\sum_{q \mid q \in \mathbb N, q \leqslant \frac n p} 1}=\sum_{p=1}^n {\left[ \frac n p \right]}.$$

[Whitaker]

venco
Делитель $3$ в $1, 2, \dots, n$ встречается ровно $\Big[\dfrac{n}{3}\Big]$

[venco]

Whitaker в сообщении #539453 писал(а):

Делитель $3$ в $1, 2, \dots, n$ встречается ровно $\Big[\dfrac{n}{3}\Big]$

Ну теперь-то уж до требуемой формулы рукой подать.

[Whitaker]

Ну теперь уж намного понятнее, чем раньше!
venco большое спасибо Вам за помощь