Giải toán bằng phương pháp quy nạp

Giải toán bằng phương pháp quy nạp

Hôm nay chúng ta sẽ học về phép quy nạp toán học. Thông thường, chúng ta sẽ dùng quy nạp để chứng minh một phát biểu nào đó đúng với mọi số tự nhiên.


Để tiện cho việc diễn đạt, chúng ta sẽ gọi $P(n)$ là một phát biểu nào đó liên quan đến biến số tự nhiên $n$. Chứng minh bằng quy nạp sẽ gồm các bước sau.

Bước 1: gọi là bước khởi điểm. Chúng ta sẽ chứng minh $P(n)$ đúng cho trường hợp đầu tiên là $n=0$.

Bước 2: gọi là bước quy nạp. Bước này là bước quan trọng nhất. Ở bước này,
chúng ta giả sử rằng $P(n)$ đúng cho các trường hợp $0 \leq n \leq k$,
với giả thiết đó, chúng ta sẽ chứng minh $P(n)$ cũng đúng với trường hợp $n=k+1$. Từ hai bước này, theo nguyên lý quy nạp toán học, chúng ta sẽ kết luận rằng $P(n)$ sẽ đúng với mọi số tự nhiên $n$.

Bây giờ chúng ta sẽ dùng quy nạp để giải bài toán đầu tiên.

Bài toán 1. Chứng minh rằng $1 + 3 + 5 + 7 + \dots + (2n+1) = (n+1)^2.$

Lời giải. Chúng ta sẽ chứng minh bằng quy nạp theo biến số $n$ công thức sau
$1 + 3 + 5 + 7 + \dots + (2n+1) = (n+1)^2.$

Bước 1. Với $n=0$, chúng ta có $1 = (0+1)^2$
Như vậy công thức ở trên đúng cho trường hợp $n=0$.

Bước 2. Giả sử công thức đúng cho các trường hợp $0 \leq n \leq k$. Chúng ta sẽ chứng minh rằng công thức trên cũng đúng cho trường hợp $n=k+1$, có nghĩa là chúng ta sẽ chứng minh $1 + 3 + 5 + 7 + \dots + (2k+1) + (2k+3) = (k+2)^2.$

Thực vậy, theo giả thiết quy nạp thì công thức đúng cho trường hợp $n=k$, cho nên $1 + 3 + 5 + 7 + \dots + (2k+1) = (k+1)^2.$

Do đó, $1 + 3 + 5 + 7 + \dots + (2k+1) + (2k+3) = (k+1)^2 + (2k+3) = k^2 + 4k + 4 = (k+2)^2.$

Như vậy chúng ta đã chứng minh rằng công thức đúng cho trường hợp $n=k+1$.
Theo nguyên lý quy nạp toán học thì công thức phải đúng với mọi số tự nhiên $n$. $\blacksquare$

Như vậy chúng ta đã biết cách chứng minh bằng quy nap.

Muốn chứng minh $P(n)$ đúng với mọi số tự nhiên $n$, chúng ta chứng minh $P(0)$ đúng
chúng ta chứng minh rằng nếu $P(0), P(1), \dots, P(k)$ đúng thì $P(k+1)$ cũng đúng.Bước chứng minh quy nạp (bước thứ 2) là bước quan trọng nhất bởi vì nhờ nó chúng ta có:
vì $P(0)$ đúng nên $P(1)$ đúng
vì $P(0), P(1)$ đúng nên $P(2)$ đúng
vì $P(0), P(1), P(2)$ đúng nên $P(3)$ đúng
vì $P(0), P(1), P(2), P(3)$ đúng nên $P(4)$ đúng
v.v...tóm lại với $n$ là số bất kỳ thì nhờ quy nạp chúng ta cũng sẽ chứng minh được $P(n)$ là đúng.

Bây giờ chúng ta tiếp tục giải tiếp một vài bài toán cho quen với phương pháp chứng minh quy nạp.

Bài toán 2. Chứng minh rằng với mọi số tự nhiên $n$, luôn tồn tại hai số nguyên $x$ và $y$ sao cho $x^2 - 2012 y^2 = 13^n .$

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

Tồn tại hai số nguyên $x$ và $y$ để cho $x^2 - 2012 y^2 = 13^n$.

Với $n=0$, chúng ta có $13^0 = 1 = 1^2 - 2012 \times 0^2 .$
Như vậy mệnh đề trên đúng cho trường hợp $n=0$.

Giả sử rằng mệnh đề trên đúng với các trường hợp $0 \leq n \leq k$. Chúng ta sẽ chứng minh mệnh đề cũng đúng cho trường hợp $n=k+1$, tức là, chúng ta sẽ chứng minh rằng tồn tại hai số nguyên $x$ và $y$ để cho $x^2 - 2012 y^2 = 13^{k+1} .$

Thực vậy, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, tức là chúng ta có thể tìm được hai số nguyên $a$ và $b$ sao cho $a^2 - 2012 b^2 = 13^k$
Mặt khác, chúng ta lại có $45^2 - 2012 \times 1^2 = 13$
Do đó dùng hằng đẳng thức $(u^2 - d v^2)(s^2 - d t^2) = (us + d vt)^2 - d (ut + vs)^2$ chúng ta suy ra $13^{k+1} = (a^2 - 2012 b^2)(45^2 - 2012 \times 1^2) = (45 a + 2012 b)^2 - 2012 (a + 45 b)^2.$
Như vậy chúng ta đã chứng minh được mệnh đề đúng cho trường hợp $n=k+1$.

Theo nguyên lý quy nạp toán học, chúng ta kết luận rằng, với mọi số tự nhiên $n$ thì sẽ tồn tại $x$ và $y$ để $13^n = x^2 - 2012 y^2$. $\blacksquare$

Ở bài toán sau đây thì bước khởi điểm là $n=5$ chứ không phải là $n=0$.

Bài toán 3. Chứng minh rằng với mọi $n \geq 5$, chúng ta có bất đẳng thức $2^n > n^2$.

Lời giải. Chúng ta sẽ chứng minh bất đẳng thức $2^n > n^2$ bằng quy nạp theo $n$.

Với $n =5$, chúng ta có $2^5 = 32 > 5^2 = 25$
Do đó bất đẳng thức đúng cho trường hợp $n=5$.

Giả sử rằng bất đẳng thức đúng cho các trường hợp $5 \leq n \leq k$. Chúng ta sẽ chứng minh bất đẳng thức đúng cho trường hợp $n=k+1$.

Thực vậy, theo giả thiết quy nạp thì bất đẳng thức đúng cho trường hợp $n=k$, nên chúng ta có $2^k > k^2.$
Do đó $2^{k+1} = 2 \times 2^k > 2k^2 = (k+1)^2 + (k-1)^2 -2 .$
Vì $k \geq 5$ nên $(k-1)^2 -2 > 0$, do đó $2^{k+1} > (k+1)^2.$
Vậy bất đẳng thức đúng cho trường hợp $n=k+1$. Theo nguyên lý quy nạp thì bất đẳng thức $2^n > n^2$ đúng với mọi số tự nhiên $n \geq 5$. $\blacksquare$

Bài tập.
1. Chứng minh rằng $1!1 + 2!2 + 3!3 + \dots + n!n = (n+1)! - 1 .$
2. Chứng minh rằng với mọi số tự nhiên $n$, luôn tồn tại hai số nguyên $x$ và $y$ sao cho $x^2 + y^2 = 5^n .$
3. Chứng minh rằng $\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{n^2} \leq 2 - \frac{1}{n}.$

Bài toán 4. Chứng minh rằng $1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$

Lời giải. Chúng ta sẽ chứng minh bằng quy nạp rằng với mọi $n \geq 1$ thì $1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$

Với $n=1$, chúng ta có $1 \times 2 \times 3= 6 = \frac{1}{4} 1 \times 2 \times 3 \times 4$
Như vậy công thức ở trên đúng cho trường hợp $n=1$.

Giả sử công thức trên đúng cho các trường hợp $1 \leq n \leq k$. Chúng ta sẽ chứng minh rằng công thức cũng đúng cho trường hợp $n=k+1$, có nghĩa là chúng ta sẽ chứng minh $1 \times 2 \times 3 + \dots + k (k+1)(k+2) + (k+1)(k+2)(k+3) = \frac{1}{4} (k+1)(k+2)(k+3)(k+4).$
Thực vậy, theo giả thiết quy nạp thì công thức đúng cho trường hợp $n=k$, cho nên $1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + k (k+1)(k+2) = \frac{1}{4} k(k+1)(k+2)(k+3).$
Do đó $1 \times 2 \times 3 + \dots + k (k+1)(k+2) + (k+1)(k+2)(k+3) $ $= \frac{1}{4} k(k+1)(k+2)(k+3) + (k+1)(k+2)(k+3)$ $= \frac{1}{4} (k+1)(k+2)(k+3)(k+4).$
Như vậy chúng ta đã chứng minh rằng công thức đúng cho trường hợp $n=k+1$.
Theo nguyên lý quy nạp toán học thì công thức phải đúng với mọi số tự nhiên $n \geq 1$. $\blacksquare$

Bài toán 5. Chứng minh rằng $49 ~\mid~ 8^n + 42 n - 1.$

Lời giải. Chúng ta sẽ chứng minh bằng quy nạp mệnh đề sau đây $8^n + 42 n - 1 = 0 \pmod{49}$

Với $n=0$, chúng ta có $8^0 + 42 \times 0 - 1 = 0$
Do đó mệnh đề trên đúng cho trường hợp $n=0$.

Giả sử rằng mệnh đề đúng cho các trường hợp $0 \leq n \leq k$. Chúng ta sẽ chứng minh mệnh đề cũng đúng cho trường hợp $n=k+1$, có nghĩa là chúng ta sẽ chứng minh $8^{k+1} + 42 (k+1) - 1 = 8^{k+1} + 42 k + 41 = 0 \pmod{49}.$

Thực vậy, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, cho nên $8^k + 42 k - 1 = 0 \pmod{49} .$
Vì vậy, $8(8^k + 42 k - 1) = 8^{k+1} + 336 k - 8 = 0 \pmod{49} .$
Do đó $8^{k+1} + 42 k + 41 = (8^{k+1} + 336 k - 8) - 49(6k - 1) = 0 \pmod{49} .$
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 toán học thì mệnh đề phải đúng với mọi số tự nhiên $n$. $\blacksquare$

Chúng ta thấy rằng ở các bài toán mà chúng ta đã giải ở trên, ở bước quy nạp, để chứng minh $P(k+1)$ đúng, chúng ta chỉ sử dụng giả thiết là $P(k)$ đúng. Như vậy chúng ta chưa cần dùng đến giả thiết là $P(0)$, $P(1)$, ..., $P(k-1)$ đúng.

Trong bài toán tiếp theo đây, để chứng minh $P(k+1)$ đúng, chúng ta cần sử dụng hai giả thiết là $P(k-1)$ đúng và $P(k)$ đúng.

Bài toán 6. Dãy số Fibonacci được xác định như sau: $F_0 = 0$, $F_1 = 1$, $F_{n+1} = F_n + F_{n-1}$. Do đó
$F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, \dots$

Chứng minh rằng công thức cho số Fibonacci là như sau
$F_n = \dfrac{1}{\sqrt{5}} \left[ \left( \dfrac{1 + \sqrt{5}}{2} \right)^n - \left( \dfrac{1 - \sqrt{5}}{2} \right)^n \right]$

Lời giải. Để cho ngắn gọn, chúng ta sẽ đặt $\alpha = \dfrac{1 + \sqrt{5}}{2}, ~~ \beta = \dfrac{1 - \sqrt{5}}{2}.$

Chúng ta sẽ chứng minh bằng quy nạp mệnh đề sau $F_n = \frac{1}{\sqrt{5}} ( \alpha^n - \beta^n ) $

Với $n=0$, chúng ta có $\frac{1}{\sqrt{5}} ( \alpha^0 - \beta^0 ) = 0 = F_0$
Do đó mệnh đề trên đúng cho trường hợp $n=0$.

Với $n=1$, chúng ta có $\frac{1}{\sqrt{5}} ( \alpha^1 - \beta^1 ) = \frac{1}{\sqrt{5}} \sqrt{5} = 1 = F_1$
Do đó mệnh đề trên đúng cho trường hợp $n=1$.

Giả sử rằng mệnh đề đúng cho 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 cho trường hợp $n=k+1$, có nghĩa là chúng ta sẽ chứng minh $F_{k+1} = \frac{1}{\sqrt{5}} ( \alpha^{k+1} - \beta^{k+1} ) $
Thực vậy, vì $0 \leq k-1 \leq k$, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k-1$, cho nên $F_{k-1} = \frac{1}{\sqrt{5}} ( \alpha^{k-1} - \beta^{k-1} ) $

Cũng theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, cho nên $F_{k} = \frac{1}{\sqrt{5}} ( \alpha^{k} - \beta^{k} ) $
Từ đó suy ra $F_{k+1} = F_{k-1} + F_k = \frac{1}{\sqrt{5}} [ (\alpha^{k-1} + \alpha^{k}) - (\beta^{k-1} + \beta^{k})] $ $= \frac{1}{\sqrt{5}} [ \alpha^{k-1} (1 + \alpha) - \beta^{k-1} ( 1 + \beta)] $

Chúng ta thấy rằng $\alpha$ và $\beta$ là hai nghiệm của phương trình $1+x=x^2$, do đó $1+\alpha=\alpha^2$ và $1+\beta=\beta^2$. Từ đó suy ra $F_{k+1} = \frac{1}{\sqrt{5}} ( \alpha^{k-1} \alpha^2 - \beta^{k-1} \beta^2 ) = \frac{1}{\sqrt{5}} ( \alpha^{k+1} - \beta^{k+1} )$
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 toán học thì mệnh đề phải đúng với mọi số tự nhiên $n$. $\blacksquare$

Ở bài toán số 6, để chứng minh $P(k+1)$ đúng, chúng ta cần sử dụng hai giả thiết là $P(k-1)$ đúng và $P(k)$ đúng. Vì vậy mà ở bước khởi điểm, chúng ta phải chứng minh rằng $P(0)$ đúng và $P(1)$ đúng. Từ đó, nhờ bước quy nạp chúng ta có:
vì P(0),P(1) đúng nên P(2) đúng
vì P(0),P(1), P(2) đúng nên P(3) đúng
vì P(0),P(1), P(2), P(3) đúng nên P(4) đúng
v.v...từ đó, suy ra $P(n)$ đúng với mọi $n$.

Chứng minh $1 > 2$
Bây giờ chúng ta sẽ dùng quy nạp để chứng minh rằng $1 > 2$. Đố các bạn chỉ ra cách chứng minh này sai ở điểm nào.
Cho dãy số xác định như sau: $a_0 = 1$, $a_1 = 1$, $a_{n+1} = a_{n-1} + a_n + 11$.
Chúng ta sẽ chứng minh bằng quy nạp mệnh đề sau đây
Với mọi $n$, thì $a_n > 4 n - 2$
Với $n=0$, chúng ta có $a_0 = 1 > 4 \times 0 - 2 = -2$
Do đó mệnh đề trên đúng cho trường hợp $n=0$.
Giả sử rằng mệnh đề đúng cho các trường hợp $0 \leq n \leq k$. Chúng ta sẽ chứng minh mệnh đề cũng đúng cho trường hợp $n=k+1$, có nghĩa là chúng ta sẽ chứng minh
$a_{k+1} > 4(k+1) - 2 = 4k + 2$
Thực vậy, theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k-1$, cho nên
$a_{k-1} > 4(k-1) - 2 = 4k - 6$
Cũng theo giả thiết quy nạp thì mệnh đề đúng cho trường hợp $n=k$, cho nên
$a_{k} > 4k - 2$
Từ đó suy ra
$a_{k+1} = a_{k-1} + a_k + 11 > (4k - 6) + (4k - 2) + 11 = 8k + 3 > 4k + 2 $

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 toán học thì mệnh đề phải đúng với mọi số tự nhiên $n$.
Vậy chúng ta chứng minh xong bất đẳng thức
$a_n > 4 n - 2$
Thay $n=1$ vào bất đẳng thức trên chúng ta có
$1 > 2$

Vậy lời giải trên sai ở đâu?!

Bài tập

1. Tìm công thức tổng quát cho $1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$
2. Chứng minh rằng $25 ~\mid~ 6^n - 5n - 1$

Tìm công thức tổng quát cho bài toán này.
3. 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 > 3n$.

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 = \dfrac{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)$

Bài tập

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ểmChứng minh rằng $n$ đường thẳng này cắt nhau tạo thành $dfrac{n(n-1)}{2}$ điểm.




Theo WWW.VNMATH.COM