Quy nạp III

Hôm nay chúng ta giải tiếp một vài bài toán bằng phương pháp quy nạp.


Bài toán 7. Để ý rằng $$\cos 2 \alpha = 2 \cos^2 \alpha - 1$$
Chứng minh rằng có thể viết $\cos n\alpha$ thành một đa thức của biến $\cos \alpha$.



Lời giải. Chúng ta chứng minh mệnh đề sau bằng quy nạp

Với mọi số tự nhiên $n$, tồn tại một đa thức $P_n$ sao cho $\cos n\alpha = P_n(\cos \alpha)$.

Với $n=0$, chúng ta có $$cos 0 = 1$$
do đó chúng ta có thể chọn đa thức $P_0(x) = 1$ và mệnh đề đúng với trường hợp $n=0$.

Mệnh đề hiển nhiên đúng với trường hợp $n=1$ với đa thức $P_1(x) = x$.

Giả sử mệnh đề đúng với các trường hợp $0 \leq n \leq k$ trong đó $k \geq 1$. Chúng ta sẽ chứng minh mệnh đề cũng đúng với trường hợp $n=k+1$.

Chúng ta có $$\cos (k+1)\alpha + \cos (k-1)\alpha = 2 \cos k\alpha \cos \alpha$$
Do đó $$\cos (k+1)\alpha = 2 \cos k\alpha \cos \alpha - \cos (k-1)\alpha$$

Vì $0 \leq k-1 < k$, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k-1$, cho nên sẽ tồn tại một đa thức $P_{k-1}(x)$ để $$\cos (k-1)\alpha = P_{k-1}(\cos \alpha)$$

Cũng theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, do đó sẽ tồn tại một đa thức $P_{k}(x)$ để $$\cos k\alpha = P_{k}(\cos \alpha)$$

Từ đó suy ra $$\cos (k+1)\alpha = 2 P_{k}(\cos \alpha) \cos \alpha - P_{k-1}(\cos \alpha)$$

Do đó nếu chúng ta chọn đa thức $$P_{k+1}(x) = 2 P_{k}(x) x - P_{k-1}(x)$$ thì $\cos (k+1)\alpha = P_{k+1}(\cos \alpha)$. Như vậy thì mệnh đề đúng cho trường hợp $n=k+1$.

Theo nguyên lý quy nạp thì mệnh đề đúng với mọi $n$. $\blacksquare$



Theo lời giải trên, chúng ta có $P_0(x) = 1$, $P_1(x) = x$ và $$P_{k+1}(x) = 2 P_{k}(x) x - P_{k-1}(x)$$
Từ đó chúng ta có thể tính được
$$P_{2}(x) = 2 P_{1}(x) x - P_{0}(x) = 2 x^2 - 1$$
$$P_{3}(x) = 2 P_{2}(x) x - P_{1}(x) = 2(2 x^2 - 1)x - x = 4 x^3 - 3x$$
$$P_{4}(x) = 2 P_{3}(x) x - P_{2}(x) = 2(4 x^3 - 3x)x - (2 x^2 - 1) = 8 x^4 - 8x^2 + 1$$
$$P_{5}(x) = 2 P_{4}(x) x - P_{3}(x) = 2(8 x^4 - 8x^2 + 1)x - (4 x^3 - 3x) = 16 x^5 - 20x^3 + 5x$$
Có nghĩa là
$$\cos 2 \alpha = 2 \cos^2 \alpha - 1$$
$$\cos 3 \alpha = 4 \cos^3 \alpha - 3 \cos \alpha$$
$$\cos 4 \alpha = 8 \cos^4 \alpha - 8\cos^2 \alpha + 1$$
$$\cos 5 \alpha = 16 \cos^5 \alpha - 20 \cos^3 \alpha + 5 \cos \alpha$$




Bài toán 8. Với dãy số Fibonacci $$F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, \dots$$
Tìm tất cả các số $n$ để $F_n> n^2$.

Lời giải. Chúng ta có
$$F_0=0 = 0^2, F_1=1 = 1^2, F_2=1 < 2^2, F_3=2 < 3^2, F_4=3 < 4^2,$$
$$F_5=5 < 5^2, F_6=8 < 6^2, F_7 = 13 < 7^2, F_8 = 21 < 8^2, F_9 = 34 < 9^2,$$
$$F_{10} = 55 < 10^2, F_{11} = 89 < 11^2, F_{12} = 144 = 12^2, F_{13} = 233 > 13^2, F_{14} = 377 > 14^2$$

Chúng ta sẽ chứng minh bằng quy nạp mệnh đề sau

Với mọi số tự nhiên $n \geq 13$, $F_n> n^2$.

Theo tính toán ở trên $$F_{13} = 233 > 13^2 = 169, F_{14} = 377 > 14^2 = 196$$
do đó mệnh đề đúng với trường hợp $n = 13$ và $n=14$.


Giả sử mệnh đề đúng với các trường hợp $13 \leq n \leq k$ trong đó $k \geq 14$. Chúng ta sẽ chứng minh mệnh đề cũng đúng với trường hợp $n=k+1$.

Vì $13 \leq k-1 < k$, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k-1$, do đó $$F_{k-1}> (k-1)^2$$

Cũng theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, do đó $$F_{k}> k^2$$

Từ đó suy ra $$F_{k+1} = F_{k-1} + F_k > (k-1)^2 + k^2 = (k+1)^2 + (k^2 - 4k)$$

Bởi vì $k \geq 14$, cho nên $k^2 - 4k > 0$, do đó $F_{k+1} > (k+1)^2$. Như vậy mệnh đề đúng cho trường hợp $n=k+1$.

Theo nguyên lý quy nạp thì mệnh đề đúng với mọi $n \geq 13$. Vậy $F_n> n^2$ khi và chỉ khi $n \geq 13$. $\blacksquare$




Bài toán 9. Cho $n$ số khác nhau $x_1, x_2, \dots, x_n$. Còn $y_1, y_2, \dots, y_n$ là $n$ số bất kỳ. Chứng minh rằng tồn tại một đa thức $P(x)$ sao cho $$P(x_1) = y_1, P(x_2) = y_2, \dots, P(x_n) = y_n$$

Lời giải. Chúng ta sẽ chứng minh bằng quy nạp mệnh đề sau

Tồn tại đa thức $P_n(x)$ thoã mãn $$P_n(x_1) = y_1, P_n(x_2) = y_2, \dots, P_n(x_n) = y_n$$

Với trường hợp $n=1$, chúng ta chỉ cần chọn đa thức hằng số $P_1(x) = y_1$ thì chúng ta sẽ có $P_1(x_1) = y_1$. Vậy mệnh đề đúng cho trường hợp $n=1$.

Giả sử mệnh đề đúng với các trường hợp $1 \leq n \leq k$. Chúng ta sẽ chứng minh mệnh đề cũng đúng với trường hợp $n=k+1$.

Thực vậy, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, do đó sẽ tồn tại một đa thức $P_{k}(x)$ thõa mãn $$P_k(x_1) = y_1, P_k(x_2) = y_2, \dots, P_k(x_k) = y_k$$

Nếu chúng ta chọn $$P_{k+1}(x) = P_k(x) + a (x-x_1)(x-x_2) \dots (x-x_k)$$
thì rõ ràng $$P_{k+1}(x_1) = P_k(x_1) = y_1, P_{k+1}(x_2) = P_k(x_2) = y_2, \dots, P_{k+1}(x_k) = P_k(x_k) = y_k$$

Chúng ta chỉ cần xác định giá trị của $a$ sao cho $P_{k+1}(x_{k+1}) = y_{k+1}$.

Chúng ta có $$P_{k+1}(x_{k+1}) = P_k(x_{k+1}) + a (x_{k+1} - x_1)(x_{k+1} - x_2) \dots (x_{k+1} - x_k)$$
Vậy để $P_{k+1}(x_{k+1}) = y_{k+1}$ thì $$a = \frac{y_{k+1} - P_k(x_{k+1})}{(x_{k+1} - x_1)(x_{k+1} - x_2) \dots (x_{k+1} - x_k)}$$

Như vậy chúng ta đã chứng minh mệnh đề đúng cho trường hợp $n=k+1$.

Theo nguyên lý quy nạp thì mệnh đề đúng với mọi $n$. $\blacksquare$



Lời giải bài toán 9 cho phép chúng ta tìm đa thức $P(x)$ để $P(1) = 2$, $P(2) = 3$, $P(3) = 5$, $P(4) = 7$ như sau

• Đầu tiên, chọn $P_1(x) = 2$ thì $P_1(1) = 2$.

• Tiếp theo, chọn $P_2(x) = 2 + a(x-1)$ thì $P_2(1) = 2$ và $P_2(2) = 2 + a$. 
• Chọn $a = 1$, chúng ta có $P_2(2) = 3$. Vậy $P_2(x) = 2 + (x-1)$.

• Chọn $P_3(x) = 2 + (x-1) + a(x-1)(x-2)$ thì $P_3(1) = 2$, $P_3(2) = 3$ và $P_3(3) = 4 + 2a$.
• Chọn $a = \frac{1}{2}$, chúng ta có $P_3(3) = 5$. Vậy $P_3(x) = 2 + (x-1) + \frac{1}{2}(x-1)(x-2)$.

• Chọn $P_4(x) = 2 + (x-1) + \frac{1}{2}(x-1)(x-2) + a(x-1)(x-2)(x-3)$ thì $P_4(1) = 2$, $P_4(2) = 3$, $P_4(3) = 5$ và $P_4(4) = 8 + 6a$. 
• Chọn $a = - \frac{1}{6}$, chúng ta có $P_4(4) = 7$. 

Tóm lại đa thức cần tìm là $$P_4(x) = 2 + (x-1) + \frac{1}{2}(x-1)(x-2) - \frac{1}{6} (x-1)(x-2)(x-3)$$



Xin 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 $n$ là số lẻ thì tồn tại một đa thức $Q_n$ sao cho $\sin n\alpha = Q_n(\sin \alpha)$. 
• nếu $n$ là số chẵn thì tồn tại một đa thức $R_n$ sao cho $\sin n\alpha = \cos \alpha R_n(\sin \alpha)$. 

2. Tính $\sin \frac{\pi}{5}$ và $\cos \frac{\pi}{5}$.

3. Cho dãy số xác định như sau: $a_0 = 3$, $a_1 = -1$, $a_2=9$,
$$a_{n+1} = 4 a_{n-1} + 4 a_{n-2} - a_n,$$
chứng minh rằng nếu $n$ là số lẻ thì $a_n = -1$.


4. Trên mặt phẳng, cho $n$ đường thẳng với hai tính chất sau

• hai đường thẳng bất kỳ thì không song song với nhau
• ba đường thẳng bất kỳ thì không cắt nhau tại cùng một điểm

Chứng minh rằng $n$ đường thẳng này cắt nhau tạo thành $n(n-1)/2$ điểm.

5. Tìm lời giải khác cho bài toán 9.