Nhân tiện nói về sự tuần hoàn của các số dư, tôi xin kể cho các bạn một chuyện thế này:
Ngày trước, tôi được dạy về phương pháp quy nạp toán học như thế này: Để chứng minh mệnh đề $f(n)$ nào đó đúng với mọi số nguyên $n$ từ $n_{min}$ nào đó trở đi. Đầu tiên ta xác nhận rằng $f(n_{min})$ đúng. Sau đó giả sử $f(n)$ đúng, suy ra được $f(n+1)$ đúng! Vậy là xong!
Nguyên lý thật đơn giản! $f(n)\Rightarrow f(n+1)$ rồi $f(n+1)\Rightarrow f(n+2)$, v.v...
Tôi tự hỏi rằng có nhất thiết phải từ $f(n)$ đúng rồi suy ra $f(n+1)$ đúng mới là đúng quy tắc, đúng phương pháp quy nạp hay không?
Giả sử có trường hợp $f(n)$ đúng, nhưng tôi không thể suy ra được $f(n+1)$ đúng thì phải làm thế nào? Hay phương pháp quy nạp là không thể sử dụng được?
Giả sử từ $f(n)$ đúng, tôi chỉ suy ra được $f(n+3)$ đúng, nhưng tôi kiểm tra thấy $f(0), f(1), f(2)$ đều đúng? Vậy $f(n)$ đã được chứng minh bằng quy nạp hay chưa?
Câu trả lời: Đó chính là ĐPCM!
Thậy vậy:
$f(0)\Rightarrow f(3)\Rightarrow f(6)\Rightarrow ...\Rightarrow f(3k)$
$f(1)\Rightarrow f(4)\Rightarrow f(7)\Rightarrow ...\Rightarrow f(3k+1)$
$f(2)\Rightarrow f(5)\Rightarrow f(8)\Rightarrow ...\Rightarrow f(3k+2)$
Chúng ta cùng xem xét ví dụ sau:
Chứng minh rằng: Với $n$ không âm, $m$ nguyên dương ta có:
$$\sum_{k=0}^n \left\lfloor\frac{k}{m}\right\rfloor=\left(n+1-\frac{m}{2}\right)\left\lfloor\frac{n}{m}\right\rfloor-\frac{m}{2}\left\lfloor\frac{n}{m}\right\rfloor^2\quad(1)$$
Bài này nếu dùng nguyên tắc quy nạp thông thường thì đúng là không được rồi! Còn để chứng minh trực tiếp (tìm hiểu xem công thức ở đâu mà ra) thì cũng tốn không ít chất xám đâu! Thế nhưng nếu áp dụng phương pháp quy nạp "kiểu đồng dư" thì không thành vấn đề:
- Dễ thấy với $0\le n\le m-1$ thì $VT = VP=0$
- Giả sử $(1)$ đúng với $n$, ta chứng minh rằng $(1)$ cũng đúng với $n+m$
$\sum_{k=0}^{n+m} \left\lfloor\frac{k}{m}\right\rfloor=\sum_{k=0}^n \left\lfloor\frac{k}{m}\right\rfloor+\sum_{k=n+1}^{n+m}\left\lfloor\frac{k}{m}\right\rfloor=\sum_{k=0}^n \left\lfloor\frac{k}{m}\right\rfloor+\sum_{k=0}^{m-1}\left\lfloor\frac{n+1+k}{m}\right\rfloor$
$=\left(n+1-\frac{m}{2}\right)\left\lfloor\frac{n}{m}\right\rfloor-\frac{m}{2}\left\lfloor\frac{n}{m}\right\rfloor^2+n+1\quad$ (Theo giả thiết quy nạp và định lý Hermite)
Mặt khác, khi thay $n$ bởi $n+m$ ở VP của $(1)$, ta được:
$\left(n+1-\frac{m}{2}+m\right)\left(\left\lfloor\frac{n}{m}\right\rfloor+1\right)-\frac{m}{2}\left(\left\lfloor\frac{n}{m}\right\rfloor+1\right)^2$
$=\left(n+1-\frac{m}{2}\right)\left\lfloor\frac{n}{m}\right\rfloor+m\left\lfloor\frac{n}{m}\right\rfloor+n+1+\frac{m}{2}-\frac{m}{2}\left\lfloor\frac{n}{m}\right\rfloor^2-m\left\lfloor\frac{n}{m}\right\rfloor-\frac{m}{2}$
$=\left(n+1-\frac{m}{2}\right)\left\lfloor\frac{n}{m}\right\rfloor-\frac{m}{2}\left\lfloor\frac{n}{m}\right\rfloor^2+n+1$
Từ đó ta có ĐPCM