Hôm trước chúng ta đã học về tam giác Pascal và cách khai triển nhị thức Newton dựa vào các hệ số trong tam giác Pascal. Nhân dịp học về quy nạp, chúng ta sẽ chứng minh bằng quy nạp
- công thức của tam giác số Pascal $$p_{n,k} = {n \choose k} = \frac{n!}{k! (n-k)!}$$
- và định lý khai triển nhị thức Newton $$(x+y)^n = x^n + {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 + \dots + {n \choose {n-2}} x^{2} y^{n-2} + {n \choose {n-1}} x y^{n-1} + y^n$$
Tam giác Pascal là một tam giác số như sau
tam giác này được xây dựng trên quy tắc mỗi số ở hàng dưới sẽ bằng tổng của hai số đứng phía trên ở hàng trên
Nếu chúng ta đánh số thứ tự bắt đầu từ số 0 như hình dưới đây
và dùng ký hiệu $p_{n,k}$ để chỉ số thứ $k$ ở hàng thứ $n$ của tam giác Pascal thì công thức xây dựng tam giác Pascal là $$p_{n-1,k-1} + p_{n-1,k} = p_{n,k}.$$
Bây giờ chúng ta sẽ chứng minh bằng quy nạp theo biến số $n$ công thức sau đây $$p_{n,k} = {n \choose k} = \frac{n!}{k! (n-k)!}$$
Với $n=0$, chúng ta có $$p_{0,0} = 1 = \frac{0!}{0!0!}$$ như vậy công thức đúng với trường hợp $n=0$. Chúng ta lưu ý rằng $0!$ bằng $1$ chứ không phải bằng $0$.
Giả sử công thức đúng với các trường hợp $0 \leq n \leq N$. Chúng ta sẽ chứng minh công thức cũng đúng với trường hợp $n=N+1$.
Thực vậy, với trường hợp $k=0$ hoặc $k=N+1$ chúng ta có $$p_{N+1,0} = p_{N+1,N+1} = 1 = \frac{(N+1)!}{0! (N+1)!} = {{N+1} \choose 0} = {{N+1} \choose {N+1}}$$
Với trường hợp $1 \leq k \leq N$, chúng ta có $$p_{N+1,k} = p_{N,k-1} + p_{N,k}$$
Theo giả thiết quy nạp thì công thức đúng với trường hợp $n=N$, cho nên $$p_{N,k-1} = {N \choose {k-1}} = \frac{N!}{(k-1)! (N-k+1)!}, \quad p_{N,k} = {N \choose k} = \frac{N!}{k! (N-k)!}$$
Từ đó suy ra $$p_{N+1,k} = p_{N,k-1} + p_{N,k} = \frac{N!}{(k-1)! (N-k+1)!} + \frac{N!}{k! (N-k)!} $$ $$= \frac{N! k}{k! (N-k+1)!} + \frac{N!(N-k+1)}{k! (N-k+1)!} $$
$$= \frac{N!(N+1)}{k! (N-k+1)!} = \frac{(N+1)!}{k! (N-k+1)!} = {{N+1} \choose k}$$
Như vậy chúng ta đã chứng minh công thức đúng cho trường hợp $n =N+1$. Tóm lại, theo nguyên lý quy nạp thì chúng ta đã chứng minh được công thức cho các hệ số trong tam giác Pascal là $$p_{n,k} = {n \choose k} = \frac{n!}{k! (n-k)!}$$
Xin nói thêm một chút về ký hiệu ${n \choose k}$. Ký hiệu này đọc là "$n$ chọn $k$", lý do là vì ${n \choose k}$ chính là số cách chọn $k$ đồ vật (không kể thứ tự) trong số $n$ đồ vật. Ví dụ, nếu chúng ta có $4$ con cá thì sẽ có đúng ${4 \choose 2} = 6$ cách chọn ra $2$ con cá.
 |
| có đúng ${4 \choose 2} = 6$ cách chọn ra $2$ con cá từ $4$ con cá |
Bây giờ chúng ta dùng quy nạp để chứng minh định lý khai triển nhị thức Newton $$(x+y)^n = x^n + {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 + \dots + {n \choose {n-2}} x^{2} y^{n-2} + {n \choose {n-1}} x y^{n-1} + y^n$$
Công thức hiển nhiên đúng cho trường hợp $n=0$ và $n=1$. Giả sử công thức đúng cho các trường hợp $0 \leq n \leq N$, trong đó $N \geq 1$. Chúng ta sẽ chứng minh công thức đúng cho trường hợp $n=N+1$.
Thực vậy,
$$(x+y)^{N+1} = (x+y) (x+y)^N $$ $$= (x+y)(x^N + p_{N,1} x^{N-1} y + p_{N,2} x^{N-2} y^2 + \dots + p_{N, N-2} x^{2} y^{N-2} + p_{N,N-1} x y^{N-1} + y^N)$$
$$= x^{N+1} + p_{N,1} x^{N} y + p_{N,2} x^{N-1} y^2 + \dots + p_{N, N-2} x^{3} y^{N-2} + p_{N,N-1} x^2 y^{N-1} + x y^N$$
$$ ~~~~ + x^N y + p_{N,1} x^{N-1} y^2 + p_{N,2} x^{N-2} y^3 + \dots + p_{N, N-2} x^{2} y^{N-1} + p_{N,N-1} x y^{N} + y^{N+1}$$
Để ý rằng theo công thức xây dựng tam giác Pascal thì $$p_{N,1} + 1 = p_{N+1,1}, p_{N,2} + p_{N,1} = p_{N+1,2}, \dots, p_{N,N-1} + p_{N, N-2} = p_{N+1, N-1}, 1 + p_{N,N-1} = p_{N+1,N},$$ do đó
$$(x+y)^{N+1} = x^{N+1} + p_{N+1,1} x^{N} y + p_{N+1,2} x^{N-1} y^2 + \dots + p_{N+1, N-1} x^{2} y^{N-1} + p_{N+1,N} x y^{N} + y^{N+1}$$
Vậy chúng ta đã chứng minh công thức đúng cho trường hợp $n=N+1$. Theo nguyên lý quy nạp thì chúng ta đã chứng minh xong định lý khai triển nhị thức Newton
$$(x+y)^n = x^n + p_{n,1} x^{n-1} y + p_{n,2} x^{n-2} y^2 + \dots + p_{n,n-2} x^{2} y^{n-2} + p_{n,n-1} x y^{n-1} + y^n$$ $$= x^n + {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 + \dots + {n \choose {n-2}} x^{2} y^{n-2} + {n \choose {n-1}} x y^{n-1} + y^n$$
Thay $y$ bằng $-y$ chúng ta có hằng đẳng thức
$$(x-y)^n = x^n - {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 - \dots + (-1)^{n-2}{n \choose {n-2}} x^{2} y^{n-2} + (-1)^{n-1}{n \choose {n-1}} x y^{n-1} + (-1)^n y^n$$
Hẹn gặp lại các bạn ở kỳ sau.
Bài tập về nhà.
1. Chứng minh rằng nếu $p$ là số nguyên tố thì ${p \choose k}$ chia hết cho $p$ với mọi $0 < k < p$. Từ đó suy ra $$(x+y)^p = x^p + y^p \pmod{p}$$
2. Chứng minh các đẳng thức sau
$$1 + {2012 \choose 1} + {2012 \choose 2} + \dots + {2012 \choose 2010} + {2012 \choose 2011} + 1 = 2^{2012}$$
$$1 + {2012 \choose 2} + {2012 \choose 4} + \dots + {2012 \choose 2010} + 1=2^{2011}$$
$${2012 \choose 1} + {2012 \choose 3} + \dots + {2012 \choose 2009} + {2012 \choose 2011} = 2^{2011}$$
3. Dùng $\Delta$ để ký hiệu phép toán sau $$\Delta p(x) = p(x+1) - p(x)$$
Áp dụng $\Delta$ một lần nữa cho biểu thức $\Delta p(x)$, chúng ta có $$\Delta^2 p(x) = \Delta (\Delta p(x)) = (p(x+2) - p(x+1)) - (p(x+1) - p(x)) = p(x+2) - 2 p(x+1) + p(x)$$
Áp dụng $\Delta$ một lần nữa, chúng ta có $$\Delta^3 p(x) = p(x+3) - 3p(x+2) + 3 p(x+1) - p(x)$$
Phát biểu và chứng minh công thức tổng quát.