Bài toán ( Putnam 2007 ) Cho k là một số nguyên dương . Chứng minh rằng tồn tại các đa thức $P_{0}(n),P_{1}(n),...,P_{k-1}(n)$ ( phụ thuộc k ) sao cho với mọi số nghuyên n
$\left \lfloor \frac{n}{k} \right \rfloor^{k}=P_{0}(n)+P_{1}(n)\left \lfloor \frac{n}{k} \right \rfloor+...+P_{k-1}(n)\left \lfloor \frac{n}{k} \right \rfloor^{k-1}$, trong đó $\left \lfloor x \right \rfloor$ dùng để chỉ số nguyên lớn nhất không vượt quá x.
Lời giải. Mấu chốt của chứng minh nằm ở nhận xét sau :
Với mọi số nguyên n , Tồn tại một số $j\in \left \{ 0,1,...,k-1 \right \}$ sao cho $\left \lfloor \frac{n}{k} \right \rfloor=\frac{n-j}{k}$.
Thật vậy , theo thuật toán chia với mọi số nguyên n , ta đều có thể viết $n=qk+j$ , trong đó $j\in \left \{ 0,...,k-1 \right \}$ nên$q\leq \frac{n}{k}=q+\frac{j}{k}< q+1\Rightarrow \left \lfloor \frac{n}{k} \right \rfloor=q=\frac{n-j}{k}$
Từ nhận xét trên ta thấy
$\prod_{j=0}^{k-1}\left ( \left \lfloor \frac{n}{k} \right \rfloor -\frac{n-j}{k}\right )=0$
Đến đây khai triển tích trên ta có ngay điều phải chứng minh