induction_01Dec2015

50 Mathematical Induction 33. จงแสดงวา 2 | n(n + 1) ทกุ คา n ∈ N † 33. แนวคิด ให an = n(n + 1) เพราะฉะน้ัน a1 = 2 ให P(n) แทนขอความ “ 2 | an ลงตวั ” (1) การแสดงวา P(1) เปน จริง เพราะวา a1 = 2 เพราะฉะนนั้ 2 | a1 เพราะฉะนั้น P(1) เปน จริง (2) การแสดงวา ถา P(k) เปน จริง เม่อื k ≥ 1 แลว P(k + 1) เปนจรงิ สมมติ P(k) เปน จรงิ เม่ือ k ≥ 1 เพราะฉะน้นั 2 | ak ak+1 = (k + 1)(k + 2) = k(k + 1) + 2(k + 1) = ak + 2(k + 1) เพราะวา 2 | ak และ 2 | 2(k + 1) เพราะฉะน้ัน 2 | ak+1 เพราะฉะน้ัน P(k + 1) เปนจรงิ โดยอุปนยั เชงิ คณิตศาสตร จะได P(n) เปน จริง ทกุ คา n ∈ N เพราะฉะนน้ั 2 | n(n + 1) ทุกคา n ∈ N หมายเหตุ การใชเหตผุ ลทีง่ ายกวาน้ีคอื n(n + 1) เปนจํานวนคู เพราะฉะนน้ั 2 หาร n(n + 1) ลงตัว ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 51 † 34. จงแสดงวา 3 | n(n + 1)(n + 2) ทกุ คา n ∈ N 34. แนวคิด ให an = n(n + 1)(n + 2) เพราะฉะนนั้ a1 = 6 ให P(n) แทนขอความ “ 3 | n(n + 1)(n + 2) ” (1) การแสดงวา P(1) เปน จรงิ เพราะวา a1 = 6 เพราะฉะนั้น 3 | a1 เพราะฉะนัน้ P(1) เปน จรงิ (2) การแสดงวา ถา P(k) เปนจริง เมอ่ื k ≥ 1 แลว P(k + 1) เปน จรงิ สมมติ P(k) เปนจรงิ เม่ือ k ≥ 1 ak+1 - ak = (k + 1)(k + 2)(k + 3) - k(k + 1)(k + 2) = (k + 1)(k + 2)((k + 3) - k) = 3(k + 1)(k + 2) เพราะฉะนน้ั ak+1 = 3(k + 1)(k + 2) + ak เพราะวา (P(k) เปนจริง ⇒ 3 | ak ) และ 3 | 3(k + 1)(k + 2) เพราะฉะน้นั 3 | ak+1 เพราะฉะนัน้ P(k + 1) เปนจริง โดยอุปนัยเชงิ คณิตศาสตร จะได P(n) เปน จรงิ ทุกคา n ∈ N เพราะฉะน้ัน 3 | n(n + 1)(n + 2) ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

52 Mathematical Induction 35. จงแสดงวา 4 | n(n + 1)(n + 2)(n + 3) ทุกคา n ∈ N † 35. แนวคดิ ให an = n(n + 1)(n + 2)(n + 3) เพราะฉะน้ัน a1 = 24 ให P(n) แทนขอความ “ 4 | an ” (1) การแสดงวา P(1) เปนจรงิ เพราะวา a1 = 24 เพราะฉะนั้น 4 | a1 เพราะฉะน้นั P(1) เปนจริง (2) การแสดงวา ถา P(k) เปน จรงิ เมอ่ื k ≥ 1 แลว P(k + 1) เปนจรงิ สมมติ P(k) เปนจริง เมื่อ k ≥ 1 ak+1 - ak = (k + 1)(k + 2)(k + 3)(k + 4) - k(k + 1)(k + 2)(k + 3) = (k + 1)(k + 2)(k + 3)((k + 4) - k) = 4(k + 1)(k + 2)(k + 3) เพราะฉะน้นั ak+1 = 4(k + 1)(k + 2)(k + 3) + ak เพราะวา (P(k) เปนจริง ⇒ 4 | ak ) และ 4 | 4(k + 1)(k + 2)(k + 3) เพราะฉะนน้ั 3 | ak+1 เพราะฉะน้ัน P(k + 1) เปนจรงิ โดยอุปนัยเชงิ คณติ ศาสตร จะได P(n) เปน จรงิ ทุกคา n ∈ N เพราะฉะนนั้ 4 | n(n + 1)(n + 2)(n + 3) ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 53 36. กําหนดให m เปน จํานวนเตม็ บวก จงแสดงวา m | n(n + 1)(n + 2) ... (n + m - 1) ทุกคา n ∈ N 36. แนวคิด แบบที่ 1 ให an = n(n + 1)(n + 2) ... (n + m - 1) ให m เปนจํานวนเตม็ บวก ให P(n) แทนขอ ความ “ m | an ” (1) การแสดงวา P(1) เปน จริง a1 = (1)(1 + 1)(1 + 2) ... (1 + m + 1) = 1⋅2⋅3 ... m เพราะฉะนน้ั m | a1 เพราะฉะนั้น P(1) เปนจรงิ (2) การแสดงวา ถา P(k) เปน จรงิ เม่อื k ≥ 1 แลว P(k + 1) เปน จริง สมมติ P(k) เปนจริง เมื่อ k ≥ 1 ak+1 - ak = (k + 1)((k + 1) + 1)((k + 1) + 2) ... ((k + 1) + m - 1) - k(k + 1)(k + 2) ... (k + m - 1) = (k + 1)(k + 2)(k + 3) ... (k + m) - k(k + 1)(k + 2) ... (k + m - 1) = (k + 1)(k + 2) ... (k + m - 1)((k + m) - k) = m(k + 1)(k + 2) ... (k + m - 1) เพราะฉะนน้ั ak+1 = ak + m(k + 1)(k + 2) ... (k + m - 1) เพราะวา (P(k) เปนจริง ⇒ m | ak ) และ m | m(k + 1)(k + 2) ... (k + m - 1) เพราะฉะนัน้ m | ak+1 เพราะฉะนั้น P(k + 1) เปนจริง โดยอปุ นัยเชงิ คณิตศาสตร จะได P(n) เปนจริง ทกุ คา n ∈ N เพราะฉะนน้ั m | n(n + 1)(n + 2) ... (n - m + 1) ทกุ คา n ∈ N แบบที่ 2 เพราะวา m, m + 1, m + 2, ... , m + m - 1 เปนจํานวนเตม็ ทเ่ี รียงคา กัน n ตัว เพราะฉะน้ันมอี ยางนอยหนึ่งตัวจาก m, m + 1, m + 2, ... , m + m - 1 ท่ีหารดวย n ลงตวั เพราะฉะนัน้ n | (m(m + 1)(m + 2) ... (m + n - 1)) แบบที่ 3 สมมติ ไมม ี t ∈ { 0, 1, 2, ... , n - 1 } ทีท่ ําให n | (n + t ) ... (1) ให Ci = { x | x ≡ i (mod n) }, i = 0, 1, 2, ... , n - 1 เพราะฉะนน้ั เซตจํานวนเต็ม = C0 ∪ C1 ∪ C2 ∪ ... ∪ Cn−1 เพราะฉะนัน้ 0, 1, 2, ... , n - 1 ∈ C0 ∪ C1 ∪ C2 ∪ ... ∪ Cn−1 จาก (1) จะได 0, 1, 2, ... , n - 1 ∉ C0 เพราะฉะนน้ั 0, 1, 2, ... , n - 1 ∈ C1 ∪ C2 ∪ ... ∪ Cn−1 ให 0, 1, 2, ... , n - 1 เปนนก n ตัวและ C1 , C2 , ... , Cn−1 เปน รงั นก n - 1 รังซง่ึ นอ ยกวา จํานวนนก โดยหลกั รงั นกพิราบจะมี i, j ∈ { 0, 1, 2, ... , n - 1 } และ Ck ท่ที ําให n + i, n + j ∈ Ck โดยไมส ญู เสียสาระสําคญั ของกรณที ว่ั ไปเราสามารถสมมติให i < j เพราะวา i < j เพราะฉะนั้น 0 < j - i ... (2) เพราะฉะนัน้ n + i ≡ k (mod n) และ n + j ≡ k (mog n) เพราะฉะนน้ั (n + j ) - (n + i ) ≡ 0 (mod n) เพราะฉะนนั้ j - i ≡ 0 (mod n) เพราะฉะนั้น n| ( j - i ) ... (3) จาก (2) และ (3) จะได n ≤ j - i ... (4) เพราะวา i, j ∈ { 0, 1, 2, ... , n - 1 } และ i < j เพราะฉะน้นั 1 ≤ j - i ≤ n - 1 ... (5) เพราะฉะนั้น (4) และ (5) ขดั แยง กัน รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

54 Mathematical Induction เพราะฉะน้นั ที่สมมติ (1) ไมม ี t ∈ { 0, 1, 2, ... , n - 1 } ทท่ี ําให n | (n + t ) ไมจรงิ † เพราะฉะน้นั มี t ∈ { 0, 1, 2, ... , n - 1 } ที่ทําให n | (n + t ) เพราะฉะนน้ั n | (m(m + 1)(m + 2) ... (m + n - 1)) รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 55 † 37. จงแสดงวา 3 | ( n3 - n) ทุกคา n ∈ N 37. แนวคิด จากขอ 34 จะได 3 หารผลคูณของจํานวนเต็มบวกสามตัวเรียงกนั ไดเสมอ เพราะวา ( n3 - n) = (n - 1)n(n + 1) เปน ผลคณู ของจํานวนเต็มบวกสามตวั เรียงกนั เพราะฉะนั้น 3 | ( n3 - n) ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

56 Mathematical Induction 38. จงแสดงวา 5 | ( n5 - n) ทกุ คา n ∈ N 38. แนวคดิ แบบที่ 1 ให an = n5 - n เพราะฉะน้ัน a1 = 0 ให P(n) แทนขอ ความ “ 5 | an ” (1) การแสดงวา P(1) เปนจริง เพราะวา a1 = 0 เพราะฉะน้ัน 5 | a1 เพราะฉะนั้น P(1) เปนจริง (2) การแสดงวา ถา P(k) เปน จรงิ เม่ือ k ≥ 1 แลว P(k + 1) เปน จริง สมมติ P(k) เปนจรงิ เม่อื k ≥ 1 ak+1 - ak = ((k + 1) 5 - (k + 1)) - ( k5 - k) = (k + 1) 5 - k5 - 1 = ( k5 + 5 k4 + 10 k3 + 10 k2 + 5k + 1) - k5 - 1 = 5 k4 + 10 k3 + 10 k2 + 5k = 5( k4 + 2 k3 + 2 k2 + k) เพราะฉะนน้ั ak+1 = 5( k4 + 2 k3 + 2 k2 + k) + ak เพราะวา (P(k) เปนจรงิ ⇒ 5 | ak ) และ 5 | 5( k4 + 2 k3 + 2 k2 + k) เพราะฉะนั้น 5 | ak+1 เพราะฉะน้นั P(k + 1) เปน จรงิ โดยอุปนัยเชิงคณติ ศาสตร จะได P(n) เปนจริง ทกุ คา n ∈ N เพราะฉะน้ัน 5 | ( n5 - n) ทกุ คา n ∈ N แบบที่ 2 n5 - n = n( n4 - 1) = n( n2 - 1)( n2 + 1) = n(n + 1)(n - 1)( n2 + 1) = (n - 1) n(n + 1)( n2 + 1) กรณีที่ 1 เมอ่ื หลกั หนว ยของ n เปน 0, 1, 4, 5, 6 หรือ 9 จะได 5 | (n - 1)n(n + 1) เพราะฉะนน้ั 5 | ( n5 - n) กรณที ่ี 2 เมือ่ หลกั หนวยของ n เปน 2, 3, 7 หรือ 8 จะไดห ลกั หนวยของ n2 เปน 4 หรอื 9 เพราะฉะนน้ั หลักหนวยของ n2 + 1 ตอ งเปน 5 หรือ 0 เพราะฉะนนั้ 5 | ( n2 + 1) เพราะฉะนนั้ 5 | ( n5 - n) แบบที่ 3 n5 - n = (n - 1)(n + 1)( n2 + 1) n ≡ 0 (mod 5) ⇒ n5 - n ≡ 0 (mod 5) ⇒ 5 | ( n5 - n) n ≡ 1 (mod 5) ⇒ n - 1 ≡ 0 (mod 5) ⇒ (n - 1) (n + 1)( n2 + 1) ≡ 0 (mod 5) ⇒ 5 | ( n5 - n) n ≡ 2 (mod 5) ⇒ n2 ≡ 4 (mod 5) ⇒ n2 + 1 ≡ 0 (mod 5) ⇒ (n - 1)(n + 1)( n2 + 1) ≡ 0 (mod 5) ⇒ 5 | ( n5 - n) รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 57 † n ≡ 3 (mod 5) ⇒ n2 ≡ 9 (mod 5) ⇒ n2 + 1 ≡ 0 (mod 5) ⇒ (n - 1)(n + 1)( n2 + 1) ≡ 0 (mod 5) ⇒ 5 | ( n5 - n) n ≡ 4 (mod 5) ⇒ n2 ≡ 16 (mod 5) ⇒ n2 - 1 ≡ 0 (mod 5) ⇒ (n - 1)(n + 1)( n2 + 1) ≡ 0 (mod 5) ⇒ 5 | ( n5 - n) เพราะฉะนั้น 5 | ( n5 - n) ทุกคา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

58 Mathematical Induction 39. จงแสดงวา 7 | ( n7 - n) ทุกคา n ∈ N † 39. แนวคดิ แบบที่ 1 ให an = n7 - n เพราะฉะน้ัน a1 = 0 ให P(n) แทนขอ ความ “ 7 | an ” (1) การแสดงวา P(1) เปน จริง เพราะวา a1 = 0 เพราะฉะน้ัน 7 | a1 เพราะฉะน้นั P(1) เปนจรงิ (2) การแสดงวา ถา P(k) เปนจริง เมือ่ k ≥ 1 แลว P(k + 1) เปนจรงิ สมมติ P(k) เปนจริง เมื่อ k ≥ 1 ak+1 - ak = ((k + 1) 7 - (k + 1)) - ( k7 - k) = (k + 1) 7 - k7 - 1 = ( k7 + 7 k6 + 21 k5 + 35 k4 + 35 k3 + 21 k2 + 7k + 1) - k7 - 1 = 7 k6 + 21 k5 + 35 k4 + 35 k3 + 21 k2 + 7k = 7( k6 + 3 k5 + 5 k4 + 5 k3 + 3 k2 + k) เพราะฉะนน้ั ak+1 = 7( k6 + 3 k5 + 5 k4 + 5 k3 + 3 k2 + k) + ak เพราะวา (P(k) เปนจรงิ ⇒ 7 | ak ) และ 7 | 7( k6 + 3 k5 + 5 k4 + 5 k3 + 3 k2 + k) เพราะฉะนนั้ 7 | ak+1 เพราะฉะน้ัน P(k + 1) เปน จรงิ โดยอปุ นัยเชงิ คณติ ศาสตร จะได P(n) เปนจริง ทกุ คา n ∈ N เพราะฉะน้ัน 7 | ( n7 - n) ทุกคา n ∈ N แบบท่ี 2 n7 - n = n( n6 - 1) = n( n3 - 1)( n3 + 1) = n(n - 1)( n2 + n + 1)(n + 1)( n2 - n + 1) = (n - 1)n(n + 1)( n2 - n + 1)( n2 + n + 1) จําแนกกรณตี ามเศษเหลือจากการหาร n ดว ย 7 n ≡ 0 (mod 7) ⇒ n7 - n ≡ 0 (mod 7) ⇒ 7 | ( n7 - n) n ≡ 1 (mod 7) ⇒ n - 1 ≡ 0 (mod 7) ⇒ 7 | (n - 1) ⇒ 7 | ( n7 - n) n ≡ 2 (mod 7) ⇒ n2 + n + 1 ≡ 4 + 2 + 1 (mod 7) ⇒ 7 | ( n2 + n + 1) ⇒ 7 | ( n7 - n) n ≡ 3 (mod 7) ⇒ n2 - n + 1 ≡ 9 - 3 + 1 (mod 7) ⇒ 7 | ( n2 - n + 1) ⇒ 7 | ( n7 - n) n ≡ 4 (mod 7) ⇒ n2 + n + 1 ≡ 16 + 4 + 1 (mod 7) ⇒ 7 | ( n2 + n + 1) ⇒ 7 | ( n7 - n) n ≡ 5 (mod 7) ⇒ n2 - n + 1 ≡ 25 - 5 + 1 (mod 7) ⇒ 7 | ( n2 - n + 1) ⇒ 7 | ( n7 - n) n ≡ 6 (mod 7) ⇒ n + 1 ≡ 6 + 1 (mod 7) ⇒ 7 | (n + 1) ⇒ 7 | ( n7 - n) เพราะฉะน้นั 7 | ( n7 - n) ทุกคา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 59 40. จงแสดงวา 11 | ( n11 - n) ทกุ คา n ∈ N † 40. แนวคิด แบบที่ 1 ให an = n11 - n เพราะฉะน้นั a1 = 0 ให P(n) แทนขอความ “ 11 | an ” (1) การแสดงวา P(1) เปนจรงิ เพราะวา a1 = 0 เพราะฉะนัน้ 11 | a1 เพราะฉะนั้น P(1) เปน จรงิ (2) การแสดงวา ถา P(k) เปน จรงิ เมือ่ k ≥ 1 แลว P(k + 1) เปนจริง สมมติ P(k) เปนจรงิ เมือ่ k ≥ 1 -ak+1 ak = ((k + 1)11 - (k + 1)) - ( k11 - k) = (k + 1)11 - k11 - 1 = k11 + 11 k10 + 55 k9 + 165 k8 + 330 k7 + 462 k6 + 462 k5 + 330 k4 + 165 k3 + 55 k2 + 11k + 1 - k11 - 1 = 11 k10 + 55 k9 + 165 k8 + 330 k7 + 462 k6 + 462 k5 + 330 k4 + 165 k3 + 55 k2 + 11k = 11( k10 + 5 k9 + 15 k8 + 30 k7 + 42 k6 + 42 k5 + 30 k4 + 15 k3 + 5 k2 + k) เพราะฉะนัน้ ak+1 = 11( k10 + 5 k9 + 15 k8 + 30 k7 + 42 k6 + 42 k5 + 30 k4 + 15 k3 + 5 k2 + k) + ak เพราะวา (P(k) เปนจริง ⇒ 11 | ak ) และ 11 | 11( k10 + 5 k9 + 15 k8 + 30 k7 + 42 k6 + 42 k5 + 30 k4 + 15 k3 + 5 k2 + k) เพราะฉะน้ัน 11 | ak+1 เพราะฉะนน้ั P(k + 1) เปน จรงิ โดยอุปนัยเชงิ คณติ ศาสตร จะได P(n) เปน จรงิ ทุกคา n ∈ N เพราะฉะนัน้ 11 | ( n11 - n) ทุกคา n ∈ N แบบท่ี 2 โดย Fermat's Theorem p เปนจํานวนเฉพาะและ a เปน จํานวนเต็มบวกและ p ⁄| a จะได ap−1 ≡ 1 (mod p) เพราะฉะนน้ั ap ≡ a (mod p) เพราะฉะนนั้ p | ( ap - a) เพราะฉะน้ัน p | ( np - n) ทุกคา n ∈ N เพราะฉะนั้น 11 | ( n11 - n) ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

60 Mathematical Induction 41. จงแสดงวา 3 | n( n2 + 2) ทุกคา n ∈ N † 41. แนวคดิ แบบท่ี 1 ให an = n( n2 + 2) ให P(n) แทนขอ ความ “ 3 | an ” (1) การแสดงวา P(1) เปนจรงิ เพราะวา a1 = (1)(12 + 2) = 3 เพราะฉะนนั้ 3 | a1 เพราะฉะน้ัน P(1) เปน จรงิ (2) การแสดงวา ถา P(k) เปนจริง เมื่อ k ≥ 1 แลว P(k + 1) เปน จรงิ สมมติ P(k) เปนจริง เม่อื k ≥ 1 เพราะวา ak+1 - ak = (k + 1)((k + 1) 2 + 2) - k( k2 + 2) = (k + 1) 3 + 2(k + 1) - k3 - 2k = ( k3 + 3 k2 + 3k + 1) + 2 - k3 = 3 k2 + 3k + 3 เพราะฉะนนั้ ak+1 = ak + 3( k2 + k + 1) เพราะวา (P(k) เปนจรงิ ⇒ 3 | ak ) และ 3 | (3( k2 + k + 1)) เพราะฉะนน้ั 3 | ak+1 เพราะฉะนั้น P(k + 1) เปน จริง โดยอปุ นยั เชงิ คณิตศาสตร จะได P(n) เปนจรงิ ทกุ คา n ∈ N เพราะฉะน้ัน 3 | n( n2 + 2) ทกุ คา n ∈ N แบบท่ี 2 n ≡ 0 (mod 3) ⇒ n7 - n ≡ 0 (mod 3) ⇒ 3 | n( n2 + 2) n ≡ 1 (mod 3) ⇒ n2 ≡ 1 (mod 3) ⇒ n2 + 2 ≡ 3 (mod 3) ⇒ 3 | ( n2 + 2) ⇒ 3 | n( n2 + 2) n ≡ 2 (mod 3) ⇒ n2 ≡ 4 (mod 3) ⇒ n2 + 2 ≡ 6 (mod 3) ⇒ 3 | ( n2 + 2) ⇒ 3 | n( n2 + 2) รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 61 † 42. จงแสดงวา 24 | (2n - 1)((2n - 1) 2 - 1) ทุกคา n ∈ N 42. แนวคดิ ให an = (2n - 1)((2n - 1) 2 - 1) ให P(n) แทนขอ ความ “ 24 | an ” (1) การแสดงวา P(1) เปนจรงิ เพราะวา a1 = (1)(12 - 1) = 0 เพราะฉะนน้ั 3 | a1 เพราะฉะนั้น P(1) เปนจริง (2) การแสดงวา ถา P(k) เปนจรงิ เมอ่ื k ≥ 1 แลว P(k + 1) เปนจรงิ สมมติ P(k) เปน จริง เมอ่ื k ≥ 1 เพราะวา ak+1 - ak = (2(k + 1) - 1)((2(k + 1) - 1) 2 - 1) - (2k - 1)((2k - 1) 2 - 1) = (2k + 1)((2k + 1) 2 - 1) - (2k - 1)((2k - 1) 2 - 1) = (2k + 1) 3 - (2k + 1) - (2k - 1) 3 + (2k - 1) = (2k + 1) 3 - (2k - 1) 3 - 2 = (8 k3 + 12 k2 + 6k + 1) - (8 k3 - 12 k2 + 6k - 1) - 2 = 24 k2 เพราะฉะนนั้ ak+1 = ak + 24 k2 เพราะวา (P(k) เปนจรงิ ⇒ 24 | ak ) และ 24 | (24 k2 ) เพราะฉะนนั้ 24 | ak+1 เพราะฉะนั้น P(k + 1) เปนจรงิ โดยอปุ นยั เชงิ คณิตศาสตร จะได P(n) เปน จริง ทกุ คา n ∈ N เพราะฉะน้นั 24 | (2n - 1)((2n - 1) 2 - 1) ทกุ คา n ∈ N หมายเหตุ 24 | (2n - 1)((2n - 1) 2 - 1), n = 1, 2, 3, … มคี วามหมายเทยี บเทา กับ 24 | m( m2 - 1) เม่ือ m เปน เลขคี,่ m = 1, 2, 3, … รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

62 Mathematical Induction 43. จงแสดงวา 6 | n(n + 1)(2n + 1) ทกุ คา n ∈ N † 43. แนวคิด ให an = n(n + 1)(2n + 1) ให P(n) แทนขอความ “ 6 | an ” (1) การแสดงวา P(1) เปนจริง เพราะวา a1 = (1)(2)(3) = 6 เพราะฉะน้นั 6 | a1 เพราะฉะน้นั P(1) เปน จริง (2) การแสดงวา ถา P(k) เปนจริง เม่ือ k ≥ 1 แลว P(k + 1) เปน จริง สมมติ P(k) เปนจริง เมอื่ k ≥ 1 เพราะวา ak+1 - ak = (k + 1)((k + 1) + 1)(2(k + 1) + 1) - k(k + 1)(2k + 1) = (k + 1)(k + 2)(2k + 3) - k(k + 1)(2k + 1) = (k + 1)((k + 2)(2k + 3) - k(2k + 1)) = (k + 1)(2 k2 + 7k + 6 - 2 k2 - k) = (k + 1)(6k + 6) = 6(k + 1) 2 เพราะฉะน้นั ak+1 = ak + 6(k + 1) 2 เพราะวา (P(k) เปน จริง ⇒ 6 | ak ) และ 6 | (6(k + 1) 2 ) เพราะฉะนัน้ 6 | ak+1 เพราะฉะนั้น P(k + 1) เปน จรงิ โดยอปุ นยั เชิงคณติ ศาสตร จะได P(n) เปน จริง ทุกคา n ∈ N เพราะฉะนัน้ 6 | n(n + 1)(2n + 1) ทุกคา n ∈ N หมายเหตุ เพราะวา n(n + 1) เปน เลขคู เพราะฉะนั้น 2 | n(n + 1) n ≡ 0 (mod 3) ⇒ 3 | n ⇒ 3 | n(n + 1)(2n + 1) n ≡ 1 (mod 3) ⇒ 2n ≡ 2 (mod 3) ⇒ 2n + 1 ≡ 3 (mod 3) ⇒ 3 | (2n + 1) ⇒ 3 | n(n + 1)(2n + 1) n ≡ 2 (mod 3) ⇒ n + 1 ≡ 3 (mod 3) ⇒ 3 | (n + 1) ⇒ 3 | n(n + 1)(2n + 1) เพราะฉะนั้น 3 | n(n + 1)(2n + 1) ทุกคา n = 1, 2, 3, ... เพราะวา gcd(2, 3) = 1 และ 3 | n(n + 1)(2n + 1) และ 2 | n(n + 1) เพราะฉะน้ัน 6 | n(n + 1)(2n + 1) ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 63 44. จงแสดงวา p| ⎛⎜ p ⎟⎞ ทุกจํานวนเฉพาะ p และ r = 1, 2, …, p - 1 ⎝ r ⎠ 44. แนวคิด ให p เปน จํานวนเฉพาะ ⎜⎛ p ⎞⎟ = p! = (r + 1)(r + 2)...(p − 1) p! ⎝ r ⎠ r!(p − r)! (p − r)! เพราะวา r ≠ 0 และ r ≠ p เพราะฉะน้นั ไมม จี ํานวนเต็มใดในตวั ประกอบของ (p - r)! ท่จี ะไปหาร p ไดล งตัว เพราะฉะนัน้ p หาร ⎛⎜ pr ⎟⎠⎞ ลงตัวเสมอ † ⎝ รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

64 Mathematical Induction 45. กําหนด p เปน จํานวนเฉพาะ จงแสดงวา p | ( np - n) ทุกคา n ∈ N 45. แนวคิด ให p เปน จํานวนเฉพาะ P(n) แทนขอ ความ “ p | ( np - n) ” (1) การแสดงวา P(1) เปน จริง เพราะวา 1p - 1 = 0 เพราะฉะนนั้ p | (1p - 1) เพราะฉะนนั้ P(1) เปนจริง (2) การแสดงวา ถา P(k) เปนจริง เมื่อ k ≥ 1 แลว P(k + 1) เปนจรงิ สมมติ P(k) เปนจริง เมื่อ k ≥ 1 เพราะฉะน้ัน k | ( kp - k) เพราะวา (k + 1) p - (k + 1) = p ⎜⎛ p ⎞⎟ kp−r -k-1 ⎝ r ⎠ ∑ r=0 = kp + p−1 ⎜⎛ pr ⎠⎟⎞ kp−r + 1 - k -1 ⎝ ∑ r =1 = ( kp - k) + p−1 ⎛⎜ pr ⎞⎟⎠ kp−r ⎝ ∑ r =1 และ p| ⎛⎜ p ⎞⎟ ทุกคา r = 1, 2, 3, …, p - 1 ⎝ r ⎠ เพราะฉะนน้ั p | (( kp - k) + p−1 ⎛⎜ p ⎞⎟ kp−r ) เพราะฉะน้ัน P(k + 1) เปนจรงิ ⎝ r ⎠ ∑ r =1 โดยอปุ นยั เชงิ คณิตศาสตร จะได P(n) เปนจริง ทุกคา n ∈ N เพราะฉะน้นั p | np - n ทุกคา n ∈ N หมายเหตุ โดย Fermat Theorem จะได ap−1 ≡ 1(mod p) เพราะฉะนัน้ p | ( ap−1 - 1) เพราะฉะน้นั p | ( ap - a) เพราะฉะนัน้ p | ( np - n) ทกุ คา n ∈ N † รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 65 46. จงแสดงวา 35 | ( 36n - 26n ) ทกุ คา n ∈ N 46. แนวคดิ ให an = 36n - 26n ให P(n) แทนขอ ความ “ 35 | an ” (1) การแสดงวา P(1) เปน จรงิ เพราะวา a1 = 36 - 26 = 729 - 64 = 665 = 35(19) เพราะฉะนัน้ 35 | a1 เพราะฉะนน้ั P(1) เปนจริง (2) การแสดงวา ถา P(k) เปน จริง เมอื่ k ≥ 1 แลว P(k + 1) เปนจริง สมมติ P(k) เปนจริง เมอ่ื k ≥ 1 เพราะวา ak+1 - ak = ( 36(k+1) - 26(k+1) ) - ( 36k - 26k ) = ( 36(k +1) - 36k ) - ( 26(k +1) - 26k ) = 36k ( 36 - 1) - 26k ( 26 - 1) = 36k (729 - 1) - 26k (64 - 1) = 36k (728) - 26k (63) = 36k (665) + 36k (63) - 26k (63) = 36k (35)(19) + 63( 36k - 26k ) = 36k (35)(19) + 63 ak เพราะฉะนัน้ ak+1 = 36k (35)(19) + 64 ak เพราะวา (P(k) เปนจรงิ ⇒ 35 | ak ) และ 35 | ( 36k (35)(19)) เพราะฉะนั้น 35 | ak+1 เพราะฉะนั้น P(k + 1) เปน จรงิ โดยอุปนยั เชงิ คณติ ศาสตร จะได P(n) เปน จริง ทกุ คา n ∈ N เพราะฉะนั้น 35 | ( 36n - 26n ) ทกุ คา n ∈ N † รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

66 Mathematical Induction 47. จงแสดงวา 30 | ( 24n+1 - 2) ทุกคา n ∈ N † 47. แนวคดิ ให an = 24n+1 - 2 ให P(n) แทนขอความ “ 30 | an ” (1) การแสดงวา P(1) เปนจริง เพราะวา a1 = 25 - 2 = 32 -2 = 30 เพราะฉะนั้น 30 | a1 เพราะฉะนน้ั P(1) เปนจรงิ (2) การแสดงวา ถา P(k) เปน จรงิ เมื่อ k ≥ 1 แลว P(k + 1) เปนจริง สมมติ P(k) เปน จรงิ เมอื่ k ≥ 1 เพราะวา ak+1 - ak = ( 24(k+1)+1 - 2) - ( 24k+1 - 2) = -24k +5 24k +1 = (24k+1 24 - 1) = 24k+1 (15) = 24k (30) เพราะฉะนัน้ ak+1 = 24k (30) + ak เพราะวา (P(k) เปนจรงิ ⇒ 30 | ak ) และ 30 | ( 24k (30)) เพราะฉะน้ัน 30 | ak+1 เพราะฉะนั้น P(k + 1) เปนจริง โดยอปุ นัยเชิงคณิตศาสตร จะได P(n) เปน จรงิ ทุกคา n ∈ N เพราะฉะนน้ั 30 | ( 24n+1 - 2) ทุกคา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 67 † 48. จงแสดงวา 20 | (112n - 1) ทุกคา n ∈ N 48. แนวคิด ให an = 112n - 1 ให P(n) แทนขอ ความ “ 20 | an ” (1) การแสดงวา P(1) เปนจรงิ เพราะวา a1 = 112 - 1 = 120 เพราะฉะนน้ั 20 | a1 เพราะฉะนั้น P(1) เปน จรงิ (2) การแสดงวา ถา P(k) เปนจรงิ เมื่อ k ≥ 1 แลว P(k + 1) เปน จรงิ สมมติ P(k) เปน จริง เมอื่ k ≥ 1 เพราะวา ak+1 - ak = (112(k+1) - 1) - (112k - 1) = -112(k +1) 112k = 112k (121 - 1) = 112k (120) เพราะฉะนั้น ak+1 = 112k (120) + ak เพราะวา (P(k) เปน จรงิ ⇒ 20 | ak ) และ 20 | (112k (120))) เพราะฉะนน้ั 20 | ak+1 เพราะฉะนน้ั P(k + 1) เปน จริง โดยอุปนัยเชงิ คณิตศาสตร จะได P(n) เปนจริง ทุกคา n ∈ N เพราะฉะนั้น 20 | (112n - 1) ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

68 Mathematical Induction 49. จงแสดงวา 8 | n(n + 1)(n + 2)(n + 3) ทกุ คา n ∈ N † 49. แนวคิด ให an = n(n + 1)(n + 2)(n + 3) ให P(n) แทนขอความ “ 8 | an ” (1) การแสดงวา P(1) เปนจรงิ เพราะวา a1 = (1)(2)(3)(4) = 8 เพราะฉะนน้ั 8 | a1 เพราะฉะนนั้ P(1) เปนจรงิ (2) สมมติ P(k) เปน จรงิ เม่ือ k ≥ 1 เพราะวา ak+1 - ak = (k + 1)((k + 1) + 1)((k + 1) + 2)((k + 1) + 3) - k(k + 1)(k + 2)(k + 3) = (k + 1)(k + 2)(k + 3)(k + 4) - k(k + 1)(k + 2)(k + 3) = (k + 1)(k + 2)(k + 3)((k + 4) - k) = 4(k + 1)(k + 2)(k + 3) เพราะฉะนั้น ak+1 = ak + 4(k + 1)(k + 2)(k + 3) เพราะวา (k + 1)(k + 2)(k + 3) เปน เลขคู เพราะฉะนนั้ 2 | ((k + 1)(k + 2)(k + 3)) เพราะฉะนน้ั 8 | (4(k + 1)(k + 2)(k + 3)) เพราะวา (P(k) เปน จรงิ ⇒ 8 | ak ) และ 8 | (4(k + 1)(k + 2)(k + 3)) เพราะฉะนัน้ 8 | ak+1 เพราะฉะน้ัน P(k + 1) เปนจรงิ โดยอปุ นยั เชงิ คณติ ศาสตร จะได P(n) เปน จริง ทกุ คา n ∈ N เพราะฉะนัน้ 8 | n(n + 1)(n + 2)(n + 3) ทกุ คา n ∈ N หมายเหตุ 8 | n(n + 1)(n + 2)(n + 3) ทุกคา n ∈ N หมายความวา ผลคณู ของจํานวนเต็มบวก 4 ตวั ท่ีเรียงกนั ตองหารดว ย 8 ลงตัว รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 69 50. จงแสดงวา 120 | ( n5 - 5 n3 + 4n) ทกุ คา n ∈ N † 50. แนวคิด แบบที่ 1 ให an = n5 - 5 n3 + 4n ให P(n) แทนขอ ความ “ 120 | an ” (1) การแสดงวา P(1) เปนจรงิ เพราะวา a1 = 1 - 5 + 4 = 0 เพราะฉะน้นั 120 | a1 เพราะฉะน้ัน P(1) เปนจรงิ (2) สมมติ P(k) เปน จริง เมื่อ k ≥ 1 ak+1 - ak = ((k + 1) 5 - 5(k + 1) 3 + 4(k + 1)) - ( k5 - 5 k3 + 4k) = k5 + 5 k4 + 10 k3 + 10 k2 + 5k - 5( k3 + 3 k2 + 3k + 1) + 4 - k5 + 5 k3 = 5(k - 1)k(k + 1)(k + 2) เพราะฉะนั้น ak+1 = ak + 5(k - 1)k(k + 1)(k + 2) เพราะวา 4! | ((k - 1)k(k + 1)(k + 2)) เพราะฉะน้ัน 120 | (5(k - 1)k(k + 1)(k + 2)) เพราะวา (P(k) เปนจริง ⇒ 120 | ak ) และ 120 | (5(k - 1)k(k + 1)(k + 2)) เพราะฉะนน้ั 120 | ak+1 เพราะฉะนั้น P(k + 1) เปนจรงิ โดยอุปนยั เชงิ คณิตศาสตร จะได P(n) เปน จรงิ ทกุ คา n ∈ N เพราะฉะนัน้ 5! | ( n5 - 5 n3 + 4n) ทกุ คา n ∈ N หมายเหตุ n5 - 5 n3 + 4n = (n - 2)(n - 1)n(n + 1)(n + 2) เพราะวา n - 2, n - 1, n, n + 1, n + 2 เปนจํานวนเตม็ 5 ตัวทเ่ี รียงคา กัน เพราะฉะนั้น 5! | ((n - 2)(n - 1)n(n + 1)(n + 2)) เพราะฉะน้นั 5! หารผลคูณของจํานวนเต็ม 5 ตวั ท่เี รยี งคากนั แบบที่ 2 ให n เปนจํานวนเตม็ บวกใดๆ ให f(n) = n5 - 5 n3 + 4n เพราะวา f(0) = 0, f(1) = 0, f(-1) = 0, f(-2) = 0, f(2) = 0 เพราะฉะนัน้ n5 - 5 n3 + 4n = (n - 2)(n - 1)n(n + 1)(n + 2) เพราะวา 5 | (n - 2)(n - 1)n(n + 1)(n + 2), 8 | (n - 2)(n - 1)n(n + 1)(n + 2), 3 | n(n + 1)(n + 2) และ 5, 8, 3 ไมม ตี ัวประกอบรว มกนั เพราะฉะนน้ั (5)(8)(3) | (n - 2)(n - 1)n(n + 1)(n + 2) เพราะฉะนัน้ 120 | (n - 2)(n - 1)n(n + 1)(n + 2) เพราะฉะนั้น 5! | ( n5 - 5 n3 + 4n) ทุกคา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

70 Mathematical Induction 51. จงแสดงวา 7 | ( 32n+1 + 2n+2 ) ทกุ คา n ∈ N 51. แนวคิด ให an = 32n+1 + 2n+2 ให P(n) แทนขอความ “ 7 | an ” (1) การแสดงวา P(1) เปนจรงิ เพราะวา a1 = 35 เพราะฉะนน้ั 7 | a1 เพราะฉะน้ัน P(1) เปน จรงิ (2) การแสดงวา ถา P(k) เปนจรงิ เมอ่ื k ≥ 1 แลว P(k + 1) เปนจรงิ สมมติ P(k) เปน จรงิ เมื่อ k ≥ 1 -ak +1 ak = ( 32(k +1)+1 + ) - (2(k +1)+2 32k +1 + 2k+2 ) = (32k+1 32 - 1) + (2k+2 21 - 1) = 32k+1 (8) + 2k +2 = 32k+1 (7) + ( 32k+1 + 2k +2 ) = 32k+1 (7) + ak เพราะฉะน้นั ak+1 = 2 ak + 32k+1 (7) เพราะวา (P(k) เปน จริง ⇒ 7 | ak ) และ 7 | ( 32k+1 (7)) เพราะฉะนั้น 7 | ak+1 เพราะฉะนน้ั P(k + 1) เปน จรงิ โดยอุปนยั เชงิ คณิตศาสตร จะได P(n) เปนจรงิ ทุกคา n ∈ N เพราะฉะน้นั 7 | ( 32n+1 + 2n+2 ) ทุกคา n ∈ N † รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 71 † 52. จงแสดงวา 6 | (n( n2 + 5)) ทกุ คา n ∈ N 52. แนวคิด ให an = n( n2 + 5) ให P(n) แทนขอความ “ 6 | an ” (1) การแสดงวา P(1) เปนจริง เพราะวา a1 = 6 เพราะฉะนนั้ 6 | a1 เพราะฉะน้ัน P(1) เปน จริง (2) การแสดงวา ถา P(k) เปนจริง เมือ่ k ≥ 1 แลว P(k + 1) เปนจริง สมมติ P(k) เปน จริง เมือ่ k ≥ 1 ak+1 - ak = ((k + 1)((k + 1) 2 + 5) - k( k2 + 5) = (k + 1) 3 + 5k + 5 - k3 - 5k = k3 + 3 k2 + 3k + 1 + 5 - k3 = 3( k2 + k) + 6 = 3k(k + 1) + 6 เพราะฉะนั้น ak+1 = ak + (3k(k + 1) + 6) เพราะวา k(k + 1) เปน เลขคแู ละ gcd(3, 2) = 1 เพราะฉะนน้ั 2 | k(k + 1) เพราะฉะนน้ั 6 | (3k(k + 1)) เพราะฉะน้ัน 6 | (3k(k + 1) + 6) เพราะวา (P(k) เปนจรงิ ⇒ 6 | ak ) และ 6 | (3k(k + 1) + 6) เพราะฉะนนั้ 6 | ak+1 เพราะฉะน้ัน P(k + 1) เปนจรงิ โดยอุปนัยเชิงคณติ ศาสตร จะได P(n) เปน จรงิ ทุกคา n ∈ N เพราะฉะนนั้ 6 | (n( n2 + 5)) ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

72 Mathematical Induction 53. จงแสดงวา 5 | ( 22n−1 + )32n−1 ทุกคา n ∈ N † 53. แนวคดิ ให an = 22n−1 + 32n−1 ให P(n) แทนขอ ความ “ 5 | an ” (1) การแสดงวา P(1) เปน จรงิ เพราะวา a1 = 5 เพราะฉะนัน้ 5 | a1 เพราะฉะนั้น P(1) เปน จรงิ (2) การแสดงวา ถา P(k) เปน จรงิ เมื่อ k ≥ 1 แลว P(k + 1) เปน จริง สมมติ P(k) เปน จรงิ เมอ่ื k ≥ 1 -ak +1 ak = ( 22(k +1)−1 + )32(k +1)−1 - ( 22k −1 + )32k −1 = (22k−1 22 - 1) + (32k−1 32 - 1) = 22k−1 (3) + 32k−1 (8) = 22k−1 (3) + 32k−1 (3) + 32k−1 (5) = 3( 22k−1 + )32k−1 + 32k−1 (5) = 3 ak + 32k−1 (5) เพราะฉะนน้ั ak+1 = 4 ak + 32k−1 (5) เพราะวา (P(k) เปน จรงิ ⇒ 5 | ak ) และ 5 | ( 32k−1 (5)) เพราะฉะนั้น 5 | ak+1 เพราะฉะนนั้ P(k + 1) เปนจรงิ โดยอปุ นัยเชงิ คณิตศาสตร จะได P(n) เปนจริง ทกุ คา n ∈ N เพราะฉะนั้น 5 | ( 22n−1 + )32n−1 ทุกคา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 73 54. กําหนดให n เปน จํานวนเต็มบวกและ k เปนจํานวนเต็มบวกค่ี จงแสดงวา n (n + 1) | ( 1k + 2k + 3k +… nk ) 2 54. แนวคดิ ให Sk = 1k + 2k + 3k + … nk และ k เปนเลขคี่ กรณที ่ี 1 n เปน เลขคู ให n = 2m เพราะฉะนัน้ n (n + 1) = m(2m + 1) 2 Sk = 1k + 2k + 3k + ... + (m - 1) k + mk + (m + 1) k + (m + 2) k + … + (2m - 1) k + (2m) k Sk = ((2m) k + 1k ) + ((2m - 1) k + 2k ) + ... + ((m + 2) k + (m - 1) k ) + ((m + 1) k + mk ) เพราะวา k เปน เลขคี่ เพราะฉะนน้ั (a + b) | ( ak + bk ) เพราะฉะนั้น (2m + 1) | ((2m) k + 1k ) ((2m - 1) + 2) | ((2m - 1) k + 2k ) ⇒ (2m + 1) | ((2m - 1) k + 2k ) : ((m + 2) + (m - 1)) | ((m + 2) k + (m - 1) k ) ⇒ (2m + 1) | ((m + 2) k + (m - 1) k ) ((m + 1 + m) | ((m + 1) k + mk ) ⇒ (2m + 1) | ((m + 1) k + mk ) เพราะฉะนน้ั (2m + 1) | Sk Sk = (1k + (2m - 1) k ) + ( 2k + (2m - 2) k ) + ... + ((m - 1) k + (m + 1) k ) + mk + (2m) k เพราะวา (1 + (m - 1)) | (1k + (m - 1) k ) ⇒ 2m | (1k + (2m - 1) k ) (2 + (2m - 2)) | ( 2k + (2m - 2) k ) ⇒ 2m | ( 2k + (2m - 2) k ) : ((m - 1) + (m + 1) | ((m - 1) k + (m + 1) k ) ⇒ 2m | ((m - 1) k + (m + 1) k ) m | mk m | (2m) k เพราะฉะน้นั m | Sk เพราะวา gcd(m, 2m + 1) = 1 และ m | Sk และ (2m + 1) | Sk เพราะฉะนนั้ m(2m + 1) | Sk เพราะฉะนน้ั n (n + 1) | Sk 2 กรณที ี่ 2 n เปน จํานวนเตม็ บวกค่ี ให n = 2m - 1 เพราะฉะนัน้ n (n + 1) = m(2m - 1) 2 Sk = 1k + 2k + 3k + … + nk Sk = 1k + 2k + 3k + ... + (m - 1) k + mk + (m + 1) k + … + (2m - 2) k + (2m - 1) k = (1k + (2m − 1)k ) + ( 2k + (2m - 2) k ) + … + ((m - 1) k + (m + 1)) k + mk เพราะวา (1 + (2m - 1)) | (1k + nk ) ⇒ 2m | (1k + nk ) ⇒ m | (1k + nk ) (2 + (2m - 2)) | ( 2k + (2m - 1) k ) ⇒ 2m | ( 2k + (2m - 1) k ) ⇒ m | ( 2k + (2m - 1) k ) : ((m - 1) + (m + 1)) | ((m - 1) k + (m + 1) k ) ⇒ 2m | ((m - 1) k + (m + 1) k ) ⇒ m | ((m - 1) k + (m + 1)) k รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

74 Mathematical Induction m | mk เพราะฉะนัน้ m | Sk Sk = 1k + 2k + ... + 3k + … + (m - 1) k + mk + ... + (2m - 3) k + (2m - 2) k + (2m - 1) k = (1k + (2m - 2) k ) + ( 2k + (2m - 3) k ) + … + ((m - 1) k + mk ) + (2m - 1) k เพราะวา (1 + (2m - 2)) | (1k + (2m - 2) k ) ⇒ (2m - 1) | (1k + (2m - 2) k ) ((2 + (2m - 3)) | ( 2k + (2m - 3) k ) ⇒ (2m - 1) | ( 2k + (2m - 3) k ) : ((m - 1) + (m)) | ((m - 1) k + mk ) ⇒ (2m - 1) | ((m - 1) k + mk ) (2m - 1) | (2m - 1) k เพราะฉะนน้ั (2m - 1) | Sk เพราะวา gcd(m, 2m - 1) = 1 และ m | Sk และ (2m - 1) | Sk เพราะฉะนั้น m(2m - 1) | Sk เพราะฉะนน้ั n (n + 1) | Sk 2 เพราะฉะนน้ั จากกรณี 1 และ 2 จะได ( n (n + 1)) | (1k + 2k + 3k + … + nk ) † 2 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 75 † 55. จงแสดงวา ทุกจํานวนจริง a ≥ 2 จะได an > n ทุกคา n ∈ N 55. แนวคดิ กําหนด a ≥ 2 และ P(n) แทนขอ ความ “ an > n ” (1) การแสดงวา P(1) เปน จริง เพราะวา a ≥ 2 เพราะฉะนน้ั a1 ≥ 1 เพราะฉะน้นั P(1) เปน จริง (2) การแสดงวา ถา P(k) เปนจรงิ แลว P(k + 1) เปนจริง สมมติ P(k) เปนจรงิ เมอ่ื k ≥ 1 เพราะวา ak+1 = ak a > ka (P(k) เปนจริง ⇒ ak > k) ≥ k(2) (เพราะวา a ≥ 2 ) = k(1 + 1) > k(1 + 1 ) (เพราะวา k ≥ 1 ⇒ 1 ≥ 1 ) k k =k+1 เพราะฉะน้ัน ak+1 > k + 1 เพราะฉะนั้น P(k + 1) เปน จริง โดยอปุ นัยเชิงคณติ ศาสตร จะได P(n) เปน จริง ทุกคา n ∈ N เพราะฉะน้นั ทุกจํานวนจริง a ≥ 2 จะได an > n ทุกคา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

76 Mathematical Induction 56. จงแสดงวา 3n ≥ 1 + 2n ทกุ คา n ∈ N † 56. แนวคิด ให P(n) แทนขอ ความ “ 3n ≥ 1 + 2n ” (1) การแสดงวา P(1) เปน จรงิ เพราะวา 31 = 3 ≥ 1 + 2(1) เพราะฉะนนั้ P(1) เปน จริง (2) การแสดงวา ถา P(k) เปน จริง แลว P(k + 1) เปน จริง สมมติ P(k) เปน จริง เมอ่ื k ≥ 1 3k +1 = 3k 3 ≥ (1 + 2k)(3) (P(k) เปนจริง ⇒ 3k ≥ 1 + 2k) = 3 + 6k > 3 + 2k (เพราะวา 6k > 2k ) = 3 + 2k = 1 + 2k + 2 = 1 + 2(k + 1) เพราะฉะน้นั 3k+1 ≥ 1 + 2(k + 1) เพราะฉะน้ัน P(k + 1) เปน จริง โดยอปุ นยั เชงิ คณติ ศาสตร จะได P(n) เปนจริง ทกุ คา n ∈ N เพราะฉะนนั้ 3n ≥ 1 + 2n ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 77 57. ให m เปน จํานวนเต็มบวก จงแสดงวา 1 + n ≤ (1 + 1 ) n ทุกคา n∈N mm 57. แนวคิด แบบท่ี 1 ให P(n) แทนขอความ “ 1 + n ≤ (1 + 1 ) n ” mm (1) การแสดงวา P(1) เปน จรงิ เพราะวา 1 + 1 ≤ (1 + 1 )1 เพราะฉะน้นั P(1) เปน จรงิ mm (2) การแสดงวา ถา P(k) เปนจริง เมอื่ k ≥ 1 แลว P(k + 1) เปน จริง สมมติ P(k) เปนจรงิ เมอื่ k ≥ 1 (1 + 1 ) k+1 = (1 + 1 )(1 + 1 ) k m mm ≥ (1 + 1 )(1 + k ) (P(k) เปน จรงิ ⇒ (1 + 1 ) k ≥ 1 + k ) mm mm =1+ k + 1 + k m m m2 = 1 + k+1 + k m m2 > 1 + k +1 ( k ≥ 0) m m2 เพราะฉะน้ัน 1 + k + 1 < (1 + 1 ) k+1 เพราะฉะนัน้ P(k + 1) เปน จริง mm โดยอปุ นัยเชิงคณติ ศาสตร จะได P(n) เปนจรงิ ทกุ คา n ∈ N เพราะฉะน้ัน 1 + n < (1 + 1 ) n ทกุ คา n ∈ N mm แบบที่ 2 (1 + 1 )n =1+ ⎛⎜⎝ n ⎠⎟⎞ ( 1 )1 + ⎜⎛⎝ n ⎠⎟⎞ ( 1 ) 2 +…+( 1 )n 1 m 2 m m m > 1 + ⎜⎝⎛ n ⎞⎟⎠ ( 1 ) ( ⎜⎝⎛ n ⎟⎞⎠ ( 1 ) 2 +…+( 1 )n ≥ 0) 1 m 2 m m =1+ n m เพราะฉะน้ัน (1 + 1 ) n > 1 + n ทกุ คา n = 1, 2, 3, … และ m > 0 † mm รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

78 Mathematical Induction 58. ให m เปน จํานวนจริงบวก จงแสดงวา (1 + 1 ) n < 1 + n + n2 ทกุ คา n = 1, 2, 3, ... , m m m m2 58. แนวคดิ ให P(n) แทนขอความ “ (1 + 1 ) n < 1 + n + n2 ” m m m2 เพราะวา (1 + 1 )1 = 1 + 1 < 1 + 1 + 1 เพราะฉะนัน้ P(1) เปน จรงิ m m m m2 สมมติ P(k) เปน จริง เมื่อ k ∈ { 1, 2, 3, ... , m - 1 } เพราะฉะนั้น (1 + 1 ) k < 1 + k + k2 ... (1) m m m2 (จาก (1)) (1 + 1 ) k+1 = (1 + 1 )(1 + 1 ) k m mm < (1 + 1 )(1 + k + k2 ) m m m2 = 1 + k + k2 + 1 + k + k2 m m2 m m2 m3 = 1 + k + 1 + k2 + k + k2 m m2 m3 0 < k ≤ m ⇒ k2 ≤ (k + 1)m ⇒ k2 ≤k+1⇒ k2 ≤ k +1 m m3 m2 เพราะฉะนน้ั (1 + 1 ) k+1 = 1 + k + 1 + k2 + k + k2 m m m2 m3 ≤ 1 + k + 1 + k2 + k + k + 1 m m2 m2 = 1 + k + 1 + k2 + 2k + 1 m m2 = 1 + k + 1 + (k + 1)2 m m2 เพราะฉะนัน้ (1 + 1 ) k+1 ≤ 1 + k + 1 + (k + 1)2 m m m2 เพราะฉะน้นั P(k + 1) เปน จริง เพราะฉะนน้ั (1 + 1 ) n < 1 + n + n2 ทุกคา n = 1, 2, 3, ... , m m m m2 หมายเหตุ m = 2 และ n = 7 จะได (1 + 1 ) n = (1 + 1 ) 7 = 2187 = 17.086 และ 1 + n + n2 = 1 + 7 + 49 = 76 = 16.75 m 2 128 m m2 24 4 เพราะฉะน้นั มกี รณที ่ี (1 + 1 ) n < 1 + n + n2 ไมจรงิ เมอ่ื n > m † m m m2 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 79 59. จงแสดงวา 2 ≤ (1 + 1 ) n ≤ 3 ทกุ คา n ∈ N n 59. แนวคดิ จากขอ 57 และ 58 จะได 1 + n ≤ (1 + 1 ) n < 1 + n + n2 ทุกคา n = 1, 2, ... , m mm m m2 แทนคา n = m จะได 1 + n ≤ (1 + 1 ) n ≤ 1 + n + n2 nn n m2 2 ≤ (1 + 1 ) n ≤ 1 + 1 + 1 n 2 ≤ (1 + 1 ) n ≤ 3 n หมายเหตุ n = 2, 3, 4, … จะได 2 < (1 + 1 ) n < 3 n เพราะฉะน้ัน 2 < lim (1 + 1 )n <3 n→∞ n และเมื่อหาคาลิมติ แทจรงิ จะไดว า lim (1 + 1 )n = e = 2.71828 † n→∞ n รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

80 Mathematical Induction 60. จงแสดงวา n! > ( n ) n ทกุ คา n ∈ N e 60. แนวคิด ให P(n) แทนขอความ “ n! > ( n ) n ” e (1) การแสดงวา P(1) เปน จริง เพราะวา 1 > 1 = ( 1 )1 เพราะฉะนั้น P(1) เปนจริง ee (2) การแสดงวา ถา P(k) เปน จรงิ เมอ่ื k ≥ 1 แลว P(k + 1) เปนจรงิ สมมติ P(k) เปน จรงิ เมือ่ k ≥ 1 เพราะวา (1 + )1 k +1 > (1 + 1 )k ... (1) ... (2) k +1 k † หมายเหตุ ดูการพสิ ูจน (1) ในหนงั สอื คณิตศาสตรป รนยั เลมที่ 29 โลกอสมการ หนา 138 และ lim (1 + 1 )n = e เพราะฉะน้นั e > (1 + 1 )k เพราะฉะนั้น e 1 )k >1 (1 + k n→∞ n k เพราะวา (k + 1)! = (k + 1)k! > (k + 1)( k ) k (P(k) เปน จริง ⇒ k! > ( k ) k ) e e = ( k + 1 ) k+1 ( kke ) e (k + 1)k = ( k + 1 ) k+1 ( e )e (1 + 1 )k k > ( k + 1 ) k+1 (1) (จาก (2)) e เพราะฉะนน้ั (k + 1)! > ( k + 1 ) k+1 เพราะฉะนนั้ P(k + 1) เปน จริง e โดยอปุ นยั เชิงคณิตศาสตร จะได P(n) เปนจรงิ ทกุ คา n ∈ N เพราะฉะน้นั ( n ) n < n! ทุกคา n ∈ N e รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 81 61. จงแสดงวา n! < ( n ) n ทุกคา n ∈ N e 61. แนวคดิ ให P(n) แทนขอ ความ “ n! < ( n ) n ” e (1) จงแสดงวา P(7) เปน จรงิ เพราะวา ln(6!) = ln(720) = 6.58 ln( 7 ) 7 = 7(ln 7 - ln e) = 7(ln 7 - 1) = 6.62 e เพราะฉะนั้น ln(6!) < ln( 7 )7 e 6! < ( 7 ) 7 e 7! < 7( 7 ) 7 e เพราะฉะน้ัน P(7) เปน จรงิ (2) จงแสดงวา ถา P(k) เปนจริง เมอ่ื k ≥ 1 แลว P(k + 1) เปนจริง สมมติ P(k) เปน จรงิ เม่ือ k ≥ 1 เพราะฉะนน้ั k! < k( k ) k ... (1) e หมายเหตุ f(x) = (1 + 1 ) x +1 มี f ′(x) = xln(1 + 1 ) −1 (1 + 1 ) x +1 = (ln(1 + 1 ) 1 )(1 + 1 ) x +1 x x x x - x x x เพราะฉะนั้น f ′(x) < 0 ทุกคา x > 1 เพราะฉะนัน้ f เปนฟงกชันลดแท เมือ่ x ≥ 2 เพราะฉะน้นั (1 + 1 ) n +1 > (1 + )1 n +2 ทุกคา n n n +1 เพราะวา lim (1 + 1 ) n +1 = e และ (1 + 1 ) n +1 > (1 + )1 n +2 ทุกคา n ∈ N n→∞ n n n +1 เพราะฉะนั้น (1 + 1 ) n+1 > e ทุกคา n เพราะฉะน้นั e < 1 ทุกคา n ∈ N ... (2) n (1 + 1 )n +1 n (k + 1)! = (k + 1)(k!) < (k + 1)(k( k ) k ) e = (k + 1) (k + 1)k +1kk +1e ek +1(k + 1)k +1 = (k + 1)( k +1 ) k +1 kk +1e e (k + 1)k +1 = (k + 1)( k + 1 ) k+1 ( e )e (1 + 1 )k +1 k < (k + 1)( k + 1 ) k+1 (1) (จาก (2)) e เพราะฉะนั้น (k + 1)! < (k + 1)( k + 1 ) k+1 e เพราะฉะนน้ั P(k + 1) เปน จริง โดยอปุ นยั เชิงคณิตศาสตร จะได P(n) เปน จริง ทกุ คา n ≥ 7 เพราะฉะน้ัน n! < n( n ) n ทุกคา n ≥ 7 † e รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

82 Mathematical Induction 62. การแสดงวา ( n ) n < n! < n( n ) n ทกุ คา n ≥ 7 † ee 62. แนวคดิ จากขอ 60 n! > ( n ) n และจากขอ 61 n! < n( n ) n เม่ือ n ≥ 7 ee เพระฉะน้ัน ( n ) n < n! < n( n ) n ทุกคา n ≥ 7 ee รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 83 63. จงแสดงวา 1 ⋅ 3 ⋅ 5 ⋅ … (2n − 1) < 1 ทกุ คา n ∈ N 2 4 6 2n 3n + 1 63. แนวคิด ให P(n) แทนขอ ความ “ 1 ⋅ 3 ⋅ 5 ⋅ … (2n − 1) < 1 ” 2 4 6 2n 3n + 1 (1) จงแสดงวา P(2) เปนจริง เพราะวา 1 = 1 = 0.38 และ 1 ⋅ 3 = 3 = 0.375 เพราะฉะนั้น 1 ⋅ 3 < 1 3(2) + 1 7 24 8 24 3(2) + 1 เพราะฉะน้ัน P(2) เปน จริง (2) จงแสดงวา ถา P(k) เปน จริง เม่อื k ≥ 1 แลว P(k + 1) เปนจรงิ สมมติ P(k) เปน จรงิ เม่อื k ≥ 1 เพราะฉะนัน้ 1 ⋅ 3 ⋅ 5 ⋅ … (2k − 1) < 1 2 4 6 2k 3k + 1 …1 ⋅ 3 ⋅ 5 ⋅ ⋅ (2k − 1) (2(k + 1) − 1) < 1 1 ( 2(k + 1) − 1 ) = 2k + 1 2(k + 1) 3k + 2(k + 1) (2k + 2) 3k + 1 246 2k …1 ⋅ 3 ⋅ 5 ⋅ ⋅ (2k − 1) (2k + 1) < 2k + 1 ... (1) 2(k + 1) 246 2k (2k + 2) 3k + 1 ( 2k + 1 ) 2 = (2k + 1)2 (2k + 2) 3k + 1 (2k + 2)2 (3k + 1) = (2k + 1)2 12k3 + 28k2 + 20k + 4 = (2k + 1)2 (2k + 1)2(3k + 4) + 4 = 1 (3k + 4) + 4 < 1 3k + 4 =1 3(k + 1) + 1 เพราะฉะนน้ั 2k + 1 < 1 ... (2) (2k + 2) 3k + 1 3(k + 1) + 1 จาก (1) และ (2) จะได 1 ⋅ 3 ⋅ 5 ⋅ … ⋅ (2k − 1) 2k + 1 < 1 เพราะฉะนัน้ P(k + 1) เปน จรงิ 246 2k 2k + 2 3(k + 1) + 1 โดยอปุ นยั เชงิ คณิตศาสตร จะได P(n) เปนจริง ทุกคา n = 2, 3, 4, ... เพราะฉะนนั้ 1 ⋅ 3 ⋅ 5 ⋅ … (2n − 1) < 1 ทุกคา n = 2, 3, 4, ... 2 4 6 2n 3n + 1 เพราะวา 1 = 1 เพราะฉะนั้น 1 ⋅ 3 ⋅ 5 ⋅ … (2n − 1) < 1 ทุกคา n ∈ N † 2 3(1) + 1 2 4 6 2n 3n + 1 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

84 Mathematical Induction 64. กําหนดให a1 = 1 และ an = (n) an−1 จงแสดงวา an = n! 64. แนวคดิ ให P(n) แทนขอความ “ an = n! ” (1) จงแสดงวา P(1) เปนจริง เพราะวา a1 = 1 = 1! เพราะฉะนั้น P(1) เปนจรงิ (2) จงแสดงวา ถา P(k) เปน จริง เมื่อ k ≥ 1 แลว P(k + 1) เปนจริง สมมติ P(k) เปนจรงิ เมือ่ k ≥ 1 เพราะวา ak+1 = (k + 1) a(k+1)−1 = (k + 1) ak (P(k) เปน จรงิ ⇒ ak = k!) = (k + 1)k! = (k + 1)! เพราะฉะน้ัน P(k + 1) เปน จรงิ โดยอุปนัยเชิงคณิตศาสตร จะได P(n) เปน จรงิ ทกุ คา n ∈ N เพราะฉะนัน้ an = n! ทกุ คา n ∈ N † รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 85 65. กําหนดให an = - n an - 1 + n!, a0 =1 จงแสดงวา an = ⎧⎪ n! ; n เปน เลขคู ⎨ 0 ; n เปน เลขค่ี ⎪⎩ 65. แนวคดิ ให P(n) แทนขอความ “ a2n = (2n)! ” (1) จงแสดงวา P(1) เปนจริง เพราะวา a1 = (-1) a0 + 1 = 0 และ a2 = -2 a0 + 2! = 2 เพราะฉะนั้น a2 = 2! เพราะฉะนน้ั P(1) เปน จรงิ (2) สมมติ P(k) เปนจรงิ เมอ่ื k ≥ 1 =a2(k +1) a2k +2 (P(k) เปน จรงิ ⇒ a2k = (2k)!) ... (1) a2k+1 = -(2k + 1) a2k + (2k + 1)! = -(2k + 1)((2k)!) - (2k + 1)! =0 =a2(k +1) a2k +2 (จาก (1)) = -(2k + 2) a2k+1 + (2k + 2)! = -(2k + 2)(0) + (2k + 2)! = (2k + 2)! เพราะฉะนน้ั P(k + 1) เปน จรงิ โดยอปุ นัยเชิงคณิตศาสตร จะได P(n) เปนจริง ทุกคา n ∈ N เพราะฉะน้ัน a2n = (2n)! ทุกคา n ∈ N เพราะวา a2n+1 = -(2n + 1) a2n + (2n + 1)! = -(2n + 1)(2n)! + (2n + 1)! =0 เพราะฉะนั้น a2n+1 = 0 ทุกคา n = 1, 2, 3, … เพราะฉะนัน้ an = ⎧⎪ n! ; n เปน เลขคู ทุกคา n ∈ N † ⎨ 0 ; n เปนเลขคี่ ⎪⎩ รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

86 Mathematical Induction 66. กําหนดให an = 2 an−1 + (−1)n , a0 = 2 จงแสดงวา an = 5 ( 2n ) + 1 (−1)n 3 3 66. แนวคิด ให P(n) แทนขอ ความ “ an = 5 ( 2n ) + 1 (−1)n ” 3 3 (1) จงแสดงวา P(1) เปนจรงิ เพราะวา a1 = 2 a0 + (−1)1 = 2(2) - 1 = 3 = 5 ( 21 ) + 1 (−1)1 = 10 - 1 =3 3 3 3 3 เพราะฉะนัน้ P(1) เปนจรงิ (2) จงแสดงวา ถา P(k) เปน จริง เม่ือ k ≥ 1 แลว P(k + 1) เปนจรงิ สมมติ P(k) เปนจริง เมอ่ื k ≥ 1 ak +1 = 2 ak + (−1)k +1 = 2( 5 ( 2k ) + 1 (−1)k ) + (−1)k +1 (P(k) เปน จรงิ ⇒ ak = 5 ( 2k ) + 1 (−1)k ) 3 3 3 3 = 5 ( 2k +1 ) + 2 (−1)k + (−1)k +1 3 3 = 5 ( 2k+1) - 2 (-1) (−1)k + (−1)k+1 33 = 5 ( 2k +1 ) - 2 (−1)k +1 + (−1)k +1 33 = 5 ( 2k +1 ) + 1 (−1)k+1 33 เพราะฉะนัน้ P(k + 1) เปน จริง โดยอุปนยั เชงิ คณติ ศาสตร จะได P(n) เปน จริง ทุกคา n ∈ N เพราะฉะน้ัน an = 5 ( 2n ) + 1 (−1)n ทุกคา n ∈ N † 3 3 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 87 † 67. กําหนดให an+1 = an ( an + 2), a1 = 3 จงแสดงวา an = (2)2n - 1 67. แนวคดิ ให P(n) แทนขอความ “ an = (2)2n - 1 ” (1) จงแสดงวา P(1) เปนจรงิ เพราะวา (2)21 - 1 = 4 - 1 = 3 = a1 เพราะฉะนน้ั P(1) เปน จริง (2) จงแสดงวา ถา P(k) เปนจริง เม่อื k ≥ 1 แลว P(k + 1) เปน จรงิ สมมติ P(k) เปนจรงิ เม่ือ k ≥ 1 ak+1 = ak ( ak + 2) = (ak )2 + 2 ak = ( (2)2k - 1) 2 + 2 (2)2k - 1 (P(k) เปน จริง ⇒ ak = (2)2k - 1) = (2)2k (2)2k - 2 (2)2k + 1 + (2)2k +1 - 2 = (2)2k +1 - 1 เพราะฉะน้ัน P(k + 1) เปน จริง โดยอปุ นยั เชงิ คณติ ศาสตร จะได P(n) เปนจริง ทุกคา n ∈ N เพราะฉะนัน้ an = (2)2n - 1 ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

88 Mathematical Induction 68. กําหนดให an = an −1 + 3(n - 1), a0 = 1 จงแสดงวา an = 1 (n - 1)n + 1 2 68. แนวคดิ ให P(n) แทนขอ ความ “ an = 3 (n - 1)n + 1 ” 2 (1) จงแสดงวา P(1) เปนจรงิ เพราะวา a1 = a0 + 3(1 - 1) = a0 = 1 และ 3 (1 - 1)(1) + 1 = 1 เพราะฉะนน้ั P(1) เปน จริง 2 (2) จงแสดงวา ถา P(k) เปน จริง เมอื่ k ≥ 1 แลว P(k + 1) เปน จริง สมมติ P(k) เปนจรงิ เมอื่ k ≥ 1 ak+1 = a(k+1)−1 + 3((k + 1) - 1) = ak + 3k = 3 (k - 1)k + 1 + 3k (P(k) เปน จรงิ ⇒ ak = 3 (k - 1)k + 1) 2 2 = 3 (k - 1)k + 3k + 1 2 = 3k( k − 1 + 1) + 1 2 = 3k( k + 1 ) + 1 2 = 3 k(k + 1) + 1 2 = 3 ((k + 1) - 1) (k + 1) + 1 2 เพราะฉะน้นั P(k + 1) เปน จริง โดยอปุ นยั เชงิ คณิตศาสตร จะได P(n) เปนจรงิ ทุกคา n เพราะฉะน้ัน an = 3 (n - 1)n + 1 ทกุ คา n ∈ N † 2 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 89 69. กําหนดให a1 = 3, a2 = 7, an = 3 an−1 - 2 an−2 จงแสดงวา an = 2n+1 - 1 ... (1) 69. แนวคดิ ให P(n) แทนขอความ “ an = 2n+1 - 1 ” † (1) จงแสดงวา P(3) เปนจรงิ เพราะวา 3 a2 - 2 a1 = 3(7) - 2(3) = 15 = 24 - 1 = a3 เพราะฉะนน้ั P(3) เปนจริง (2) จงแสดงวา ถา P(i) เปนจริง ทกุ คา i, i = 1, 2, 3, …, k แลว P(k + 1) เปน จรงิ สมมติ P(i) เปน จรงิ ทกุ คา i, i = 1, 2, 3, …, k เพราะฉะน้นั ak = 2k+1 - 1 และ ak−1 = 2(k−1)+1 - 1 = 3 - 2ak+1 a(k +1)−1 a(k +1)−2 = 3 ak - 2 ak−1 (จาก (1)) = 3( 2k+1 - 1) - 2( 2(k−1)+1 - 1) = 3(2⋅ 2k - 1) - 2( 2k - 1) = 6⋅ 2k - 3 - 2⋅ 2k + 2 = 4⋅ 2k - 1 = 22 ⋅ 2k - 1 = 2k+2 - 1 = 2(k +1)+1 - 1 เพราะฉะน้นั ak+1 = 2(k+1)+1 - 1 เพราะฉะน้ัน P(k + 1) เปนจริง โดยอุปนัยเชงิ คณิตศาสตร จะได P(n) เปน จรงิ ทุกคา n ∈ N เพราะฉะนั้น an = 2n+1 - 1 ทุกคา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

90 Mathematical Induction 70. กําหนดให an = an−2 และ a0 = 1 จงแสดงวา a2n = 1 − 2n n(n − 3) (2n)! 70. แนวคดิ ให P(n) แทนขอ ความ “ a2n = 1 − 2n ” (2n)! (1) จงแสดงวา P(1) เปนจรงิ เพราะวา a2 = a0 = 1 และ 1 − 2(1) = −1 เพราะฉะนัน้ P(1) เปน จริง (1)(1 − 3) −2 (2(1))! 2 (2) จงแสดงวา ถา P(k) เปนจรงิ เมอื่ k ≥ 1 แลว P(k + 1) เปนจริง สมมติ P(k) เปนจริง เม่อื k ≥ 1 =a2(k +1) a2k + 2 = a2k (2k + 2)(2k + 2 − 3) = 1 (1 − 2k) (P(k) เปนจริง ⇒ a2k = 1 − 2k ) (2k + 2)(2k + 2 − 3) (2k)! (2k)! = 1 − 2k (2(k + 1))(2k − 1)(2k)! = −1 (2(k + 1))(2k)! = −1(2k + 1) (2k + 2)(2k + 1)(2k)! = −1 − 2k (2k + 2)! = 1 − 2 − 2k (2(k + 1))! = 1 − 2(k + 1) (2(k + 1))! เพราะฉะนั้น P(k + 1) เปนจรงิ โดยอปุ นยั เชิงคณิตศาสตร จะได P(n) เปนจรงิ ทุกคา n ∈ N เพราะฉะนน้ั a2n = 1 − 2n ทกุ คา n ∈ N † (2n)! รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 91 71. กําหนดให a1 = 7 และ (2n + 1)(2n) an - 7 an−1 = 0 จงแสดงวา an = 7n 6 (2n + 1)! 71. แนวคดิ ให P(n) แทนขอความ “ an = 7n ” (2n + 1)! (1) จงแสดงวา P(1) เปน จริง เพราะวา 71 = 7 = a1 เพราะฉะนัน้ P(1) เปนจรงิ (2(1) + 1)! 6 (2) จงแสดงวา ถา P(k) เปนจรงิ เมื่อ k ≥ 1 แลว P(k + 1) เปนจริง สมมติ P(k) เปนจรงิ เม่ือ k ≥ 1 (2(k + 1) + 1)(2(k + 1)) ak+1 - 7 a(k+1)−1 = 0 (2(k + 1) + 1)(2(k + 1)) ak+1 = 7 ak = 7( 7k 1)! ) (P(k) เปน จรงิ ⇒ ak = 7k 1)! ) (2k + (2k + = 7k +1 (2k + 1)! =ak +1 7k +1 (2(k + 1) + 1)(2(k + 1)(2k + 1)! = 7k +1 (2(k + 1) + 1)! เพราะฉะนั้น P(k + 1) เปนจรงิ โดยอปุ นยั เชิงคณติ ศาสตร จะได P(n) เปน จริง ทกุ คา n ∈ N เพราะฉะนนั้ an = 7n ทกุ คา n ∈ N † (2n + 1)! รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

92 Mathematical Induction 72. กําหนดให a0 = 0, a1 = 1 และ n an + 2 an−2 = 0, n = 2, 3, 4, … จงแสดงวา a2n = (−1)n ทกุ คา n ∈ N n! 72. แนวคิด ให P(n) แทนขอความ “ a2n = (−1)n ” n! (1) จงแสดงวา P(1) เปนจรงิ เพราะวา 2 a2 + 2 a2−2 = 0 เพราะฉะน้ัน a2 = - a0 = -1 = (−1)1 เพราะฉะนน้ั a 2(1) = (−1)1 1! 1! เพราะฉะนนั้ P(1) เปน จรงิ (2) จงแสดงวา ถา P(k) เปน จรงิ เมอื่ k ≥ 1 แลว P(k + 1) เปนจริง สมมติ P(k) เปน จริง 2(k + 1) a2(k+1) - 2 a2(k+1)−2 = 0 (k + 1) a2(k+1) = - a2k = -( (−1)k ) (P(k) เปนจริง ⇒ a2k = (−1)k ) k! k! (−1)k +1 (−1)k +1 (k + 1)(k!) (k + 1)! = =a2(k +1) เพราะฉะนน้ั P(k + 1) เปนจรงิ โดยอปุ นยั เชงิ คณิตศาสตร จะได P(n) เปนจรงิ ทกุ คา n ∈ N เพราะฉะนน้ั a2n = (−1)n ทุกคา n ∈ N † n! รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 93 73. กําหนดให an = 2 an−1 + 3an−2 , a0 = 1 และ a1 = 1 จงแสดงวา an = - 1 ( 3n + (−1)n ) 2 73. แนวคดิ ให P(n) แทนขอความ “ an = 1 ( 3n + (−1)n )” 2 (1) จงแสดงวา P(1) เปนจริง เพราะวา 1 ( 31 + (−1)1 ) = 1 = a1 เพราะฉะนัน้ P(1) เปนจริง 2 (2) จงแสดงวา ถา P(1), P(2), … , P(k) เปน จริง แลว P(k + 1) เปน จริง สมมติ P(1), P(2), … , P(k) เปนจรงิ เพราะฉะนั้น ak = 1 ( 3k + (−1)k ) และ ak −1 = 1 ( 3k −1 + )(−1)k −1 ... (1) 2 2 † ak+1 = 2 ak + 3 ak−1 = 2( 1 ( 3k + (−1)k )) + 3( 1 ( 3k−1 + )(−1)k−1 (จาก (1)) 22 = 3k + (−1)k + 1 ( 3k ) + (−1)k−1 3 22 = 3 ( 3k ) + (−1)k (1 + (−1)−1 ( 3 )) 22 = 3k+1 + (−1)k (1 - 3 ) 22 = +3k +1 (−1)k+1 22 = (1 3k +1 + )(−1)k +1 2 เพราะฉะนนั้ P(k + 1) เปนจรงิ โดยอุปนยั เชิงคณิตศาสตร จะได P(n) เปน จรงิ ทุกคา n ∈ N เพราะฉะนน้ั an = 1 ( 3n + (−1)n ) ทุกคา n ∈ N 2 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

94 Mathematical Induction 74. กําหนดให a0 = 1, a1 = 1 และ an = 3 an−1 + 4 an−2 จงแสดงวา an = 2 ( 4n ) + 3 (−1)n 5 5 74. แนวคดิ ให P(n) แทนขอ ความ “ an = 2 ( 4n ) + 3 (−1)n ” 5 5 (1) จงแสดงวา P(1) เปน จริง เพราะวา 2 ( 41 ) + 3 (−1)1 = 8 - 3 =1= a1 เพราะฉะนน้ั P(1) เปนจรงิ 5 5 5 5 (2) จงแสดงวา ถา P(1), P(2), ... , P(k) เปน จรงิ แลว P(k + 1) เปนจรงิ สมมติ P(1), P(2), ... , P(k) เปน จรงิ เพราะฉะนน้ั ak = 2 ( 4k ) + 3 (−1)k และ ak −1 = 2 ( 4k −1 ) + 3 (−1)k −1 ... (1) 5 5 5 5 ak+1 = 3 ak + 4 ak−1 = 3( 2 ( 4k ) + 3 (−1)k ) + 4( 2 ( 4k−1 ) + 3 )(−1)k−1 (จาก (1)) 55 55 = 6 ( 4k ) + 8 ( 4k −1 ) + 9 (−1)k + 12 (−1)k−1 55 55 = 6 ( 4k ) + 8 ( 1 )( 4k ) + ( 9 - 12 ) (−1)k 5 54 55 = ( 6 + 2 ) 4k - 3 (−1)k 55 5 = 8 4k + 3 (−1)k +1 55 = 2 ( 4k +1 ) + 3 (−1)k+1 55 เพราะฉะนนั้ P(k + 1) เปน จรงิ โดยอุปนัยเชิงคณติ ศาสตร จะได P(n) เปน จริง ทกุ คา n ∈ N เพราะฉะนนั้ an = 2 ( 4n ) + 3 (−1)n ทกุ คา n ∈ N † 5 5 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 95 75. กําหนดให a1 = 2 และ an = an−1 + n จงแสดงวา an =1+ 1 n(n + 1), n = 1, 2, 3, … 2 75. แนวคิด ให P(n) แทนขอความ “ an =1 + 1 n(n + 1) ” 2 (1) จงแสดงวา P(1) เปน จรงิ เพราะวา 1 + 1 (1)(1 + 1) = 2 = a1 เพราะฉะน้ัน P(1) เปนจรงิ 2 (2) จงแสดงวา ถา P(1), P(2), … , P(k) แลว P(k + 1) เปน จรงิ สมมติ P(1), P(2), … , P(k) เปนจรงิ ak+1 = a(k+1)−1 + (k + 1) (P(k) เปนจรงิ ⇒ ak =1 + 1 k(k + 1)) = ak + (k + 1) 2 = 1 + 1 k(k + 1) + (k + 1) 2 = 1 + (k + 1)( k + 1) 2 = 1 + 1 (k + 1)(k + 2) 2 = 1 + 1 (k + 1)((k + 1) + 1) 2 เพราะฉะนน้ั P(k + 1) เปนจรงิ โดยอปุ นยั เชิงคณติ ศาสตร จะได P(n) เปนจริง ทุกคา n ∈ N เพราะฉะนน้ั an =1+ 1 n(n + 1) ทุกคา n ∈ N † 2 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

96 Mathematical Induction 76. กําหนดให an = an−1 + n(n - 1), a1 = 3 จงแสดงวา an = n(n2 − 1) +3 3 76. แนวคิด ให P(n) แทนขอความ “ an = n(n2 − 1) +3” 3 (1) จงแสดงวา P(1) เปน จรงิ เพราะวา 1(12 − 1) +3=3= a1 เพราะฉะน้ัน P(1) เปนจรงิ 3 (2) จงแสดงวา ถา P(k) แลว P(k + 1) เปนจรงิ สมมติ P(k) เปนจรงิ เม่อื k ≥ 1 ak+1 = ak + (k + 1)((k + 1) - 1) = ak + k(k + 1) = ( k(k2 − 1) + 3) + k(k + 1) (P(k) เปนจรงิ ⇒ ak = k(k2 − 1) + 3) 3 3 = ( k(k2 − 1) + k(k + 1)) + 3 3 = 1 (k + 1)(k(k - 1) + 3k) + 3 3 = 1 (k + 1)( k2 + 2k) + 3 3 = (k + 1)((k + 1)2 − 1) + 3 3 เพราะฉะน้นั P(k + 1) เปน จริง โดยอปุ นยั เชิงคณติ ศาสตร จะได P(n) เปนจรงิ ทกุ คา n ∈ N เพราะฉะนนั้ an = n(n2 − 1) + 3 ทุกคา n ∈ N † 3 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 97 † 77. กําหนดให an = 3 an−1 - 2, a0 = 0 จงแสดงวา an = - 3n + 1 77. แนวคดิ ให P(n) แทนขอความ “ an = - 3n + 1 ” (1) จงแสดงวา P(1) เปนจริง เพราะวา a1 = 3 a0 - 2 = -2 = - 31 + 1 เพราะฉะนนั้ P(1) เปน จริง (2) จงแสดงวา ถา P(k) เปนจริง เมือ่ k ≥ 1 แลว P(k + 1) เปน จริง สมมติ P(k) เปน จรงิ เมอ่ื k ≥ 1 ak +1 = 3 a(k +1)−1 - 2 = 3ak - 2 (P(k) เปนจรงิ ⇒ ak = - 3k + 1) = 3(- 3k + 1) - 2 = - 3k+1 + 1 เพราะฉะนั้น P(k + 1) เปนจริง โดยอปุ นยั เชงิ คณิตศาสตร จะได P(n) เปนจริง ทุกคา n ∈ N เพราะฉะน้นั an = - 3n + 1 ทกุ คา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

98 Mathematical Induction 78. กําหนดให an = an −1 + 3n2 , a1 = 3 จงแสดงวา an = n(n + 1)(2n + 1) 2 78. แนวคิด ให P(n) แทนขอความ “ an = n(n + 1)(2n + 1) ” 2 (1) จงแสดงวา P(1) เปน จริง เพราะวา 1(1 + 1)(2(1) + 1) =3= a1 เพราะฉะนนั้ P(1) เปน จริง 2 (2) จงแสดงวา ถา P(k) แลว P(k + 1) เปนจริง สมมติ P(k) เปนจริง เม่อื k ≥ 1 ak+1 = ak + 3(k + 1) 2 = k(k + 1)(2k + 1) + 3(k + 1) 2 (P(k) เปน จรงิ ⇒ ak = k(k + 1)(2k + 1) ) 2 2 = k(k + 1)(2k + 1) + 6(k + 1)2 2 = 1 (k + 1)(2 k2 + k + 6k + 6) 2 = 1 (k + 1)(2 k2 + 7k + 6) 2 = 1 (k + 1)(k + 2)(2k + 3) 2 = (k + 1)((k + 1) + 1)(2(k + 1) + 1) 2 เพราะฉะนนั้ P(k + 1) เปนจริง โดยอุปนยั เชิงคณติ ศาสตร จะได P(n) เปน จรงิ ทุกคา n ∈ N เพราะฉะนน้ั an = n(n + 1)(2n + 1) ทุกคา n ∈ N † 2 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 99 79. กําหนดให an = 2 an−1 + n, a0 = 1 จงแสดงวา an = 3( 2n ) - n - 2 79. แนวคดิ ให P(n) แทนขอ ความ “ an = 3( 2n ) - n - 2 ” (1) จงแสดงวา P(1) เปนจริง เพราะวา a1 = 2 a0 + 1 = 2(1) + 1 = 3 = 3( 21) - 1 - 2 = 6 - 1 - 2 = 3 เพราะฉะนน้ั P(1) เปน จริง (2) จงแสดงวา ถา P(k) เปนจริง เมือ่ k ≥ 1 แลว P(k + 1) เปน จรงิ สมมติ P(k) เปน จริง เมอ่ื k ≥ 1 ak+1 = 2 ak + (k + 1) (P(k) เปน จริง ⇒ ak = 3( 2k ) - k - 2) = 2(3( 2k ) - k - 2) + (k + 1) = 3( 2k+1) - 2k - 4 + k + 1 = 3( 2k+1) - (k + 1) - 2 เพราะฉะนั้น P(k + 1) เปน จรงิ โดยอปุ นัยเชงิ คณติ ศาสตร จะได P(n) เปนจรงิ ทุกคา n ∈ N เพราะฉะนน้ั an = 3( 2n ) - n - 2 ทุกคา n ∈ N † รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั