Sum of Divisor Functions

Number theory 3 Minutes

Bổ đề. Với mỗi số nguyên dương n , ta có

\displaystyle \sum_{k=1}^n \tau(k) = \sum_{k=1}^n \left[ \frac{n}{k} \right]

và

\displaystyle \sum_{k=1}^n \sigma(k) = \sum_{k=1}^n k \cdot \left[ \frac{n}{k} \right].

Chứng minh. Xét đẳng thức thứ nhất. Theo định nghĩa, \tau(k) là số lượng các ước số dương của k , nên ta có thể viết \tau(k) = \sum_{d|k} 1 . Thay biểu thức này vào vế trái, ta được:

\displaystyle \sum_{k=1}^n \tau(k) = \sum_{k=1}^n \sum_{d|k} 1.

Thay vì tính tổng theo k trước, ta sẽ đổi thứ tự lấy tổng bằng cách cố định số nguyên dương d \in \{1, 2, \dots, n\} . Ta cần đếm xem d là ước của bao nhiêu số nguyên dương k không vượt quá n .

Các số k nhận d làm ước chính là các bội số của d , bao gồm: d, 2d, 3d, \dots, md . Vì k \le n nên ta phải có md \le n , tương đương với m \le \frac{n}{d} . Số lượng các bội số thỏa mãn điều kiện này chính là phần nguyên của \frac{n}{d} , ký hiệu là \left[ \frac{n}{d} \right] .

Vì mỗi bội số k đóng góp 1 đơn vị vào tổng chung tương ứng với ước d , ta có:

\displaystyle \sum_{k=1}^n \tau(k) = \sum_{d=1}^n \sum_{\substack{k=1 \\ d|k}}^n 1 = \sum_{d=1}^n \left[ \frac{n}{d} \right].

Chỉ cần đổi tên biến chạy d thành k , ta thu được đẳng thức thứ nhất.

Hoàn toàn tương tự đối với đẳng thức thứ hai. Nhớ lại định nghĩa hàm tổng các ước \sigma(k) = \sum_{d|k} d , ta viết lại vế trái:

\displaystyle \sum_{k=1}^n \sigma(k) = \sum_{k=1}^n \sum_{d|k} d .

Lại tiến hành đổi thứ tự lấy tổng, ta cố định ước d \in \{1, 2, \dots, n\} . Mỗi khi k là một bội số của d (và k \le n ), số d sẽ xuất hiện một lần trong biểu thức của \sigma(k) .

Như đã lập luận ở phần trước, trong đoạn từ 1 đến n có đúng \left[ \frac{n}{d} \right] bội số của d . Mỗi lần xuất hiện, ước này đóng góp một giá trị bằng d vào tổng chung. Do đó, tổng giá trị đóng góp của riêng số d đối với toàn bộ hệ thống là d \cdot \left[ \frac{n}{d} \right] .

Lấy tổng tất cả các đóng góp này khi d chạy từ 1 đến n , ta nhận được

\displaystyle \sum_{k=1}^n \sigma(k) = \sum_{d=1}^n d \cdot \left[ \frac{n}{d} \right].

Một lần nữa, thay đổi tên biến chạy d thành k , ta lập tức có được đẳng thức thứ hai. \Box

Unknown's avatar

Published by Nguyen Trung-Tuan

A math teacher.

Published

Leave a comment