induction_01Dec2015

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

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

102 Mathematical Induction 82. S1 , S2 , S3 , … เปน ลําดบั ของเซต { 1 }, { 2, 3 }, { 4, 5, 6 }, … การหาผลบวกของสมาชกิ ในเซต Sn 82. แนวคดิ จํานวนสมาชิกของ S1 ∪ S2 ∪ S3 ∪ … ∪ Sk =1+2+3+…+k = k (k + 1) 2 เพราะฉะนนั้ สมาชกิ ตัวแรกของ Sk +1 คือ k (k + 1) + 1 2 และสมาชกิ ตวั สดุ ทา ยของ Sk +1 คอื k (k + 1) + k+ 1 2 Sk +1 ={ k (k + 1) + 1, k (k + 1) + 2, …, k (k + 1) + (k + 1) } 2 2 2 ผลบวกของสมาชิกใน Sk+1 = k + 1 ( k (k + 1) + 1 + k (k + 1) + (k + 1)) 22 2 = (k + 1) ( k2 + k + 1 + k2 + k + k + 1) 2 22 22 = (k + 1) ( k2 + 2k + 2) 2 = (k + 1) ((k + 1) 2 + 1) 2 เพราะฉะน้นั ผลบวกของสมาชกิ ใน Sn คอื n ( n2 + 1) † 2 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 103 † 83. จงแสดงวา 2n < n! ทกุ คา n ≥ 4 83. แนวคดิ ให P(n) แทนขอความ “ 2n < n! ” (1) การแสดงวา P4) เปน จรงิ เพราะวา 24 = 16 < 24 = 4! เพราะฉะนน้ั P(1) เปนจรงิ (2) การแสดงวา ถา P(k) เปนจรงิ เม่อื k ≥ 1 แลว P(k + 1) เปนจริง สมมติ P(k) เปนจรงิ เมื่อ k ≥ 1 เพราะฉะนนั้ 2k < k! เพราะวา 2k+1 < 2( 2k ) < 2(k!) < (k + 1)(k!) = (k + 1)! เพราะฉะนน้ั P(k + 1) เปน จรงิ โดยอปุ นัยเชิงคณติ ศาสตร จะได P(n) เปน จรงิ ทกุ คา n ≥ 4 เพราะฉะนั้น 2n < n! ทกุ คา n ≥ 4 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

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

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

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

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

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

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

110 Mathematical Induction 90. จงแสดงวา 24 | (713( 93n−2 ) + 15) ทุกคา n ∈ N † 90. แนวคิด ให P(n) แทนขอความ “ 24 | (713( 93n−2 ) + 15) ” (1) การแสดงวา P(1) เปน จรงิ เพราะวา 713( 93(1)−2 ) + 15 = 713(9) + 15 = 6432 = 268(24) เพราะฉะน้นั P(1) เปน จริง (2) การแสดงวา ถา P(k) เปนจรงิ เม่ือ k ≥ 1 แลว P(k + 1) เปน จรงิ สมมติ P(k) เปน จรงิ เมอ่ื k ≥ 1 713( 93(k+1)−2 ) + 15 = 713( 93 ( 93k−2 )) + 15 = 93 (713( 93k−2 ) + 15) - 15( 93 - 1) = 729(713( 93k−2 ) + 15) - 24(455) เพราะวา (P(k) เปน จรงิ ⇒ 24 | (713( 93k−2 ) + 15)) และ 24 | 24(455) เพราะฉะนัน้ 24 | (713( 93(k+1)−2 ) + 15) เพราะฉะนน้ั P(k + 1) เปนจรงิ โดยอุปนัยเชงิ คณิตศาสตร จะได P(n) เปน จริง ทกุ คา n ∈ N เพราะฉะนน้ั 24 | (713( 93n−2 ) + 15) ทุกคา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

Mathematical Induction 111 91. จงแสดงวา 24 | (16n + 93n−2 - 1) ทกุ คา n ∈ N 91. แนวคิด ให P(n) แทนขอความ “ 24 | (16n + 93n−2 - 1) ” (1) การแสดงวา P(7) เปน จรงิ เพราะวา 16 + 9 - 1 = 24 เพราะฉะน้นั P(1) เปน จรงิ (2) การแสดงวา ถา P(k) เปนจริง เมอ่ื k ≥ 1 แลว P(k + 1) เปน จรงิ สมมติ P(k) เปน จรงิ เมื่อ k ≥ 1 + - 116k +1 93(k +1)−2 = 16(16k ) + 93 ( 93k−2 ) - 1 = 16(16k ) + 729( 93k−2 ) - 1 = 16(16k + 93k−2 - 1) - 16( 93k−2 ) + 729( 93k−2 ) + 16 - 1 = 16(16k + 93k−2 - 1) + 713( 93k−2 ) + 15 เพราะวา (P(k) เปน จรงิ ⇒ 24 | (16k + 93k−2 - 1)) และ 24 | (713( 93k−2 ) + 15) (จากขอ 92) เพราะฉะนัน้ 24 | (16k+1 + 93(k+1)−2 - 1) เพราะฉะนัน้ P(k + 1) เปนจรงิ โดยอุปนยั เชงิ คณิตศาสตร จะได P(n) เปน จรงิ ทุกคา n ∈ N เพราะฉะนั้น 24 | (16n + 93n−2 - 1) ทกุ คา n ∈ N † รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

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

Mathematical Induction 113 † 93. จงแสดงวา 11 | ((8)102n + (6)102n−1 + 9) ทุกคา n ∈ N 93. แนวคิด ให P(n) แทนขอความ “ 11 | ((8)102n + (6)102n−1 + 9) ” (1) การแสดงวา P(1) เปน จริง เพราะวา (8)102 + (6)102−1 + 9 = 800 + 60 + 9 = 869 = 79(11) เพราะฉะนัน้ P(1) เปน จริง (2) การแสดงวา ถา P(k) เปนจริง เมือ่ k ≥ 1 แลว P(k + 1) เปน จรงิ สมมติ P(k) เปนจริง เมือ่ k ≥ 1 (8)102(k+1) + (6)102(k+1)−1 + 9 = 100(8)102k + 100(6)102k−1 + 9 = 100(8)102k + 100(6)102k−1 + 9 = 100((8)102k + (6)102k−1 + 9) - 900 + 9 = 100((8)102k + (6)102k−1 + 9) - 891 เพราะวา (P(k) เปน จริง ⇒ 11 | ((8)102k + (6)102k−1 + 9))) และ 11 | 891 เพราะฉะน้นั 11 | ((8)102(k+1) + (6)102(k+1)−1 + 9 ) เพราะฉะนน้ั P(k + 1) เปน จริง โดยอปุ นัยเชงิ คณิตศาสตร จะได P(n) เปนจรงิ ทุกคา n ∈ N เพราะฉะน้นั 11 | ((8)102n + (6)102n−1 + 9) ทุกคา n ∈ N รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

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

Mathematical Induction 115 95. จงแสดงวา 14 + 24 + 34 + ... + (n - 1) 4 < n5 ทุกคา n ∈ N 5 95. แนวคิด ให P(n) แทนขอ ความ “ 14 + 24 + 34 + ... + (n - 1) 4 < n5 ” 5 (1) การแสดงวา P(1) เปนจรงิ เพราะวา 04 < 15 เพราะฉะนน้ั P(1) เปน จริง 4 (2) การแสดงวา ถา P(k) เปน จรงิ เมอ่ื k ≥ 1 แลว P(k + 1) เปนจรงิ สมมติ P(k) เปนจรงิ เมอ่ื k ≥ 1 เพราะฉะน้นั 14 + 24 + 34 + ... + (k - 1) 4 < k5 5 14 + 24 + 34 + ... + (k - 1) 4 + k4 < k5 + k4 (บวก k4 สองขา ง) 5 = 1 ( k5 + 5 k4 ) 5 ≤ 1 ( k5 + 5 k4 + 10 k3 + 5 k2 + 1) 5 = (k + 1)5 5 เพราะฉะนั้น P(k + 1) เปน จรงิ โดยอปุ นยั เชงิ คณิตศาสตร จะได P(n) เปนจริง ทุกคา n ∈ N เพระฉะน้ัน 14 + 24 + 34 + ... + (n - 1) 4 < n5 ทุกคา n ∈ N † 5 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

116 Mathematical Induction 96. จงแสดงวา n5 < 14 + 24 + 34 + ... + n4 ทุกคา n ∈ N 5 96. แนวคิด ให P(n) แทนขอความ “ n5 < 14 + 24 + 34 + ... + n4 ” 5 (1) การแสดงวา P(1) เปนจรงิ เพราะวา 15 < 14 เพราะฉะน้ัน P(1) เปนจรงิ 5 (2) การแสดงวา ถา P(k) เปนจริง เมอื่ k ≥ 1 แลว P(k + 1) เปน จรงิ สมมติ P(k) เปนจรงิ เมื่อ k ≥ 1 เพราะฉะน้นั k5 < 14 + 24 + 34 + ... + k4 ... (1) 5 (จาก (1)) (k + 1)5 = 1 ( k5 + 5 k4 + 10 k3 + 10 k2 + 5k + 1) † 55 = k5 + 1 (5 k4 + 10 k3 + 10 k2 + 5k + 1) 5 5 < 14 + 24 + 34 + … + k4 + 1 (5 k4 + 10 k3 + 10 k2 + 5k + 1) 5 < 14 + 24 + 34 + … + k4 + 1 (5 k4 + 10 k3 + 10 k2 + 5k + 5) 5 = 14 + 24 + 34 + … + k4 + ( k4 + 2 k3 + 2 k2 + k + 1) ≤ 14 + 24 + 34 + … + k4 + ( k4 + 4 k3 + 6 k2 + 4k + 1) = 14 + 24 + 34 + … + k4 + (k + 1) 4 เพราะฉะนัน้ P(k + 1) เปนจริง โดยอุปนยั เชิงคณติ ศาสตร จะได P(n) เปน จริง ทุกคา n ∈ N เพระฉะนน้ั n5 < 14 + 24 + 34 + ... + n4 ทุกคา n ∈ N 5 รองศาสตราจารย์ ดาํ รงค์ ทพิ ยโ์ ยธา ภาควชิ าคณติ ศาสตรแ์ ละวทิ ยาการคอมพวิ เตอร์ คณะวทิ ยาศาสตร์ จฬุ าลงกรณ์มหาวทิ ยาลยั

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

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

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

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