Biểu diễn $x^k$

Đề bài:
Cho $k$ là 1 số nguyên dương. Chứng minh rằng tồn tại các số nguyên dương $a_0;a_1;\ldots;a_{k-1}$ sao cho với mọi số nguyên dương $x$ ta có: $\displaystyle x^k=a_0\left(\begin{array}{l}x\\k\end{array}\right)+a_1\left(\begin{array}{l}x+1\\\quad k\end{array}\right)+\ldots+a_{k-1}\left(\begin{array}{l}x+k-1\\\quad\quad k\end{array}\right)$.
Quy ước: $\displaystyle \left(\begin{array}{l}n\\k\end{array}\right)=0$ nếu $k>n\ge0$

Lời giải:
Với $k,x$ là các số nguyên dương, ta xét $A$ là tập hợp các tập hợp có dạng $\displaystyle\left\{m_1+\frac{1}{k};m_2+\frac{2}{k};\ldots;m_k+\frac{k}{k}\right\}$, trong đó $m_i\in\mathbb{Z}\cap[1;x]$.
Dễ thấy $|A|=x^k$.
Ta sẽ đếm số phần tử của $A$ theo cách khác.
Với mỗi tập hợp thuộc $A$ ta sắp xếp các phần tử theo thứ tự tăng dần: $\displaystyle n_1+\frac{p_1}{k}<n_2+\frac{p_2}{k}<\ldots<n_k+\frac{p_k}{k}$.
Với mỗi hoán vị $p=(p_1;p_2;\ldots;p_k)$ của $(1;2;\ldots;k)$ ta xét tập hợp $A_p\subset A$ chứa tất cả các tập hợp sau khi sắp xếp các phần tử theo thứ tự tăng dần ta nhận được hoán vị $p$ ở tử số.
Ta sẽ chứng minh: $|A_p|=\left(\begin{array}{l}x+r_p\\\quad k\end{array}\right)$ với $r_p$ phụ thuộc vào $p,k$, và không phụ thuộc vào $x$.
Với bộ số $n_i$ thỏa mãn $1\le n_1\le n_2\le\ldots\le n_k\le x$ và $n_i<n_{i+1}$ khi $p_i<p_{i+1}$ sẽ xác định 1 phần tử của $A_p$.
Xét các số nguyên không âm $e_1;e_2;\ldots;e_n$ thỏa mãn:
                $e_1=0$
                $e_{i+1}=\left\{\begin{array}{l}e_1+1&;p_i<p_{i+1}\\e_1&;p_i>p_{i+1}\end{array}\right.$
Khi đó ta có: $1\le n_1+e_1<n_2+e_2<\ldots<n_k+e_k\le x+e_k$
Dẫn tới: $\{n_1+e_1;n_2+e_2;\ldots;n_k+e_k\}$ là tập con $k$ phần tử của tập $\{1;2;\ldots;x+e_k\}$, suy ra: $|A_p|=\left(\begin{array}{l}x+r_p\\\quad k\end{array}\right)$, với $r_p=e_k$.
Dễ thấy $r_p$ không phụ thuộc vào $x$ và $0\le r_p\le k-1$.
Gọi $a_i$ là số hoán vị $p$ có $r_p=i$, ta có:
               $\displaystyle x^k=|A|=\sum_{p}|A_p|=\sum_{i=0}^{k-1}a_i\left(\begin{array}{l}x+i\\\quad k\end{array}\right)$
Ta sẽ chứng minh $a_i>0$ bằng cách chỉ ra với mỗi $i$, tồn tại một hoán vị $p$ có $r_p=i$. Thật vậy, ta có thể chọn hoán vị: $p=(n;n-1;\ldots;i+1;1;2;\ldots;i)$ thỏa mãn $r_p=i$