Tài liệu Phương pháp quy nạp cho bài toán chia hết

Người Thầy MỖI NGÀY MỘT TẦM CAO MỚI Một phương pháp giải bài toán chia hết . Khi gặp bài toán chứng minh F (n) .. A với n ∈ N ta vẫn thường sử dụng phương pháp quy nạp. Cụ thể các bước của phương pháp quy nạp là . 1. F (1) .. A . . 2. Giả sử F (n) .. A ta chứng minh F (n + 1) .. A. . . . Nhưng để ý rằng: Nếu a .. c thì b .. c ⇔ a − b .. c Vậy ta có thể xem nó là một dạng khác của phương pháp quy nạp. Tức . là để chứng minh F (n).. A ta qua các bước . 1. F (1) .. A . 2. F (n + 1) − F (n) .. A Sau đây ta xét một số bài toán áp dụng phương pháp trên. Bài 1. Chứng minh rằng với mọi số tự nhiên n, n ≥ 1 thì F (n) = 16n − 15n − 1 chia hết cho 225. Giải . Ta có ngay F (1) = 0 .. 225. . . Giả sử F (n) .. 225 ta chứng minh F (n + 1) − F (n) .. 225. Thật vây F (n + 1) − F (n) = 15.16n − 15 = 15(16n − 1) . . Vì 16n − 1 .. 15 nên ta có F (n + 1) − F (n) .. 225 (đpcm). Bài 2. Chứng minh rằng với mọi số tự nhiên n, n ≥ 1 thì G(n) = 32n+3 + 40n − 27 chia hết cho 64. [email protected] 1 05/05/2014 Người Thầy MỖI NGÀY MỘT TẦM CAO MỚI Giải . Ta có ngay G(1) = 256 .. 64. . . Giả sử G(n) .. 64 ta chứng minh G(n + 1) − G(n) .. 64. Thật vây G(n + 1) − G(n) == 8.32n+3 + 40 = 8(32n+3 + 5) Suy ra . . G(n + 1) − G(n) .. 64 ⇔ F (n) = 32n+3 + 5 .. 8, ∀n ≥ 1, n ∈ N . Ta có F (1) = 248 .. 8. . . Giả sử F (n) .. 8 ta chứng minh F (n + 1) − F (n) .. 8. Thật vậy . F (n + 1) − F (n) = 8.32n+3 .. 8 . Do đó, ta có G(n + 1) − G(n) .. 64. (đpcm). Bài 3. Chứng minh rằng với mọi số tự nhiên n, n ≥ 1 ta có 1. 10n + 18n − 1 chia hết cho 27; 2. 22n+1 + 1 chia hết cho 3; 3. 10n − 4n + 3n chia hết cho 9; 4. 4n + 15n − 1 chia hết cho 9; Giải 1. Đặt F (n) = 10n + 18n − 1. . Ta có F (1) = 27 .. 27. Xét F (n + 1) − F (n) = 9.10n + 18 = 9(10n + 2). Nhận xét rằng . . F (n + 1) − F (n) .. 27 ⇔ G(n) = 10n + 2 .. 3. . . Có G(1) = 12 .. 3 và G(n + 1) − G(n) = 9.10n .. 3 . Dó đó, ta có F (n + 1) − F (n) .. 27 (đpcm). [email protected] 2 05/05/2014 Người Thầy MỖI NGÀY MỘT TẦM CAO MỚI 2. Đặt H(n) = 22n+1 + 1. Ta có ngay . H(n + 1) − H(n) = 3.22n+1 .. 3 (đpcm). 3. Đặt F (n) = 10n − 4n + 3n. Ta có F (n + 1) − F (n) = 9.10n − 3.4n + 3 = 3(3.10n − 4n + 1) Suy ra . . F (n + 1) − F (n) .. 9 ⇔ G(n) = 3.10n − 4n + 1 .. 3 Thật vậy, ta có . G(n + 1) − G(n) = 27.10n − 3.4n ..3 Suy ra điều phải chứng minh. 4. Đặt F (n) = 4n + 15n − 1. Ta có F (n + 1) − F (n) = 3.4n + 15 = 3(4n + 15) Suy ra . . F (n + 1) − F (n) .. 9 ⇔ G(n) = 4n + 15 .. 3 Thật vậy, ta có . G(n + 1) − G(n) = 3.4n .. 3 Suy ra điều phải chứng minh. [email protected] 3 05/05/2014