Lagrange interpolating polynomial

Đây là bài thứ bốn về đa thức của tôi, các bạn học sinh nên xem lại ba bài trước để học cho dễ dàng hơn.

—

Đa thức có thể được sử dụng để xấp xỉ các đường cong phức tạp, hay tính giá trị của các hàm logarit và lượng giác. Đầu tiên, chọn một vài dữ liệu đã biết, sau đó tìm một đa thức có bậc đủ bé có cùng dữ liệu đã chọn, cuối cùng xem đa thức vừa tìm được như là hàm số đang xét. Điều này dẫn đến việc tính toán nhanh hơn đáng kể.

Định lí. Cho số nguyên dương $n$ và $n+1$ số phức đôi một khác nhau $x_0,$ $x_1,$ $\ldots,$ $x_{n}.$ Khi đó với mỗi $n+1$ số phức $y_0,$ $y_1,$ $\ldots,$ $y_n,$ có đúng một đa thức $P(x)$ với hệ số phức có bậc không lớn hơn $n$ sao cho

$P(x_i)=y_i,\quad \forall i=\overline{0,n}.$

Chứng minh. Nếu $P$ và $Q$ là các đa thức thỏa mãn các điều kiện của định lí thì đa thức $P-Q$ có bậc không lớn hơn $n$ và có ít nhất $n+1$ nghiệm, suy ra $P-Q$ là đa thức không và $P=Q.$ Mặt khác, đa thức $\displaystyle P(x)=\sum_{i=0}^ny_i\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}$ thỏa mãn $P(x_i)=y_i,\quad \forall i=\overline{0,n},$ do đó định lí được chứng minh. $\Box$

Hệ quả (Công thức nội suy Lagrange). Cho số nguyên dương $n$ và đa thức $P(x)$ với hệ số phức có bậc không lớn hơn $n.$ Khi đó với mỗi $n+1$ số phức đôi một khác nhau $x_0,$ $x_1,$ $\ldots,$ $x_{n},$ ta có

$\displaystyle P(x)=\sum_{i=0}^nP(x_i)\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}.$

Trong công thức trên, $n+1$ số phức $x_0,$ $x_1,$ $\ldots,$ $x_{n}$ được gọi là các nút nội suy. Ta thường dùng công thức nội suy Lagrange trong tình huống: Biết thông tin của $P$ tại các $x_i$ , cần tìm thông tin của $P$ tại $y\not\in \{x_i\}.$

Ví dụ 1. Cho hai đa thức $A(x)=x^{81}+x^{49}+x^{25}+x^9+x$ và $B(x)=x^3-x.$ Tìm dư khi chia $A(x)$ cho $B(x).$

Lời giải. Giả sử $Q(x)$ và $R(x)$ lần lượt là thương và dư trong phép chia $A(x)$ cho $B(x).$ Ta có $A(x)=B(x)Q(x)+R(x)$ và $\deg R<3.$ Vì $B(0)=B(1)=B(-1)=0$ nên $R(0)=0,$ $R(1)=5$ và $R(-1)=-5,$ do đó áp dụng công thức nội suy Lagrange cho $R$ với các nút $0;1$ và $-1$ ta có

$\displaystyle R(x)=R(0).\frac{(x-1)(x+1)}{(0-1)(0+1)}+R(1).\frac{(x-0)(x+1)}{(1-0)(1+1)}+R(-1).\frac{(x-0)(x-1)}{(-1-0)(-1-1)}$

$\displaystyle =\frac{5}{2}x(x+1)-\frac{5}{2}x(x-1)=5x.$ $\Box$

Ví dụ 2. Cho số nguyên dương $n$ và đa thức $P$ có bậc $n$ thỏa mãn $\displaystyle P(k)=\frac{k}{k+1},\quad \forall k=\overline{0,n}.$ Tính $P(n+1).$

Lời giải. Do $P$ có bậc $n$ nên áp dụng công thức nội suy Lagrange cho $P$ với $n+1$ nút $0,$ $1,$ $\ldots,$ $n$ ta có $\displaystyle P(x)=\sum_{k=0}^nP(k)\prod_{j\not =k}\frac{x-j}{k-j}$

$\displaystyle =\sum_{k=0}^n\frac{k}{k+1}\prod_{j\not =k}\frac{x-j}{k-j}=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}\prod_{j\not =k}(x-j),\quad\forall x\in\mathbb{R}.$ Suy ra

$\displaystyle P(n+1)=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}\prod_{j\not =k}(n+1-j)$

$\displaystyle =\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}.\frac{(n+1)!}{n+1-k}$

$\displaystyle =\frac{1}{n+2}\sum_{k=0}^nk(-1)^{n-k}C^{k+1}_{n+2}=\frac{1}{n+2}\sum_{k=0}^n\left[(k+1)(-1)^{n-k}C_{n+2}^{k+1}+(-1)^{n-k+1}C_{n+2}^{k+1}\right]$

$\displaystyle =\frac{1}{n+2}\left(\sum_{k=0}^n(-1)^{n-k}(n+2)C_{n+1}^k+\sum_{i=1}^{n+1}(-1)^{n+2-i}C_{n+2}^i\right)=\dfrac{n+1+(-1)^{n+1}}{n+2}. \Box$

Ví dụ 3. Cho số nguyên dương $n$ và các số nguyên $x_0 > x_1 > \ldots > x_n.$ Chứng minh rằng một trong các số $|F(x_0)|,$ $|F(x_1)|,$ $|F(x_2)|,$ $\ldots,$ $|F(x_n)|$ lớn hơn hoặc bằng $\displaystyle \frac{n!}{2^n}.$ Trong đó

$F(x) = x^n + a_1x^{n-1} + \cdots+ a_n$

là một đa thức với hệ số thực.

Lời giải. Giả sử $\displaystyle |F(x_i)|<\dfrac{n!}{2^n},\quad \forall i=\overline{0,n}.$ Áp dụng công thức nội suy Lagrange cho $P$ với $n+1$ nút $x_0,$ $x_1,$ $\cdots,$ $x_n$ ta có

$\displaystyle x^n + a_1x^{n-1} + \cdots+ a_n\equiv \sum_{k=0}^nF(x_k)\prod_{j\not =k}\frac{x-x_j}{x_k-x_j},$ để ý đến hệ số của $x^n$ trong hai vế ta có $\displaystyle 1=\left|\sum_{k=0}^n\prod_{j\not =k}\frac{F(x_k)}{x_k-x_j}\right|\leq \sum_{k=0}^n\prod_{j\not =k}\frac{|F(x_k)|}{|x_k-x_j|}<$ $\displaystyle \sum_{k=0}^n\prod_{j\not =k}\frac{\frac{n!}{2^n}}{|x_k-x_j|}\leq \sum_{k=0}^n\prod_{j\not =k}\frac{\frac{n!}{2^n}}{|k-j|}=1,$ không thể xảy ra điều này. $\Box$

Ví dụ 4. Chứng minh rằng với mỗi số thực $a$ và với mỗi số nguyên dương $n$ ta có

$\displaystyle \sum_{k = 0}^n( - 1)^k\binom{n}{k}(a - k)^n = n!.$

Lời giải. Vế trái là đa thức của $a$ nên chỉ cần chứng minh đẳng thức khi $a$ là số nguyên. Sau đây ta chứng minh đẳng thức khi $a= 0$ và $n\geq 3$ , hay chứng minh

$\displaystyle \sum_{k = 0}^n( - 1)^{n + k}\binom{n}{k}k^n = n!.$ Theo công thức nội suy Lagrange với các nút $1,$ $2,$ $\ldots,$ $n$ ta có $\displaystyle x^n - (x - 1)(x - 2)\cdots (x - n) \equiv \sum_{k = 1}^nk^n\cdot\prod_{i\not = k}\dfrac{x - i}{k - i},\quad\forall x\in\mathbb{R}.$ Nói riêng, khi $x = 0$ ta có $\displaystyle ( - 1)^{n + 1}\cdot n! = \sum_{k = 1}^nk^n\cdot \dfrac{1}{k}\cdot \dfrac{( - 1)^{n - 1}\cdot n!}{(k - 1)!\cdot (n - k)!\cdot ( - 1)^{n - k}},$ từ đây thu được điều cần chứng minh. $\Box$ .

Continue reading →

A proof of Cauchy–Davenport theorem

Trong bài này tôi sẽ giới thiệu một chứng minh của định lí Cauchy-Davenport.

Định lí Cauchy – Davenport. Cho số nguyên tố $p$ và hai tập con khác rỗng $A,B$ của $\mathbb{Z}/p\mathbb{Z}.$ Khi đó

$|A+B|\geq\min (p,|A|+|B|-1).$

Chứng minh. Ta chứng minh khẳng định bằng quy nạp theo $|B|$ . Khi $|B|=1$ ta có

$|A+B|=|A|=\min (p,|A|)=\min (p,|A|+|B|-1).$ Suy ra khẳng định đúng khi $|B|=1$ . Khi $|B|=2$ ta viết $B=\{b_1,b_2\}$ và $A=\{a_1,a_2,\ldots,a_m\},$ ta có ngay $|A+B|\geq m$ .

Nếu $|A+B|= m$ thì $\{b_1+a_1,\ldots,b_1+a_m\}=\{b_2+a_1,\ldots,b_2+a_m\},$ suy ra $mb_1\equiv mb_2\pmod{p}$ , hay $m=p$ . Khi đó $|A+B|=p\geq\min (p,|A|+|B|-1).$

Nếu $|A+B|>m$ thì $|A+B|\geq m+1\geq\min (p,m+1)=\min (p,|A|+|B|-1).$

Vậy khẳng định đúng khi $|B|=2$ . Giả sử khẳng định đúng với mỗi tập $B$ thỏa mãn $|B|<n,$ trong đó $n\geq 3.$ Ta sẽ chứng minh khẳng định đúng với mọi tập $B$ có $|B|=n.$ Xét một tập $B$ thỏa mãn $|B|=n$ . Đặt $|A+B|=l,|A|=m$ và viết $B=\{b_1,b_2,\ldots,b_n\}.$ Xét ba trường hợp

Trường hợp 1. $l\geq p.$

Ta có $|A+B|=l\geq p\geq\min (p,|A|+|B|-1).$

Trường hợp 2. $m+n>p.$

Ta có $A+B=\{0,1,2,\ldots,p-1\}$ , thật vậy với mỗi $g\in \{0,1,2,\ldots,p-1\}$ , hai tập $g-A$ và $B$ có giao khác rỗng vì chúng là các tập con của tập $\{0,1,2,\ldots,p-1\}$ và có tổng số phần tử lớn hơn $p$ . Lấy $h\in g-A\cap B$ ta có ngay $g=b=g-a\,\, (a\in A,b\in B),$ suy ra $g=a+b\in A+B$ . Từ đây ta có $|A+B|=p\geq\min (p,|A|+|B|-1).$

Trường hợp 3. $l<p$ và $m+n\leq p.$

Ở trường hợp này thì $\min (p,|A|+|B|-1)=\min (p,m+n-1)=m+n-1.$ Áp dụng giả thiết quy nạp cho hai tập $C=A+B$ và $\{b_1,b_n\}$ ta có $|C+\{b_1,b_n\}|\geq\min (p,|C|+|\{b_1,b_n\}|-1)=\min (p,l+1)=l+1,$ suy ra $C+b_1\not = C+b_n$ , do đó tồn tại số nguyên $x$ sao cho $x-b_1\in A+B$ và $x-b_n\not\in A+B$ . Từ đây ta thấy tồn tại số nguyên dương $r<n$ sao cho $x-b_i\in A+B,\,\forall i=\overline{1,r}$ và $x-b_i\not\in A+B,\,\forall i=\overline{r+1,n}$ . Áp dụng giả thiết quy nạp cho hai tập $A$ và $B^{\prime}=\{b_{r+1},b_{r+2},\ldots,b_n\}$ ta có

$|A+B^{\prime}|\geq \min (p,|A|+|B^{\prime}|-1)=\min (p,m+n-r-1)=m+n-r-1.$ Ta có $x-b_i\not\in A+B^{\prime},\,\forall i=\overline{1,r}$ , vì nếu chẳng hạn $x-b_1\in A+B^{\prime}$ thì

$x-b_1= a+b_{s}\Rightarrow x-b_s\in A+B,$ điều này trái với cách chọn $r$ . Vậy $|A+B|\geq r+|A+B^{\prime}|\geq r+m+n-r-1=m+n-1,$ và định lí được chứng minh. $\Box$

Bằng quy nạp ta chứng minh được kết quả sau.

Hệ quả. Cho số nguyên dương $h>1,$ số nguyên tố $p$ và $h$ tập con khác rỗng $A_1,$ $A_2,\ldots,$ $A_h$ của $\mathbb{Z}/p\mathbb{Z}.$ Khi đó $\displaystyle \mid A_1+A_2+\cdots+A_h\mid \geq \min \left(p,\sum_{i=1}^h\mid A_i\mid-h+1\right).$

Combinations

Cho một tập $A$ có $n$ phần tử ( $n\in\mathbb{N}$ ) và $0\leq k\leq n$ là một số nguyên. Một $k-$ tổ hợp (một tổ hợp chập $k$ ) của $A$ là một tập con $k$ phần tử của $A$ .

Ví dụ 1. Các $3-$ tổ hợp của $A=\{a,b,c,d\}$ là

$\{a,b,c\},\{b,c,d\},\{c,d,a\},\{d,a,b\}.$

Định lí 1. Cho một tập $A$ có $n$ phần tử ( $n\in\mathbb{N}$ ) và $0\leq k\leq n$ là một số nguyên. Khi đó số $k-$ tổ hợp của $A$ bằng $C_n^k=\dfrac{A_n^k}{k!}=\dfrac{n!}{k!(n-k)!}.$

Chứng minh. Sự khác nhau giữa một $k-$ tổ hợp và một $k-$ hoán vị chính là một đằng không quan tâm đến thứ tự, trong khi đằng kia có quan tâm đến thứ tự. Tận dụng điều này ta có chứng minh như sau.

Một $k-$ hoán vị của $A$ có thể hình thành sau hai bước: Đầu tiên, chọn một $k-$ tổ hợp của $A$ ; sau đó xếp $k$ phần tử của tập này thành một hàng. Bởi vì có $C_n^k$ cách để làm bước một, $k!$ cách để làm bước hai nên theo nguyên lý nhân ta có $A_n^k=C_n^k\times k!.$ $\Box$

Ví dụ 2. Có bao nhiêu xâu nhị phân độ dài $7$ mà có đúng ba số $0$ ?

Lời giải. Một xâu nhị phân có tính chất như trong đề bài sẽ được hình thành khi ta chọn $3$ vị trí trong $7$ vị trí để viết số $0.$ Do đó số xâu thỏa mãn là $C_7^3.$ $\Box$

Ví dụ 3. Có bao nhiêu cách có thể thành lập một hội đồng gồm $5$ thành viên từ một nhóm có $11$ người chứa $4$ giáo viên và $7$ học sinh nếu

(1) Không có thêm điều kiện gì?

(2) Hội đồng chứa đúng $2$ giáo viên?

(3) Hội đồng chứa ít nhất $3$ giáo viên?

(4) Giáo viên $A$ và học sinh $B$ không thể cùng nằm trong hội đồng?

Hướng dẫn giải. (1) $C_{11}^5$ . (2) $C_4^2\times C_7^3$ . (3) $3$ hoặc $4$ giáo viên có thể nằm trong hội đồng, đáp số $91$ .

(4) Dùng quy tắc trừ, đáp số $378$ . $\Box$

Ví dụ 4. Cho $n$ là một số nguyên dương và $A$ là một tập có $2n$ phần tử. Có bao nhiêu cách phân hoạch $A$ thành các tập có $2$ phần tử?

Lời giải 1. Đầu tiên, cố định một phần tử $x$ của $A$ và chọn một phần tử trong $2n-1$ phần tử còn lại của $A$ để ghép lại với $x$ tạo thành một khối của phân hoạch; sau đó cố định một phần tử $y$ trong các phần tử còn lại của $A$ và chọn một phần tử trong $2n-3$ phần tử còn lại của $A$ để ghép lại với $y$ tạo thành một khối của phân hoạch; ta cứ làm như vậy cho đến khi còn $2$ phần tử thì đây chính là khối còn lại của phân hoạch. Theo quy tắc nhân, số phân hoạch thoả mãn là $(2n-1)\times (2n-3)\times\cdots\times 1$ . $\Box$

Lời giải 2. Chọn một tập con có $2$ phần tử của $A$ làm khối thứ nhất, sau đó chọn một tập con có $2$ phần tử của tập hợp gồm $2n-2$ phần tử còn lại làm khối thứ hai, ta cứ làm như vậy cho đến khi còn hai phần tử thì đây chính là khối thứ $n$ . Vì thứ tự các khối là không quan trọng nên số các phân hoạch thoả mãn là $\dfrac{C_{2n}^2\times C_{2n-2}^2\times\cdots\times C_2^2}{n!}$ . $\Box$

Lời giải 3. Ta xếp $2n$ phần tử của $A$ thành một hàng vào $2n$ vị trí như hình dưới đây

$\{(1),(2)\},\{(3),(4)\},\cdots,\{(2n-1),(2n)\}$ có $(2n)!$ cách để làm điều này. Vì trong mỗi tập con có $2$ phần tử thứ tự các phần tử là không quan trọng và thứ tự các khối của phân hoạch là không quan trọng nên số phân hoạch thoả mãn là

$\dfrac{(2n)!}{2!\times 2!\times\cdots\times 2!\times n!}=\dfrac{(2n)!}{n!\times 2^n}.$ $\Box$

Continue reading →

Permutations

Cho $n$ là một số nguyên dương, $r$ là một số nguyên thoả mãn $0\leq r\leq n$ và $A$ là một tập hợp có $n$ phần tử. Một $r-$ hoán vị của $A$ (hay một chỉnh hợp chập $r$ của $A$ ) là một cách xếp $r$ phần tử nào đó của $A$ thành một hàng. Một $n-$ hoán vị của $A$ sẽ được gọi là một hoán vị của $A.$

Ví dụ 1. Cho tập $A=\{a,b,c,d\}$ . Khi đó các $3-$ hoán vị của $A$ là (có tất cả $24$ ):

$abc,acb,bac,bca,cab,cba,$

$abd,adb,bad,bda,dab,dba,$

$acd,adc,cad,cda,dac,dca,$

$bcd,bdc,cbd,cdb,dbc,dcb.$ $\Box$

Định lí 1. Cho $n$ là một số nguyên dương, $r$ là một số nguyên thoả mãn $0\leq r\leq n$ và $A$ là một tập hợp có $n$ phần tử. Khi đó số $r-$ hoán vị của $A$ bằng $A_n^r=\dfrac{n!}{(n-r)!}$ . Nói riêng, số hoán vị của $A$ bằng $P_n=n!$ .

Chứng minh. Một $r-$ hoán vị của $A$ sẽ được hình thành sau $r$ bước: Đầu tiên, chọn một phần tử từ $A$ và đặt nó vào vị trí thứ nhất; sau đó ta chọn trong các phần tử còn lại của $A$ một phần và đặt nó vào vị trí thứ hai;…; và cuối cùng ta chọn một phần tử từ $n-r+1$ phần tử còn lại của $A$ và đặt nó vào vị trí thứ $r$ . Vì có $n$ cách làm bước thứ nhất, $n-1$ cách làm bước thứ hai;…; và $n-r+1$ cách làm bước thứ $r$ nên theo quy tắc nhân, ta có $A_n^r=n(n-1)\cdots (n-r+1)=\dfrac{n!}{(n-r)!}.$ $\Box$

Ví dụ 2. Gọi $E$ là tập tất cả $26$ chữ cái tiếng Anh. Tìm số các từ gồm $5$ chữ trong $E$ sao cho chữ đầu tiên, chữ cuối cùng là các nguyên âm phân biệt và ba chữ còn lại là các phụ âm phân biệt.

Lời giải. Có $5$ nguyên âm trong $E$ đó là $a,e,i,o,u$ và $21$ chữ cái còn lại là các phụ âm. Một từ thỏa mãn yêu cầu của đầu bài sẽ được hình thành sau hai bước: Đầu tiên, chọn một $2-$ hoán vị của $\{a,e,i,o,u\}$ và đặt nguyên âm thứ nhất vào vị trí $1$ , nguyên âm thứ hai vào vị trí $5$ , sau đó chọn một $3-$ hoán vị của $E\setminus \{a,e,i,o,u\}$ và đặt phụ âm thứ nhất, hai, ba của hoán vị vào vị trí $2,3,4$ tương ứng.

Bởi vì có $A_5^2$ cách để làm bước thứ nhất và $A_{21}^3$ cách để làm bước thứ hai nên theo quy tắc nhân ta có số các từ thoả mãn là $A_5^2\times A_{21}^3=159600.$ $\Box$