Quy Nạp II - Vườn Toán

Trang chủ » Công Thức Quy Nạp » Quy Nạp II - Vườn Toán

Có thể bạn quan tâm

Trang

  • Trang nhà
  • Kỹ năng mềm
  • Giới thiệu

Quy nạp II

Hôm nay chúng ta tiếp tục giải tiếp một số bài toán bằng phương pháp quy nạp. 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 = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right]$$ Lời giải. Để cho ngắn gọn, chúng ta sẽ đặt $$\alpha = \frac{1 + \sqrt{5}}{2}, ~~ \beta = \frac{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?! Hẹn các bạn ở kỳ sau, chúng ta sẽ giải thêm một vài bài toán khác bằng phương pháp quy nạp. Bài tập về nhà 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$. Labels: algebra, đại số, Fibonacci, induction, number theory, quy nạp, số học Bài đăng Mới hơn Bài đăng Cũ hơn Trang chủ

Ủng hộ Vườn Toán trên facebook

Facebook

Lưu trữ Blog

  • ▼  2012 (36)
    • ▼  tháng 9 (6)
      • 1 = 2012 = 2013
      • Nhị thức Newton
      • Quy nạp III
      • Quy nạp II
      • Quy nạp
      • Tam giác Pascal

English Version

English Version

Bài toán kết nối facebook

Phép nhân thời đồ đá

Mắt Biếc Hồ Thu

Lục giác kỳ diệu

Định lý Pitago

1 = 2012 = 2013

Dãy số Fibonacci và một bài toán xếp hình

James vẽ hình

Câu hỏi của James

Hình vuông số chính phương kỳ diệu của Vianney!

Câu đố mẹo về đo lường

Công thức lượng giác Gauss cho 17-giác đều

Chào năm mới 2014

Chào năm mới 2015

Chào năm mới 2016

Không gian 4 chiều là gì?

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Ngày số Pi (2015)

Ngày số Pi (2016)

0.9999999... có bằng 1 không? (2015)

Hình tam giác

Bàn cờ vua và kim tự tháp

Dãy số

Dãy số - Phần 1

Dãy số - Phần 2

Dãy số - Phần 3

Dãy số - Phần 4

Dãy số - Phần 5

Dãy số - Phần 6

Dãy số - Phần 7

Dãy số - Phần 8

Dãy số - Phần 9

Đại số

Tam giác Pascal

Quy nạp

Quy nạp II

Quy nạp III

Nhị thức Newton

1 = 2012 = 2013

Đa thức nội suy Newton

Đa thức nội suy Lagrange

Chứng minh Định lý Wilson bằng công thức nội suy

Tổng luỹ thừa

Số phức

Số phức

Công thức Moivre

Lượng giác

Công thức lượng giác cho góc bội

Công thức lượng giác Gauss cho 17-giác đều

Ngày số Pi (2016)

Radian là gì?

Số học

modulo - Phần 1

modulo - Phần 2

modulo - Phần 3

modulo - Phần 4

modulo - Phần 5

modulo - Phần 6

Số nguyên tố

Định lý Euclid về số nguyên tố

Một vài bài toán về số nguyên tố

Định lý Wilson

Bộ số Pitago

Modulo cho số hữu tỷ

Modulo cho số hữu tỷ II

Chứng minh lại định lý Wilson

Bổ đề Bezout

Thuật toán Euclid

Tổng luỹ thừa

Tổng luỹ thừa và định lý Wolstenholme

Câu đố mẹo về đo lường

Dựng đa giác đều 15 cạnh

Bò đi con bọ cạp!

Liên phân số Fibonacci

Hằng đẳng thức Pitago

Hình vuông số kỳ diệu của Euler

Tổ hợp

Bài toán kết nối facebook

Dãy số Fibonacci và một bài toán xếp hình

Hằng đẳng thức về dãy số Fibonacci

Dãy số Fibonacci và tam giác Pascal

Hình học

Định lý Pitago

Định lý đường cao tam giác vuông

Định lý Morley

Phương tích

Trục đẳng phương và tâm đẳng phương

Định lý Ceva và Định lý Menelaus

Lục giác kỳ diệu

Định lý Pascal

Định lý Pappus

Cánh bướm Pascal

Bài toán con bướm

Định lý Ngôi Sao Do Thái

Hãy xem xét trường hợp đặc biệt

Bài toán về tìm khoảng cách ngắn nhất và một tính chất của hình elíp

Điểm Fermat của hình tam giác

Điểm Fermat của hình tam giác II

Dựng hình

Dựng hình bằng thước và compa

Bài toán chia hình tứ giác

Dựng hình ngũ giác đều

Dựng hình đa giác đều

Dựng đa giác đều 15 cạnh

Định lý đường cao tam giác vuông

Thuật toán dựng hình

Công thức lượng giác Gauss cho 17-giác đều

Dựng hình chỉ bằng compa

Dùng compa chia đều đoạn thẳng

Giải tích

Ngày số Pi 2015

Chuỗi Taylor

Tổng nghịch đảo bình phương

Giúp bé thông minh

Xì-tin năng động

BBC - Học tiếng Anh Du học Hoa kỳ Học Bổng Hoa Kỳ VOA - Học tiếng Anh

Tạp chí toán học

Kỹ năng mềm

Tạo lập tài khoản google

Cách tạo blog toán học

Học toán trên Wolfram

Dịch tài liệu toán học

Viết văn bản toán học PDF trực tuyến bằng LaTeX

Chia xẻ tài liệu toán học trên Google Drive

Từ khóa » Công Thức Quy Nạp