🔙 Quay lại trang tải sách pdf ebook Phương Pháp Quy Nạp Toán Học Ebooks Nhóm Zalo NGUY ˜ÊN H ˜U,U ÐIÊ,N PHU,O,NG PHAP ´ QUY NAP TO ´OC .AN H . (T ´ai b ,an lâ`n thu´,hai) NHA XU `´ÂT B,AN GIAO D ´ UC. ©ebook 2.0 c,ua cuô´n sach nguyên gô ´ ´c tu`,b,an in, cac b ´ an tham . kh,ao, cho y kiê ´ ´n sai sot v ´ a l ` o`,i khuyên tai b ´,an. Moi liên h . ê. Tac gi ´,a: Nguyên H ˜ u˜,u Ðiê,n Ðiên tho . ai: 0989061951 . Email: [email protected] Email: [email protected] Web: https://nhdien.wordpress.com Web: https://vietex.blog.fc2.com/ Ch.iu tr ´ach nhiêm xuâ .´t b ,an: Giam´ dô¯´c Ngô Trâ`n ai´ Tô,ng biên tâp V . u Du ˜,o,ng Thuy. Biên tâp n . ôi dung: . Ngô Long Hâu. Biên tâp t ´ai b .,an: Tru,o,ng Công Thanh ` Tr`ınh b `ay b`ıa: Ta Tr . ong Tr .´ı Chê´ b,an: Nguên H ˜ u˜,u Ðiê,n 51 GD − 0005/796-00 Ma sô ˜ ´: 8H663M0 LO`,I NOI Ð ´ `ÂU Môt phu .,o,ng phap râ ´ ´t manh trong to . an h ´ oc d . ung nghiên c ` u´,u va ch ` u´,ng minh cac gi ´,a thuyê´t la nguyên l ` y quy n ´ ap to . an h ´ oc. C . o´ vô sô´ cac v ´ ´ı du trong c . ac môn h ´ oc.,o,chu,o,ng tr`ınh phô,thông dung ` nguyên ly n´ ay` dê¯,diên gi ˜,ai va mô t `,a. Nhu,ng dê¯,hiê,u thâ´u d¯ao vê ´ ` ky thu ˜ ât. ap d ´ ung trong h . oc t . âp, s . ang t ´ ao râ .´t ´ıt sach ´ du¯,o.,c ban t ` o´,i. Tai li ` êu nu .,o´,c ngoai c ` ung ˜ d¯a c ˜ o m´ ôt sô .´ sach n ´ oi riêng vê ´ ` vâ´n dê¯` nay, theo tôi c ` ung chu ˜,a dâ¯`y d¯,u va râ ` ´t nhiê`u ngu,o`,i kho tiê ´ ´p xuc´ du¯,o.,c vo´,i tai li ` êu n . ay. Tôi m ` anh d . an thu th . âp v . a kh `,ao sat nguyên ´ ly quy n ´ ap to . an h ´ oc theo m . oi kh .´ıa canh v . a minh h ` oa b .`ang c ˘ ac´ bai t ` âp trong chu .,o,ng tr`ınh phô,thông. Ðây la lo ` ai s . ach cung câ ´ ´p va th `,ao luân nh . u˜,ng phu,o,ng phap h ´ oc t . âp v . a gi `,ai bai t ` âp cho c . ac´ ban yêu th .´ıch toan h ´ oc, c . ac thâ ´ `y cô giao, sinh viên c ´ ac tru ´,o`,ng su, pham v . a c ` ac b ´ an.,o,lo´,p hoc sinh gi .,oi lam t ` ai li ` êu tiê .´p tuc ph . at´ triê,n. Chu,o,ng dâ¯`u xem xet c ´ ac kh ´ ´ıa canh c .,ua nguyên ly quy n ´ ap. toan h ´ oc. Do khuôn khô .,c,ua cuô´n sach ch ´ ung tôi ´ d¯a không ch ˜ u´,ng minh c .an k ˘ e s ˜ u.,tu,o,ng du¯,o,ng c,ua nguyên ly quy n ´ ap to . an h ´ oc v . a` tiên dê¯` thu´,tu.,; su.,tu,o,ng du¯,o,ng c,ua cac d ´ ang nguyên l . y quy n ´ ap. toan h ´ oc..v.v. Chu .,o,ng hai kh,ao sat c ´ ac kh ´ ´ıa canh k . y thu ˜ ât c .,ua nguyên ly n´ ay. T ` u`,chu,o,ng ba môi chu ˜,o,ng dung kh `,ao sat c ´ ac b ´ ai` tâp vê .` môt lo . ai ch .,u dê¯` ch,ı ap d ´ ung phu .,o,ng phap quy n ´ ap to . an´ hoc nhu .,: Sô´ hoc, D . ay sô ˜ ´, H`ınh hoc, Ða th . u´,c, Tô,ho.,p, Liên phân sô´ ... Tai li ` êu ch . ung tôi tham kh ´,ao co h´ an v . a ch `´ac c ˘ on nhiê ` `u bai` tâp hay chu .,a noi t ´ o´,i, ho .ac c ˘ o sai s ´ ot trong thê ´,hiên. y tu ´,,o,ng mong ban. d¯oc cho . y kiê ´ ´n s,u,a dô¯,i va bô `,sung. Moi liên h . ê g.,u,i vê` d¯.ia ch,ı: Nha xuâ ` ´t b,an Giao d ´ uc, 81 Trâ .`n Hu,ng Ðao, H . a N` ôi.. Ha N` ôi, th . ang 5 n ´ am 2000 ˘ Tac gi ´,a 3 CHU,O,NG 1 NGUYÊN LY QUY N ´ AP TO . AN H ´ OC. 1.1. Suy diên v ˜ a quy n ` ap.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Nguyên ly quy n ´ ap to . an h ´ oc.. . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3. Giai do¯ an quy n . ap v . a gi `,a thiê´t quy nap.. . . . . . . . . . . . . . 8 1.4. Hai bu,o´,c c,ua nguyên ly quy n ´ ap to . an h ´ oc.. . . . . . . . . 15 1.5. Khi nao d ` ung phu `,o,ng phap quy n ´ ap.. . . . . . . . . . . . . . . . 19 1.6. Bai t ` âp.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.1. SUY DI˜ÊN VA QUY N ` AP. Ðê,minh hoa hai kh . ai ni ´ êm râ .´t hay g .ap trong th ˘ u.,c tê´ la suy ` diên v ˜ a quy n ` ap, ta lâ .´y câu ca dao Viêt Nam ai c . ung biê ˜ ´t: "Sô´ cô c´o me c ´o cha . Me cô . d `an b `a cha cô ¯ d `an ông ¯ Sô´ cô c´o vo.,c´o chô`ng Sinh con d⯠`u l`ong ch,˘ang g ´ai th`ı trai." Ðây la câu ` do¯ an c ´,ua ông thâ`y boi, ta ´ d¯a biê ˜ ´t thâ`y boi ch ´,ı do¯ an m ´ o thôi, nhu `,ng ông thâ`y boi trong câu ca dao n ´ ay râ ` ´t khôn la d ` ung m ` ôt kh .,ang ˘ d¯.inh luôn luôn d¯ung ´ "ai c ˜ung c´o me, c ´o cha" .. Tu`,d¯o d´ u` ap d ´ ung cho ngu .,o`,i d꯴n boi c ´ u thê .,nao c ` ung ˜ d¯ung luôn, ´ ngh˜ıa la kh `,ang ˘ d¯.inh riêng cung ˜ d¯ung. Bu ´,o´,c suy luân t . u`,kh,ang ˘ d¯.inh chung ap d ´ ung cho nh . u˜,ng kh,ang ˘ d¯.inh riêng biêt g . oi l . a` ph´ep 1.1. Suy diên v ˜ a quy n ` ap. 5 suy di˜ên. Phep suy di ´ ên˜,o,v´ı du trên l . a luôn ` d¯ung v ´ o´,i hai câu dâ¯`u, nhu,ng co thê ´,sai ,o,hai câu sau. Trong toan h ´ oc râ .´t hay dung ph ` ep´ suy diên, ch ˜,ang h ˘ an, nê .´u hai goc trong c ´,ua môt tam gi . ac´ d¯a cho ˜ la` 30◦ va` 70◦, th`ı diê ¯`u kh,ang ˘ d¯.inh sau d¯ung: " G ´ oc th ´ u´,ba c,ua tam giac´ d¯a cho l ˜ a` 80◦". Mênh . dê¯` chung ,o,dây l ¯ a: "Tô `,ng cac g ´ oc´ trong c,ua môt tam gi . ac l ´ a` 180◦". Bây gio`,ta d¯oc l . ai chuy . ên cu .,o`,i dân gian Viêt nam: . "Bô´n ông thâ`y boi r ´,u nhau di xem voi. T ¯ o´,i chô voi ˜ d¯u´,ng, bô´n thâ`y boi chen v ´ ao, s ` o`,tân tay xem con voi n . o thê ´ ´ nao. Vê ` ` to´,i cho.,, bô´n thâ`y hop nhau b .`ınh phâ,m. Thâ`y so`,du¯,o.,c cai v ´ oi voi n ` oi: ´ - Tu,,o,ng voi la l .´am, t ˘ e ra ch ´,ı giô´ng con d¯,ıa cu.,c lo´,n. Tôi so`,vao` no uô ´ ´n cong ngu,o`,i lai.. Thâ`y ôm ph,ai cai chân, v ´ ôi c . ai: ˜ - Voi ch,ı hêt nhu .,cai c ´ ôt nh . a thôi. Tôi ôm v ` ao v ` u`,a tay cai´ côt c . ai. ´ Thâ`y n´am ph ˘,ai cai tai voi, chê: ´ - Cac b ´ ac ch ´,ı noi m ´ o. Con voi th ` ât ra t . u.,a nhu,cai qu ´ at. to tu,o´,ng. Thâ`y tum ph ´,ai cai´ duôi voi, cu ¯,o`,i khâ,y: - Ba bac n ´ oi sai c ´,a. Tôi d¯a t ˜ um n ´ o trong tay, th ´ `ı d¯ung l ´ a m` ôt. cai chô ´,i xê,d¯ai.. Không ai ch.iu ai, bô´n thâ`y to tiê´ng cai nhau ô ˜ `n ao m ` ôt. goc ch ´ o.,... " 6 Chu,o,ng 1. Nguyên ly quy n ´ ap to . an h ´ oc. Môi ông thâ ˜ `y boi´ dê¯`u dung kh `,ang ˘ d¯.inh riêng c,ua m`ınh dê¯, do¯ an, ph ´ at biê ´,u kh,ang ˘ d¯.inh chung. Bu,o´,c suy luân t . u`,kh,ang ˘ d¯.inh riêng tiê´n to´,i phat biê ´,u kh,ang ˘ d¯.inh chung du¯,o.,c goi l . a` ph´ep quy nap.. Kh,ang ˘ d¯.inh chung ,o,dây l ¯ a "con v ` ât. d¯o l ´ a con voi". Nhu `,vây. 4 ông thâ`y boi´ dê¯`u phat biê ´,u kh,ang ˘ d¯.inh chung sai. Ch´ac c ˘ o m´ ôt. ông nao` d¯o s ´ ang m ´´at th ˘ `ı se˜ d¯ung. Ta thâ ´ ´y r `ang phu ˘,o,ng phap quy ´ nap c . o thê ´,du¯,a d꯴n kê´t qu,a nhân. d¯.inh sai. Phu,o,ng phap quy n ´ ap. râ´t hay du¯,o.,c dung trong nghiên c ` u´,u khoa hoc, nhâ .´t la to ` an h ´ oc.. Nhu,vây ch . ung ta ph ´,ai hiê,u phu,o,ng phap quy n ´ ap thê .´ nao` dây ¯ va` ap d ´ ung thê .´ nao` dê¯,nhân. du¯,o.,c mênh . dê¯` kh,ang ˘ d¯.inh d¯ung. ´ 1.2. NGUYÊN LY QUY N ´ AP TO . AN H ´ OC. Ðê,ng´an g ˘ on ta k . y hi ´ êu m . ôt kh .,ang ˘ d¯.inh toan h ´ oc l . a` P(x),,o, dây ¯ x la m` ôt biê .´n sô´. Ngu,o`,i ta thu,o`,ng du¯,a vê` dang m . ênh . dê¯` " Vo´,i moi. x (trong môt t . âp. S nao` d¯o), ´ P(x)". Trong cuô´n sach n ´ ay` ta lâ´y x = n la nh ` u˜,ng sô´tu.,nhiên1, S la t ` âp c . ac sô ´ ´tu.,nhiên (bao gô`m toan b ` ô c . ac sô ´ ´ nguyên du,o,ng). Ta s ,u,dung m . ôt t .´ınh châ´t râ´t quan trong c .,ua tâp sô .´tu.,nhiên, thu,o`,ng ngu,o`,i ta công nhân nhu ., môt tiên . dê¯` (du¯,o.,c goi l . a tiên ` dê¯` thu´,tu.,). Tiên dê¯`: Trong môi t ˜ âp h . o.,p kh ´ac rông c ˜,ua nhu˜,ng sô´tu.,nhiên c´o môt phâ .`n t,u,nh ,o nhâ´t. Cho môi sô ˜ ´ tu.,nhiên n u´,ng vo´,i môt kh .,ang ˘ d¯.inh P(n). V´ı du,. vo´,i 1 ta cho tu,o,ng u´,ng vo´,i kh,ang ˘ d¯.inh P(1): "sô´ 1 la m` ôt sô .´ l,e", sô´ 2 cho tu,o,ng tu´,ng vo´,i P(2): " sô´ 2 la m` ôt sô .´ ch˜an"; ... B ˘`ang ˘ phu,o,ng phap nhu ´,vây ch . ung ta t ´ ao ra d . ay kh ˜,ang ˘ d¯.inh riêng 1Trong sach n ´ ay khi n ` oi´ d꯴n sô´tu.,nhiên, ta hiê,u d¯o l ´ a sô ` ´tu.,nhiên khac sô ´ ´ 0. 1.2. Nguyên ly quy n ´ ap to . an h ´ oc. 7 P(1), P(2), . . . , P(n), . . . . Nguyên ly quy n ´ ap to . an h ´ oc cho ta m . ôt. phu,o,ng phap kiê ´,m tra kh,ang ˘ d¯.inh P(n) d¯ung ho ´ .ac sai v ˘ o´,i moi. n. Nguyên ly quy n ´ ap to . an h ´ oc. du¯,o.,c thê,hiên qua . d¯.inh ly sau: ´ Ð.inh ly 1.1. ´ Cho n0 l `a môt sô .´ nguyên du,o,ng v `a P(n) l `a mênh . dê¯ ` c ´o ngh˜ıa vo´,i moi sô .´ tu.,nhiên n ≥ n0. Nê´u A) P(n0) l `a d ´ung v `a ¯ B) Nê´u P(k) d ´ung, th`ı ¯ P(k + 1) c ˜ung d ´ung v ¯ o´,i môi sô ˜ ´ tu.,nhiên k ≥ n0, khi d ´o m ¯ ênh . dê¯ ` P(n) d ´ung v ¯ o´,i moi sô .´ tu.,nhiên n ≥ n0. Chu´,ng minh. Ta se ch ˜ u´,ng minh b`ang ph ˘,an chu´,ng. Gi,a s,u,ngu,o.,c lai, m . ênh . dê¯` kh,ang ˘ d¯.inh P(n) trong Ð.inh ly´ 1.1 không d¯ung v ´ o´,i môt sô .´tu.,nhiên n ≥ n0 nao` d¯o. Ngh ´ ˜ıa la tô ` `n tai m. ôt sô .´tu.,nhiên m ≥ n0, ma` P(m) không d¯ung. Ta lâ ´ ´y sô´ tu.,nhiên m nh,o nhâ´t ma` P(m) không d¯ung ( ´ diê ¯`u nay th ` u.,c hiên. du¯,o.,c do tiên dê¯` thu´, tu.,). Theo diê ¯`u kiên A), ta c . o bâ ´ ´t d¯,ang th ˘ u´,c m > n0, tu`,d¯o suy ra ´ m − 1 ≥ n0. Tu`,bâ´t d¯,ang th ˘ u´,c vu`,a lâp v . a c ` ach ch ´ on sô .´ tu.,nhiên m suy ra P(m − 1) la` d¯ung, nhu ´,ng no không k ´ eo theo ´ du¯,o.,c P(m) d¯ung cho sô ´ ´tiê´p theo m = (m − 1) + 1. Ðiê`u nay tr ` ai v ´ o´,i gi,a thiê´t B). J Xuâ´t phat t ´ u`, mênh . dê¯` kh,ang ˘ d¯.inh vo´,i cac tru ´,o`,ng ho.,p riêng, ch,ang h ˘ an nhu .,cac sô ´ ´ 1, 2, ho .ac 3 c ˘ o thê ´,nâ,y sinh gi,a thiê´t mênh . dê¯` d¯ung v ´ o´,i moi sô .´tu.,nhiên. Sau d¯o´ dê¯,chu´,ng minh gi,a thiê´t c,ua ta vu`,a xây du.,ng ngu,o`,i ta ly lu ´ ân theo nguyên l . y quy n ´ ap to . an´ hoc. Phu .,o,ng phap ch ´ u´,ng minh nhu,vây g . oi l . a` phu,o,ng ph ´ap quy nap to ´an h . oc.. Theo d¯.inh ly trên phu ´,o,ng phap n ´ ay gô ` `m hai bu,o´,c, thu´,nhâ´t ta kiê,m tra kh,ang ˘ d¯.inh môt t .´ınh châ´t vo´,i n = n0, goi. 8 Chu,o,ng 1. Nguyên ly quy n ´ ap to . an h ´ oc. la` Bu,o´,c co,s,o,; sau d¯o ch ´ u´,ng minh r `ang nê ˘ ´u vo´,i môi˜ k ≥ n0, P(k) tho,a man t ˜ ´ınh châ´t d¯a biê ˜ ´t, th`ı suy ra P(k + 1) cung c ˜ o t ´ ´ınh châ´t â´y, goi l . a` Bu,o´,c quy nap.. Kê´t luân l . a` P(n) co t ´ ´ınh châ´t d¯a cho v ˜ o´,i moi. n ≥ n0. Cach ch ´ u´,ng minh theo quy nap to . an h ´ oc l . a tr ` anh ´ cho ta ph,ai kiê,m tra vô han bu .,o´,c cac kh ´,ang ˘ d¯.inh c,ua mênh . dê¯`. 1.3. GIAI ÐOAN QUY N . AP V . A GI `,A THI´ÊT QUY NAP. Phu,o,ng phap quy n ´ ap to . an h ´ oc râ .´t hay du¯,o.,c ap d ´ ung trong . nghiên cu´,u va t ` `ım toi trong to ` an h ´ oc, c . ac ng ´ anh khoa h ` oc kh . ac. ´ Ðê,hiê,u cach ´ ap d ´ ung phu .,o,ng phap quy n ´ ap cho . dâ¯`y d¯,u, ta xem xet m ´ ôt sô .´ v´ı du sau . dây nhu ¯, môt ph . ep´ "suy luân c ´o l ´y" . ma G. ` Polya d¯a˜ dê¯` câp. . . Cho tru,o´,c môt sô .´ tu.,nhiên n. H ˜ay t`ım tô,ng c ´ac sô´ tu., Vı d´ u 1.1. nhiên 1, 2, . . . , n. Lo`,i gi,ai. Ta ky hi ´ êu. Sn la tô `,ng ph,ai t`ım, ngh˜ıa la` Sn = 1 + 2 + · · · + n. (1.1) Ta hy vong l . a t ` `ım ra công thu´,c ng´an g ˘ on. dê¯,t´ınh tô,ng trên, công thu´,c d¯o gi ´ up ta t ´ ´ınh nhanh, gon ho .,n la ph `,ai thu.,c hiên lâ .`n lu,o.,t cac ph ´ ep c ´ ông trong tô .,ng. Ta cung biê ˜ ´t dây l ¯ a câ ` ´p sô´ công, nê .´u ban. d¯oc. d¯a biê ˜ ´t vê` câ´p sô´nay, th ` `ı ta co thê ´,co ngay công th ´ u´,c t´ınh tô,ng. Nhu,ng,o,dây ta muô ¯´n minh hoa qu . a tr ´ `ınh ap d ´ ung nguyên . ly quy n ´ ap to . an h ´ oc nên nh . u˜,ng diê ¯`u d¯a biê ˜ ´t vê` câ´p sô´ công ta b .,o qua, coi nhu,chu,a biê´t. Ta t´ınh tô,ng Sn tu`,d¯,ang th ˘ u´,c (1.1) vo´,i môt v . ai sô ` ´ tu.,nhiên liên tiê´p, ch,ang h ˘ an b .´at˘ dâ¯`u tu`,1. Nhu˜,ng kê´t qu,a t´ınh toan c ´ ac´ tru,o`,ng ho.,p riêng ta xê´p vao b `,ang 1.3. Giai do¯ an quy n . ap v . a gi `,a thiê´t quy nap. 9 n 1 2 3 4 5 6 Sn 1 3 6 10 15 21 Muc. d¯´ıch c,ua ta la t ` `ım du¯,o.,c quy luât chung (kh .,ang ˘ d¯.inh chung), vo´,i b,ang trên, môi sô ˜ ´tu.,nhiên ,o,hang trên trong b `,ang cho tu,o,ng u´,ng vo´,i cac sô ´ ´,o,hang du `,o´,i. T`ım ra quy luât c .,ua môt b . ai to ` an ph ´ u. thuôc v . ao râ ` ´t nhiê`u yê´u tô´: su.,kheo l ´ eo trong quan s ´ at; s ´ u.,nhay. c,am du.,do¯ an v ´ a kiê `,m tra c,ua ta; tu`,cac kinh nghi ´ êm. d¯a tr ˜,ai qua trong t´ınh toan c ´ ac b ´ ai to ` an tu ´,o,ng tu.,, tu`,kh,a nang liên h ˘ ê b . ai` toan tu ´,o,ng tu.,vo´,i diê ¯`u kiên m . o´,i, v.v... Trên b,ang trên ta dê thâ ˜ ´y quy luât: T .´ıch c,ua hai sô´ liên tiê´p ,o,hang trên b ``ang 2 lâ ˘ `n sô´ dâ¯`u tiên tu,o,ng u´,ng,o,hang du `,o´,i. Thât. vây, 1.2=2.1, 2.3=2.3, 3.4=2.6, 4.5=2.10, 5.6=2.15. Nhu .,vây. giai do¯ an quy n . ap. c,ua chung ta ´ d¯a th ˜ anh công: T ` `ım ra quy luât v . o´,i cac tru ´,o`,ng ho.,p riêng n = 1, 2, 3, 4, 5, 6. Tiê´p tuc m . ôt c . ach t ´ u.,nhiên la m`,o,rông quy lu . ât trên cho b .,ang sô´ vo´,i cac sô ´ ´ tu.,nhiên bâ´t ky. Ta ` du¯,a ra gi,a thiê´t th´ıch ho.,p vo´,i quy luât v . u`,a t`ım du¯,o.,c. Ð.at˘ 1 + 2 + · · · + n =n(n + 1) 2. (1.2) Môt gi .,a thiê´t ta d¯a l ˜ am nhu `,vây. du¯,o.,c goi l . a` gi,a thiê´t quy nap.. Nhu,ng câu h,oi d¯.at ra l ˘ a` d¯,ang th ˘ u´,c (1.2) co´ d¯ung v ´ o´,i moi. n = 1, 2, . . . hay không? Ro r ˜ ang nê ` ´u (1.2) d¯ung v ´ o´,i moi sô .´ tu.,nhiên th`ı b`ang c ˘ ach thay ´ n b`ang ˘ n + 1 chung ta s ´ e c ˜ o´ d¯,ang th ˘ u´,c 1 + 2 + · · · + n + (n + 1) = (n + 1)(n + 2) 2. (1.3) Trai l ´ ai, gi .,a thiê´t (1.2) la` d¯ung v ´ o´,i moi. n = 1, 2, . . ., nê´u 1) no´ d¯ung v ´ o´,i n = 1 va 2) n ` o´ d¯ung v ´ o´,i môi sô ˜ ´ k suy ra cung ˜ d¯ung ´ 10 Chu,o,ng 1. Nguyên ly quy n ´ ap to . an h ´ oc. vo´,i c,a k + 1. Ðiê`u nay không c ` o c ´ ach n ´ ao kh ` ac l ´ a ph `,ai ap d ´ ung . nguyên ly quy n ´ ap to . an h ´ oc. Ngh .˜ıa la ch ` ung ta ph ´,ai kiê,m tra nhu˜,ng diê ¯`u kiên A) v . a B) c `,ua Ð.inh ly´ 1.1. Bu,o´,c co,s,o,: vo´,i n = 1, công thu´,c (1.2) d¯ung (n ´ o c ´ on` d¯ung cho c ´,a n = 2, 3, 4, 5, 6). Bu,o´,c quy nap.: Bây gio`,chung ta ch ´ u´,ng minh công thu´,c (1.2) d¯ung ´ cho c,a diê ¯`u kiên B). V . o´,i muc. d¯´ıch d¯o ta gi ´,a thiê´t công thu´,c (1.2) d¯ung v ´ o´,i môt sô .´ n = k ≥ 1 nao` d¯o v ´ a s ` e ch ˜ u´,ng minh d¯,ang th ˘ u´,c (1.2) d¯ung v ´ o´,i n = k + 1. Ta biê´n dô¯,i 2+ (k + 1) = (k + 1)(k + 2) 1 + 2 + · · · + k + (k + 1) = k(k + 1) 2. Kê´t qu,a la ( ` 1.2) d¯ung v ´ o´,i n = k + 1. Theo nguyên ly quy n ´ ap to . an´ hoc công th . u´,c (1.2) d¯ung v ´ o´,i moi. n = 1, 2, . . . J Tom l ´ ai, qua v .´ı du. do¯,n gi,an trên ta thâ´y cac bu ´,o´,c qua tr ´ `ınh t`ım toi v ` a ch ` u´,ng minh nguyên ly quy n ´ ap to . an h ´ oc.. . T´ınh tô,ng Vı d´ u 1.2. Sn =1 a(a + 1)+1 (a + 1)(a + 2)+ · · · +1 (a + (n − 1))(a + n) vo´,i a 6= 0, −1, −2, . . . ; n = 1, 2, . . . Lo`,i gi,ai. Viêc tru .,o´,c tiên ta ph,ai t`ım ra công thu´,c gi,a thiê´t quy nap cho tô .,ng trên. Ta t´ınh S1 =1 a(a + 1), (a + 1)(a + 2)=1 a(a + 1)+1 S2 = S1 +1 S3 = S2 +1 (a + 2)(a + 3)=3 a(a + 3), (a + 1)(a + 2)=2 a(a + 2), 1.3. Giai do¯ an quy n . ap v . a gi `,a thiê´t quy nap. 11 S4 = S3 +1 (a + 3)(a + 4)=4 a(a + 4). Chung ta c ´ o thê ´,du¯,a ra gi,a thiê´t r `ang ˘ Sn =n a(a + n). (1.4) Bu,o´,c co,s,o,: Nhu,d¯a kiê ˜,m tra,o,trên. Bu,o´,c quy nap.: Gi,a thiê´t (1.4) d¯ung v ´ o´,i sô´tu.,nhiên n = k nao` d¯o.´ Khi d¯o´ Sk+1 = Sk +1 (a + k)(a + k + 1)=k a(a + k)+1 (a + k)(a + k + 1) a + k.k2 + (a + 1)k + a =1 a(a + k + 1). Nhu,ng k2 + (a + 1)k + a = (a + k)(k + 1), suy ra a + k.(a + k)(k + 1) Sk+1 =1 a(a + k + 1)=k + 1 a(a + k + 1). Tu`,kê´t qu,a vu`,a t´ınh va bu `,o´,c co,s,o,suy ra gi,a thiê´t quy nap ( . 1.4) la` d¯ung v ´ o´,i moi sô .´tu.,nhiên n ≥ 1. J . T´ınh tô,ng Vı d´ u 1.3. Sn =2 1 − a2 +2 1 + a4 + · · · +2n 1 + a2n vo´,i n = 1, 2, . . . ; |a| 6= 1. 1 + a2 +4 Lo`,i gi,ai. Ta phân t´ıch: Sô´ lu,o.,ng sô´ hang c .,ua tô,ng la` n + 1; tru`,sô´ hang . dâ¯`u tiên, con l ` ai c . ac sô ´ ´ hang kh . ac´ dê¯`u co d ´ ang . 2k 1 + a2k(k = 1, 2, . . . , n). Ta t´ınh 12 Chu,o,ng 1. Nguyên ly quy n ´ ap to . an h ´ oc. S1 =2 1 − a2 +2 1 + a2 =4 1 − a4, 1 + a4 =4 1 − a4 +4 S2 = S1 +4 S3 = S2 +8 1 + a8 =8 1 + a4 =8 1 − a8, 1 − a8 +8 1 + a8 =16 1 − a16 . Do 4 = 22, 8 = 23 va` 16 = 24tu`,cac biê ´,u thu´,c c,ua S1, S2 va` S3 co thê ´,du¯,a ra gi,a thiê´t: Sn =2n+1 1 − a2n+1, (n = 1, 2, . . .). (1.5) Bu,o´,c co,s,o,: Vo´,i n = 1, công thu´,c (1.5) d¯ung nhu ´,d¯a kiê ˜,m tra ,o,trên. Bu,o´,c quy nap.: Gi,a s,u,(1.5) d¯ung v ´ o´,i sô´tu.,nhiên n = k nao` d¯o.´ Khi d¯o´ 1 + a4 + · · · +2k Sk+1 =2 1 − a2 +2 1 + a2 +4 1 − a2k+1 +2k+1 1 + a2k +2k+1 1 + a2k+1 =2k+1 1 + a2k+1 =2k+2 1 − a2k+2. Ð,ang th ˘ u´,c (1.5) cung ˜ d¯ung v ´ o´,i n = k + 1. Nhu,vây, t . u`,nguyên ly´ quy nap to . an h ´ oc. d¯,ang th ˘ u´,c (1.5) d¯ung v ´ o´,i moi. n ≥ 1. J . T´ınh tô,ng c,ua n sô´ l,e tu.,nhiên d⯠`u tiên. Vı d´ u 1.4. Lo`,i gi,ai. Ta ky hi ´ êu tô .,ng ph,ai t`ım la` Sn: Sn = 1 + 3 + 5 + · · · + (2n − 1). Ðê,xây du.,ng gi,a thiê´t quy nap to . an h ´ oc ta t .´ınh tô,ng,o, môt sô .´ gia´ tr.i du¯,o.,c liêt kê trong b .,ang sau: 1.3. Giai do¯ an quy n . ap v . a gi `,a thiê´t quy nap. 13 n 1 2 3 4 5 6 Sn 1 4 9 16 25 36 Bây gio`,phu thu . ôc v . ao s ` u.,quan sat c ´,ua ta va kinh nghi ` êm trên . kê´t qu,a riêng dê¯,du.,do¯ an m ´ ênh . dê¯` tô,ng quat chung. D ´ ê thâ ˜ ´y cac sô ´ ´,o,hang ` Sn dê¯`u la sô ` ´ ch´ınh phu,o,ng: S1 = 12, S2 = 22, S3 = 32, S4 = 42, S5 = 52, S6 = 62. Nhu,vây ta c . o thê ´,du¯,a ra gi,a thiê´t chung la` Sn = n2. (1.6) Ta se ch ˜ u´,ng minh (1.6) d¯ung v ´ o´,i moi sô .´tu.,nhiên n. Bu,o´,c co,s,o,: Vo´,i n = 1, tô,ng ch,ı co m´ ôt sô .´ hang . Sn = 1; biê,u thu´,c n2 = 1 vo´,i n = 1, nhu,vây ( . 1.6) d¯ung. ´ Bu,o´,c quy nap.: Gi,a s,u,(1.6) d¯ung v ´ o´,i n = k, (Sk = k2). ta se˜ chu´,ng minh (1.6) d¯ung v ´ o´,i n = k + 1: Sk+1 = (k + 1)2. Thât v . ây,. Sk+1 = Sk + (2k + 1) = k2 + (2k + 1) = (k + 1)2. J Ta xet thêm m ´ ôt v .´ı du n. u˜,a theo cach l ´ am c `,ua G. Polya. . T´ınh tô,ng b`ınh phu,o,ng c,ua n sô´ tu.,nhiên d⯠`u tiên. Vı d´ u 1.5. Lo`,i gi,ai. Ta tiê´n hanh t ` `ım công thu´,c cho gi,a thiê´t quy nap. Ð . .at˘ Tn = 12 + 22 + · · · + n2. Ta hay t ˜ `ım môt sô .´ gia tr ´ .i c,ua tô,ng khi cho n = 1, 2, . . . , 6. n 1 2 3 4 5 6 Tn 1 5 14 30 55 91 Nh`ın vao b `,ang trên ta kho c ´ o thê ´,t`ım ra quy luât chung cho . Tn. Vo´,i thông tin ´ıt,oi nhu,vây không cho kê .´t qu,a g`ı, nhu,ng vo´,i kinh 14 Chu,o,ng 1. Nguyên ly quy n ´ ap to . an h ´ oc. nghiêm ta c . o thê ´,liên hê v . o´,i cac v ´ ´ı du. d¯a gi ˜,ai va so s ` anh nh ´ u˜,ng day sô ˜ ´trong v´ı du 1.1 v . a ch ` `ıa khoa t ´ `ım ra quy luât chung trong . b,ang sau: n 1 2 3 4 5 6 Tn 1 5 14 30 55 91 Sn 1 3 6 10 15 21 Tn Sn 1 1 5 3 14 6 30 10 55 15 91 21 Dong cuô ` ´i cung trong b `,ang ta co thê ´,viê´t lai:.11=33,53,146=73, 10 =93,5515 =113,9121 =133. Bây gio`,ta co thê ´,du¯,a ra gi,a thiê´t 30 3. Tu`,kê´t qu,a v´ı du 1.1 ta c . o´ Sn=2n + 1 r `ang ˘Tn Tn =2n + 1 3.n(n + 1) 2ho .ac l ˘ a` 12 + 22 + · · · + n2 =n(n + 1)(2n + 1) 6. (1.7) Ta chu´,ng minh b`ang quy n ˘ ap to . an h ´ oc cho công th . u´,c (1.7) d¯ung v ´ o´,i moi sô .´tu.,nhiên n. Bu,o´,c co,s,o,: B`ang c ˘ ach xây d ´ u.,ng trên, d¯,ang th ˘ u´,c (1.7) d¯ung v ´ o´,i n = 1. Bu,o´,c quy nap.: Gi,a s,u,(1.7) d¯ung v ´ o´,i sô´tu.,nhiên n = k nao` d¯o. Ta ´ se ch ˜ u´,ng minh r `ang n ˘ o c ´ ung ˜ d¯ung v ´ o´,i n = k + 1, ngh˜ıa la` 12 + 22 + · · · + k2 + (k + 1)2 =(k + 1)(k + 2)(2k + 3) 6. Thât v . ây,. Tk+1 = Tk + (k + 1)2 =k(k + 1)(2k + 1) 6+ (k + 1)2 1.4. Hai bu,o´,c c,ua nguyên ly quy n ´ ap to . an h ´ oc. 15 = (k + 1)k(2k + 1) + 6(k + 1) 6=(k + 1)(k + 2)(2k + 3) 6. Nhu,vây b . ai to ` an´ d¯a gi ˜,ai xong. J 1.4. HAI BU,O´,C C,UA NGUYÊN LY QUY N ´ AP TO . AN H ´ OC. Nhu,ta d¯a biê ˜ ´t nguyên ly quy n ´ ap to . an h ´ oc gô .`m hai phâ`n, viêc kiê .,m tra c,a hai câ`n du¯,o.,c tôn trong khi . ap d ´ ung nguyên l . y.´ Nê´u ta b,o di m¯ ôt trong hai . diê ¯`u kiên kiê .,m tra d¯o, th ´ `ı ta se nh ˜ ân. du¯,o.,c nhu˜,ng kê´t luân sai. Thông qua c . ac v ´ ´ı du sau . dê¯,minh hoa. va hiê `,u diê ¯`u nay ho `,n. . Chu´,ng minh r `˘ang moi sô .´ tu.,nhiên dê¯ `u b `˘ang sô´ tu., Vı d´ u 1.6. nhiên liê`n sau. Lo`,i gi,ai. Ta chu´,ng minh theo phu,o,ng phap quy n ´ ap to . an h ´ oc.. Gi,a thiê´t r `ang m ˘ ênh . dê¯` kh,ang ˘ d¯.inh d¯ung v ´ o´,i sô´ tu.,nhiên n = k nao` d¯o, ngh ´ ˜ıa la` k = (k + 1). (1.8) Chung ta s ´ e ch ˜ u´,ng minh d¯,ang th ˘ u´,c sau d¯ung ´ (k + 1) = (k + 2). (1.9) Thât v . ây, Theo gi .,a thiê´t quy nap ( . 1.8) công hai vê .´ d¯,ang th ˘ u´,c vo´,i 1, ta nhân. du¯,o.,c k + 1 = (k + 1) + 1 = k + 2. Nhu,vây, kh .,ang ˘ d¯.inh d¯ung v ´ o´,i n = k th`ı no´ d¯ung v ´ o´,i n = k + 1, do d¯o m´ ênh . dê¯` bai to ` an´ d¯ung v ´ o´,i moi. n. J Hê qu .,a c,ua bai to ` an n ´ ay l ` a tâ ` ´t c,a cac sô ´ ´ tu.,nhiên dê¯`u b`ang ˘ nhau. Ðiê`u nay th ` ât vô l . y, v ´ ây c . ach ch ´ u´,ng minh sai ,o,dâu? D ¯ ê˜ 16 Chu,o,ng 1. Nguyên ly quy n ´ ap to . an h ´ oc. dang thâ ` ´y ngay trong chu´,ng minh ap d ´ ung nguyên l . y quy n ´ ap. toan h ´ oc nhu .,ng b,o qua kiê,m tra tru,o`,ng ho.,p n = 1. Ðiê`u kiên A) v . a B) trong Ð ` .inh ly´ 1.1 co m´ ôt. y ngh ´ ˜ıa d¯.ac bi ˘ êt:. Ðiê`u kiên A) t . ao ra co .,s,o,dê¯,thu.,c hiên quy n . ap. . Ðiê`u kiên B) . du¯,a ra nguyên t´ac cho vi ˘ êc m .,o,rông t . u.,d¯ông vô . han trên co .,s,o,diê ¯`u kiên A); nguyên t .´ac˘ di t ¯ u`,tru,o`,ng ho.,p riêng nay sang tru `,o`,ng ho.,p riêng khac; t ´ u`,k d꯴n k + 1. ,O,v´ı du. .1.6 ta không kiê,m tra diê ¯`u kiên A) c .,ua Ð.inh ly´ 1.1, nên không tao ra . co,s,o,dê¯,thu.,c hiên quy n . ap., v`ı vây không c . o´ ngh˜ıa g`ı khi thu.,c hiên kiê .,m tra diê ¯`u kiên B) c .,ua Ð.inh ly´ 1.1, thu.,c châ´t la không c ` o g ´ `ı dê¯,m,o,rông c .,a. Ta xet thêm v ´ ´ı du:. . Chu´,ng minh r `˘ang vo´,i moi sô .´tu.,nhiên n bâ´t d¯,˘ang thu´,c Vı d´ u 1.7. sau d ´ung ¯ 2n > 2n + 1. (1.10) Lo`,i gi,ai. Gi,a thiê´t bâ´t d¯,ang th ˘ u´,c (1.10) d¯ung v ´ o´,i n = k, vo´,i k la` môt sô .´tu.,nhiên nao` d¯o, ngh ´ ˜ıa la ta c ` o´ 2k > 2k + 1. (1.11) Ta se ch ˜ u´,ng minh bâ´t d¯,ang th ˘ u´,c (1.10) d¯ung v ´ o´,i n = k + 1 2k+1 > 2(k + 1) + 1. (1.12) Thât v . ây,. 2kla m` ôt sô .´ không nh,o ho,n 2 vo´,i moi sô .´tu.,nhiên khac´ không. Ta công vê .´trai c ´,ua (1.11) vo´,i 2k va c ` ông vê .´ph,ai c,ua (1.11) vo´,i 2. Ta nhân. du¯,o.,c 2k + 2k > 2k + 1 + 2. Ngh˜ıa la` 2k+1 > 2(k + 1) + 1. 1.4. Hai bu,o´,c c,ua nguyên ly quy n ´ ap to . an h ´ oc. 17 Bai to ` an´ d¯a gi ˜,ai xong. J Tâ´t nhiên v´ı du n. ay c ` ung m ˜´ac sai lâ ˘ `m nhu,v´ı du tru .,o´,c không kiê,m tra Bu,o´,c co,s,o,. Thu.,c châ´t c,ua cach ch ´ u´,ng minh trên la bâ ` ´t d¯,ang th ˘ u´,c (1.10) d¯ung v ´ o´,i n = k + 1, nê´u no´ d¯ung v ´ o´,i n = k. Ðiê`u nay không suy ra bâ ` ´t d¯,ang th ˘ u´,c d¯ung v ´ o´,i ´ıt nhâ´t môt gi . a tr ´ .i c,ua n, chu´,chu,a noi t ´ o´,i vo´,i moi sô .´tu.,nhiên n. Nhu,ng ta co thê ´,th ,u,vo´,i n = 1 ho .ac˘ n = 2 bâ´t d¯,ang th ˘ u´,c (1.10) sai. Vo´,i n ≥ 3 bâ´t d¯,ang th ˘ u´,c (1.10) d¯ung. Gi ´ a tr ´ .i sô´tu.,nhiên nh,o nhâ´t n = 3 bâ´t d¯,ang th ˘ u´,c (1.10) d¯ung ( ´ diê ¯`u kiên A) v . o´,i n0 = 3 va` l.ap l ˘ ai c . ach ch ´ u´,ng minh ,o,trên tu`,gi,a thiê´t (1.10) d¯ung v ´ o´,i n = k suy ra no´ d¯ung v ´ o´,i n = k + 1 (diê ¯`u kiên B). V .`ı vây theo nguyên l . y´ quy nap to . an h ´ oc ta c . o kê ´ ´t luân: Bâ .´t d¯,ang th ˘ u´,c (1.10) d¯ung v ´ o´,i moi sô .´ tu.,nhiên n ≥ 3 (chu´,không ph,ai vo´,i moi sô .´ tu.,nhiên nhu, dê¯` bai ra). ` Trong viêc. ap d ´ ung phu .,o,ng phap quy n ´ ap to . an h ´ oc m . a ch `,ı chu´,ng minh diê ¯`u kiên A) c .,ua Ð.inh ly´ 1.1 th`ı mo´,i ch,ı du¯,a ra du¯,o.,c co,s,o,dê¯,quy nap ch . u´,không co nguyên t ´´ac n ˘ ao` dê¯,m,o,rông co .,s,o, d¯o (nhu ´,d¯.inh ly l ´ o´,n Fermat). Ta xet m ´ ôt sô .´ v´ı du:. . Chu´,ng minh r `˘ang nhu˜,ng gi ´a tr.i c,ua h `am sô´ Vı d´ u 1.8. f(n) = n2 − n + 41 vo´,i n = 0, 1, . . . l `a nhu˜,ng sô´ nguyên tô´. Lo`,i gi,ai. Ta t´ınh f(0) = 1, f(1) = 41, f(2) = 43, f(3) = 47, f(4) = 53, f(5) = 61, f(6) = 71, f(7) = 83, f(8) = 97, f(9) = 113. Ta co thê ´,t´ınh toan tiê ´ ´p tuc gi . a tr ´ .i c,ua f(n) cho to´,i n = 40, tâ´t c,a gia tr ´ .i nay` dê¯`u la sô ` ´ nguyên tô´. Nhu,ng vo´,i n = 41 ta co´ f(41) = 412 − 41 + 41 = 412. Kê´t qu,a f(41) không ph,ai la sô ` ´ nguyên tô´, nên kê´t luân c .,ua bai to ` an l ´ a không ` d¯ung. ´ J 18 Chu,o,ng 1. Nguyên ly quy n ´ ap to . an h ´ oc. Nhu,vây ta thâ .´y môt m . ênh . dê¯` co thê ´,d¯ung v ´ o´,i 40 tru,o`,ng ho.,p riêng, nhu,ng không d¯ung v ´ o´,i moi tru .,o`,ng ho.,p noi chung. ´ . Ða thu´,c xn − 1, vo´,i n l `a sô´ tu.,nhiên du,o,ng. Ða thu´,c Vı d´ u 1.9. n `ay liên quan dê¯ ´n b `ai to ´an h`ınh hoc chia . du¯,o`,ng tr`on ra n phâ`n b `˘ang nhau, nên da th ¯ u´,c n `ay du¯,o.,c râ´t nhiê`u l˜ınh vu.,c to ´an hoc. nghiên cu´,u v `a dê¯ ` câp. dê¯ ´n. Ð.˘ac biêt c ´ac nh `a to ´an h . oc quan tâm . to´,i vâ´n dê¯ ` phân t´ıch da th ¯ u´,c n `ay ra c ´ac thu`,a sô´ l `a c ´ac da th ¯ u´,c vo´,i hê sô .´ nguyên ±1, liêu. diê ¯ `u d´o c`on ¯ d ´ung v ¯ o´,i moi. n? Lo`,i gi,ai. B`ang c ˘ ach khai triê ´,n cac tru ´,o`,ng ho.,p riêng, cac nh ´ a` toan h ´ oc nh . ân thâ .´y r `ang tâ ˘ ´t c,a cac h ´ ê sô .´trong cac th ´ u`,a sô´ du¯,o.,c khai triê,n co gi ´ a tr ´ .i tuyêt. dô¯´i không qua 1. Ch ´,ang h ˘ an, . x − 1 = x − 1, x2 − 1 = (x − 1)(x + 1), x3 − 1 = (x − 1)(x2 + x + 1), x4 − 1 = (x − 1)(x + 1)(x2 + 1), x5 − 1 = (x − 1)(x4 + x3 + x2 + x + 1), x6 − 1 = (x − 1)(x + 1)(x2 + x + 1)(x2 − x + 1). Nhu˜,ng cô´ g´ang ch ˘ u´,ng minh diê ¯`u nghi ngo`,d¯ung v ´ o´,i moi. n c,ua cac nh ´ a to ` an h ´ oc không th . anh công. M ` ôt th . o`,i gian sau, nha to ` an´ hoc Nga V. Ivanov (n . am 1941) ch ˘,ı ra r `ang v ˘ o´,i da th ¯ u´,c xn − 1, diê ¯`u nghi ngo`,ch,ı d¯ung v ´ o´,i cac tru ´,o`,ng ho.,p nh,o ho,n 105. Nhu,ng vo´,i n = 105, môt th . u`,a sô´ c,ua x105 − 1 la` x48 + x47 + x46 − x43 − x42 − 2x41 − x40 − x39 + x36+ +x35 + x34 + x33 + x32 + x31 − x28 − x26 − x24 − x22 − x20 + x17 +x16 + x15 + x14 + x13 + x12 − x9 − x8 − 2x7 − x6 + x5 + x2 + x + 1. 1.5. Khi nao d ` ung phu `,o,ng phap quy n ´ ap. 19 Thu`,a sô´ nay không c ` o t ´ ´ınh châ´t c,ua cac´ da th ¯ u´,c ma c ` ac nh ´ a to ` an´ hoc muô .´n. J . Chu´,ng minh r `˘ang vo´,i moi sô .´ n mênh . dê¯ ` sau dây ¯ Vı d´ u 1.10. d ´ung: "Nê ¯ ´u a v `a b l `a nhu˜,ng sô´tu.,nhiên du,o,ng, m `a max(a, b) = n, th`ı a = b". Lo`,i gi,ai. Bu,o´,c co,s,o,: Vo´,i môi˜ n ky hi ´ êu. An la m` ênh . dê¯` c,ua bai` toan´ d¯a cho. R ˜ o r ˜ ang ` A1 la` d¯ung, v ´ `ı nê´u max(a, b) = 1, th`ı hai sô´ a va` b ph,ai trung nhau v ` a b ``ang 1 (do ˘ a va` b la sô ` ´tu.,nhiên). Bu,o´,c quy nap.: Gi,a s,u, Akla` d¯ung. Nê ´ ´u a va` b la nh ` u˜,ng sô´tu.,nhiên sao cho max(a, b) = k + 1. Ta xet hai sô ´ ´ a1 = a − 1 va` b1 = b − 1, khi d¯o´ max(a1, b1) = k, tu`,d¯o suy ra ´ a1 = b1, v`ı gi,a thiê´t Akla` d¯ung, do ´ d¯o´ a = b, ngh˜ıa la` Ak+1 cung ˜ d¯ung. Theo nguyên l ´ y quy ´ nap to . an h ´ oc. An d¯ung v ´ o´,i moi sô .´tu.,nhiên n. Hê qu .,a: Cho a va` b la hai sô ` ´ tu.,nhiên bâ´t ky. Ta t ` ´ınh du¯,o.,c max(a, b) = k, ma` k la m` ôt sô .´tu.,nhiên. Theo v´ı du trên . An d¯ung ´ vo´,i moi. n, th`ı no c ´ ung ˜ d¯ung v ´ o´,i Ak. Tu`,d¯o suy ra ´ a = b. Ngh˜ıa la` tâ´t c,a cac sô ´ ´tu.,nhiên dê¯`u b`ang nhau. Th ˘ ât vô l . y!´ Trong v´ı du trên c . ach ch ´ u´,ng minh sai ,o,dâu? Ta xem l ¯ ai to . an` bô c . ach ch ´ u´,ng minh va nguyên l ` y quy n ´ ap to . an h ´ oc.. Bu,o´,c quy nap.trong chu´,ng minh không nh´ac t ˘ o´,i diê ¯`u k ≥ 1, khi bu,o´,c quy nap chuyê .,n tiê´p tu`, Ak sang Ak+1. Thu.,c tê´trong t´ınh toan ch ´ u´,ng minh không d¯,am b,ao k ≥ 1. J 1.5. KHI NAO D ` UNG PHU `,O,NG PHAP QUY N ´ AP. Phu,o,ng phap quy n ´ ap to . an h ´ oc râ .´t co t ´ ac d ´ ung trong nghiên . cu´,u, du.,do¯ an kê ´ ´t qu,a va ch ` u´,ng minh kiê,m nghiêm kê .´t qu,a. 20 Chu,o,ng 1. Nguyên ly quy n ´ ap to . an h ´ oc. Nhu,ng nhiê`u khi ch´ınh phu,o,ng phap quy n ´ ap to . an h ´ oc l . am vi ` êc. chu´,ng minh dai d ` ong, biê ` ´n dô¯,i phu´,c tap gây râ .´t nhiê`u kho kh ´ an˘ trong chu´,ng minh. Nhiê`u bai to ` an gi ´,ai b`ang phu ˘,o,ng phap quy ´ nap c . o thê ´,gi,ai b`ang m ˘ ôt phu .,o,ng phap kh ´ ac. Ch ´ ´ınh G. Polya co´ noi: "Nhiê ´ `u bai to ` an ch ´ u´,ng minh b`ang quy n ˘ ap to . an h ´ oc c . o thê ´, chu´,ng minh b`ang c ˘ ach kh ´ ac, c ´ ach kh ´ ac´ d¯o n´`am trong ch ˘ ´ınh cach ´ chu´,ng minh quy nap to . an h ´ oc khi ta phân t .´ıch ky n˜ ôi dung ch . u´,ng minh". Trong toan h ´ oc ngu .,o`,i ta hay dung k ` y hi ´ êu. ∑ la m` ôt tô .,ng. Thu,o`,ng tô,ng co d ´ ang . Aα + Aα+1 + · · · + Aβ (α va` β la nh ` u˜,ng sô´ nguyên)va` du¯,o.,c viê´tβ∑ Ak(d¯oc l . a tô `,ng c,ua Ak, k chay t . u`,α d꯴n β). Nhu,vây. k=α Aα + Aα+1 + · · · + Aβ = β ∑ k=α Ak k goi l . a` ch ,ı sô´ c,ua tô,ng, con` α va` β la gi ` a tr ´ .i dâ¯`u va gi ` a tr ´ .i cuô´i c,ua ch,ı sô´ k. Môi sô ˜ ´ hang bên tr . ai c ´,ua d¯,ang th ˘ u´,c la` d¯ung v ´ o´,i môt. gia tr ´ .i k (k = α, α + 1, . . . , β). V´ı du. n∑ k=1 k2 = 12 + 22 + · · · + n2,(n ≥ 1), n+1 ∑ k=−1 102k = 10−2 + 100 + 102 + · · · + 102(n+1),(n ≥ −2). Phep lâ ´ ´y tô,ng co nh ´ u˜,ng t´ınh châ´t sau: Nê´u cho a va` b la nh ` u˜,ng sô´, ta co c ´ ac´ d¯,ang th ˘ u´,c β ∑ k=α aAk = a β ∑ k=α Ak, 1.5. Khi nao d ` ung phu `,o,ng phap quy n ´ ap. 21 β ∑ k=α (aAk + bBk) = a β ∑ k=α Ak + b β ∑ k=α Bk. Ky hi ´ êu tô .,ng không phu thu . ôc v . ao ch `,ı sô´, nhu,ng phu thu . ôc v . ao` gia tr ´ .i ban dâ¯`u va gi ` a tr ´ .i cuô´i cung ` β ∑ k=α Ak = β ∑ i=α Ai = β−α ∑ i=0 Aα+i Tr,o,lai nh . u˜,ng v´ı du.,o,phâ`n tru,o´,c, trong qua tr ´ `ınh t´ınh toan´ quy nap t .´ınh tô,ng 12 + 22 + · · · + n2 =n∑ k=1 k2 B`ang c ˘ ach ´ ap d ´ ung t .´ınh châ´t c,ua ky hi ´ êu tô .,ng va công th ` u´,c tô,ng cac sô ´ ´tu.,nhiênn∑ k=1 k =n(n + 1) 2,(n ≥ 1). Thât v . ây, d . ê thâ ˜ ´y n∑ k=0 (k + 1)3 −n∑ k=0 k3 = (n + 1)3. Vê´trai c ´,ua d¯,ang th ˘ u´,c trên co thê ´,biê,n dô¯,i n∑ k=0 (k + 1)3 −n∑ k=0 k3 =n∑ k=0 [(k + 1)3 − k3] =n∑ k=0 (3k2 + 3k + 1) = 3 n∑ k=1 k2 + 3n∑ k=1 k + n∑ k=0 1. Nhu,vây t . u`,cac´ d¯,ang th ˘ u´,c trên rut ra ´ (n + 1)3 = 3n∑ k=1 k2 + 3n(n + 1) 2+ (n + 1), Chuyê,n vê´ va t ` ´ınh toan ta c ´ o´ n∑ k2 =13[(n + 1)3 − 3n(n + 1) 2− (n + 1)] = 16n(n + 1)(2n + 1). k=1 22 Chu,o,ng 1. Nguyên ly quy n ´ ap to . an h ´ oc. T´ınh tô,ng sau dây (b ¯ ai` . 1.2) n∑ k=1 1 (a + k − 1)(a + k), n = 1, 2, ..; a 6= 0, −1, −2, . . . Ta s ,u,dung . d¯,ang th ˘ u´,c sau 1 (a + k − 1)(a + k)=1 a + k − 1−1 a + k. Ð.at˘ bk =1 a + k, nhu,vây. n∑ k=1 1 (a + k − 1)(a + k)= n∑ k=1 (bk−1 − bk) = b0 − bn =1a−1 a + n=n a(a + n). Cuô´i cung ta nh ` ân. du¯,o.,c n∑ (a + k − 1)(a + k)=n 1 k=1 a(a + n). Vâ´n dê¯` c,ua phâ`n nay ta c ` on` dê¯` câp tiê .´p,o, Chu,o,ng 3. 1.6. BAI T ` ÂP. . 1.11. T´ınh tô,ng b`ang c ˘ ach xây d ´ u.,ng gi,a thiê´t va ch ` u´,ng minh b`ang quy n ˘ ap to . an h ´ oc c . ac tô ´,ng sau: a) Sn = 12 − 22 + · · · + (−1)n−1n2; b) Sn = 13 + 23 + · · · + n3; c) Sn = 1.1! + 2.2! + · · · + n.n!. . 1.12. Chu´,ng minh ´ıt nhâ´t b`ang hai c ˘ ach c ´ ac công th ´ u´,c sau: 1.6. Bai t ` âp. 23 a) 12 + 32 + · · · + (2n − 1)2 =13n(2n − 1)(2n + 1), n = 1, 2, . . . b) 1.2.3 + 2.3.4 + · · · + n(n + 1)(n + 2) = 14n(n + 1)(n + 2)(n + 3), n = 1, 2, . . . c) 11.2 +12.3 + · · · +1 n(n + 1)=n n + 1, n = 1, 2, . . . . 1.13. Cho n > 1 la sô ` ´tu.,nhiên. Ta d¯.at˘ x0 =1n; n − k(x0 + x1 + · · · + xk−1), k = 1, 2, . . . , n − 1. Hay t ˜ ´ınh tô,ng xk =1 x0 + x1 + · · · + xn−1. CHU,O,NG 2 KY THU ˜ ÂT PHU .,O,NG PHAP´ QUY NAP TO . AN H ´ OC. 2.1. Môt sô .´dang nguyên l . y quy n ´ ap to . an h ´ oc.. . . . . . . . . . . 24 2.2. Mênh . dê¯` trong nguyên ly quy n ´ ap to . an h ´ oc.. . . . . . . . 32 2.3. Bu,o´,c quy nap. du¯,o.,c xây du.,ng trên P(k) . . . . . . . . . . . . . 38 2.4. Bu,o´,c quy nap. du¯,o.,c xây du.,ng trên P(k + 1) . . . . . . . . . 42 2.5. Quy nap to . an h ´ oc v . a ph ` ep truy hô ´ `i . . . . . . . . . . . . . . . . . 45 2.6. Quy nap to . an h ´ oc v . a tô `,ng quat ho ´ a´ . . . . . . . . . . . . . . . . 54 2.7. Bai t ` âp.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.1. MÔT S . Ô D ´ ANG NGUYÊN L . Y QUY N ´ AP TO . AN H ´ OC. Ðiê`u kiên A) trong Ð . .inh ly´ 1.1 cho ta co,s,o, m,o,rông b .´at˘ dâ¯`u tu`,gia tr ´ .i n0. Ðiê`u kiên B) c .,ua Ð.inh ly´ 1.1 cho ta mênh . dê¯` kh,ang ˘ d¯.inh P(n) d¯ung v ´ o´,i n0 + 1, n0 + 2, . . .. Thu.,c tê´ nhiê`u khi trong bu,o´,c quy nap. ph,ai d¯oi h `,oi hai gia tr ´ .i n = k − 1 va` n = k c,ua mênh . dê¯`, dê¯,suy ra mênh . dê¯` d¯ung v ´ o´,i n = k + 1. Trong tru,o`,ng ho.,p nay` bu,o´,c co,s,o,ph,ai kiê,m tra không nhu˜,ng ch,ı vo´,i n0, ma c `,a vo´,i n0 + 1. Tô,ng quat ho ´,n ta co thê ´,phat biê ´,u lai. d¯.inh ly´,o,phâ`n tru,o´,c nhu,sau: 2.1. Môt sô .´ dang nguyên l . y quy n ´ ap to . an h ´ oc. 25 Ð.inh ly 2.1. ´ Cho p l `a sô´ nguyên du,o,ng v `a d ˜ay c ´ac mênh . dê¯ ` P(1), P(2), . . . , P(n), . . . nê´u A) P(1), P(2), . . . , P(p) l `a nhu˜,ng mênh . dê¯ ` d ´ung v `a ¯ B) Vo´,i môi sô ˜ ´tu.,nhiên k ≥ p c ´ac mênh . dê¯ ` P(k − p + 1), P(k − p + 2), . . . , P(k) d ´ung, suy ra m ¯ ênh . dê¯ ` P(k+1) c ˜ung d ´ung, ¯ th`ı mênh . dê¯ ` P(n) d ´ung v ¯ o´,i moi sô .´ nguyên du,o,ng n. Chu´,ng minh d¯.inh ly n ´ ay ho ` an to ` an l ` .ap l ˘ ai nhu ., Ð.inh ly´ 1.1. Sau dây ta x ¯ et m ´ ôt sô .´ v´ı du s .,u,dung d . ang Ð . .inh ly´ 2.1. . Cho v0 = 2, v1 = 3 v `a vo´,i môi sô ˜ ´ tu.,nhiên k c ´o d¯,˘ang Vı d´ u 2.1. thu´,c sau: vk+1 = 3vk − 2vk−1. Chu´,ng minh r `˘ang vn = 2n + 1. Lo`,i gi,ai. Bu,o´,c co,s,o,: Vo´,i n = 0 va` n = 1 kê´t luân b . ai to ` an´ d¯ung, ´ do diê ¯`u kiên b . ai` d¯a cho. ˜ Bu,o´,c quy nap.: Gi,a s,u,r `ang ˘ vk−1 = 2k−1 + 1; vk = 2k + 1, khi d¯o´ vk+1 = 3(2k + 1) − 2(2k−1 + 1) = 2k+1 + 1. Theo nguyên ly quy n ´ ap to . an h ´ oc d . ang Ð . .inh ly´ 2.1, suy ra vn = 2n + 1 d¯ung v ´ o´,i moi sô .´tu.,nhiên n. J . Cho x1 v `a x2 l `a nghiêm c .,ua phu,o,ng tr`ınh Vı d´ u 2.2. x2 − 27x + 14 = 0; n l `a môt sô .´tu.,nhiên bâ´t k`y. Chu´,ng minh r `˘ang tô,ng Sn = xn1 + xn2không chia hê´t cho 715. Lo`,i gi,ai. Theo công thu´,c Viet x1 + x2 = 27; x1x2 = 14. 26 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. Bu,o´,c co,s,o,: Cac sô ´ ´ S1 = 27; S2 = (x1 + x2)2 − 2x1x2 = 701 va` S3 = (x1 + x2)[(x1 + x2)2 − 3x1x2] = 27 · 687 dê¯`u không chia hê´t cho 715. Suy ra mênh . dê¯` c,ua bai to ` an´ d¯ung v ´ o´,i n = 1, 2, 3. Bu,o´,c quy nap.: Gi,a s,u, mênh . dê¯` d¯ung v ´ o´,i n = k − 2, n = k − 1, n = k, ta t´ınh xk+1 1 + xk+1 2 = (x1 + x2)(xk1 + xk2) − x1x2(xk−1 1 + xk−1 2) = (x1 + x2)[(x1 + x2)(xk−1 1 + xk−1 2)− − x1x2(xk−2 1 − xk−2 2)] − x1x2(xk−1 1 + xk−1 2) = 715(xk−1 1 + xk−1 2) − 378(xk−2 1 + xk−2 2). Do d¯o´ xk+1 1 + xk+1 2không chia hê´t cho 715, v`ı 378 không chia hê´t cho 715, noi c ´ ach kh ´ ac m ´ ênh . dê¯` d¯ung v ´ o´,i n = k + 1. J . Chu´,ng minh vo´,i moi sô .´thu.,c x > 0 v `a moi sô .´tu.,nhiên Vı d´ u 2.3. n bâ´t d¯,˘ang thu´,c sau d ´ung ¯ xn−4 +1 xn + xn−2 + xn−4 + · · · +1 xn−2 +1xn ≥ n + 1. (2.1) Lo`,i gi,ai. 1a) Vo´,i n = 1 bâ´t d¯,ang th ˘ u´,c (2.1) co d´ ang . x +1x≥ 2. (2.2) Bâ´t d¯,ang th ˘ u´,c (2.2) suy ra tu`,bâ´t d¯,ang th ˘ u´,c hiê,n nhiên: (x − 1)2 ≥ 0. 1b) Vo´,i n = 2 bâ´t d¯,ang th ˘ u´,c (2.1) co d´ ang . x2 + 1 +1x2 ≥ 3. (2.3) Bâ´t d¯,ang th ˘ u´,c (2.2) d¯ung v ´ o´,i moi. x > 0, vây n . o c ´ ung ˜ d¯ung v ´ o´,i x2, x2 +1x2 ≥ 2. 2.1. Môt sô .´ dang nguyên l . y quy n ´ ap to . an h ´ oc. 27 Công hai vê .´ c,ua bâ´t d¯,ang th ˘ u´,c sau cung v ` o´,i 1, ta nhân. du¯,o.,c (2.3). 2) Gi,a s,u,bâ´t d¯,ang th ˘ u´,c (2.1) d¯ung v ´ o´,i n = k, ma` k la m` ôt sô .´ tu.,nhiên nao` d¯o´ xk + xk−2 + xk−4 + · · · +1 xk−4+1 xk−2+1xk≥ k + 1, (2.4) ta se ch ˜ u´,ng minh khi d¯o bâ ´ ´t d¯,ang th ˘ u´,c (2.1) d¯ung v ´ o´,i n = k + 2, hay la` xk+2 + xk + xk−2 + · · · +1 xk−2+1xk+1 xk+2≥ k + 3. (2.5) Thât v . ây, trong ( . 2.2) thê´ x b,o,i xk+2, ta nhân. du¯,o.,c xk+2 +1 xk+2≥ 2. (2.6) Công vê .´ tu,o,ng u´,ng c,ua cac bâ ´ ´t d¯,ang th ˘ u´,c (2.4) va ( ` 2.6), ta se c ˜ o´ (2.5). Tom l ´ ai:. Bu,o´,c co,s,o,: Trong 1a) va 1b) ta ` d¯a ch ˜ u´,ng minh bâ´t d¯,ang th ˘ u´,c d¯ung cho ´ n = 1 va` n = 2. Bu,o´,c quy nap.: Trong 2) ta d¯a ch ˜ u´,ng minh tu`,gi,a thiê´t d¯ung ´ c,ua (2.1) vo´,i n = k suy ra no´ d¯ung v ´ o´,i n = k + 2. Kê´t qu,a la` + Tu`,1a) va 2) cho ta kh `,ang ˘ d¯.inh la bâ ` ´t d¯,ang th ˘ u´,c (2.1) d¯ung ´ vo´,i moi sô .´ l,e n. + Tu`,1b) va 2) cho ta kh `,ang ˘ d¯.inh la bâ ` ´t d¯,ang th ˘ u´,c (2.1) d¯ung ´ vo´,i moi sô .´ ch˜an˘ n. Nhu,vây, bâ .´t d¯,ang th ˘ u´,c (2.1) d¯ung v ´ o´,i moi sô .´tu.,nhiên n. J . Chu´,ng minh r `˘ang vo´,i moi sô .´ tu.,nhiên n d¯,˘ang thu´,c Vı d´ u 2.4. sau d ´ung: ¯ 28 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. a) b) 12 7.2n 17 7.2n − − 17 7.2n−1 12 7.2n−2 = 2n−1; = 2n+1, ,o,dây ¯ [a] l `a sô´ nguyên lo´,n nhâ´t nh ,o ho,n a. Lo`,i gi,ai. Bu,o´,c co,s,o,: Vo´,i n = 1, 2, 3 nhu˜,ng d¯,ang th ˘ u´,c trên d¯ung ´ b`ang c ˘ ach kiê ´,m tra tru.,c tiê´p. Bu,o´,c quy nap.: Gi,a thiê´t r `ang hai ˘ d¯,ang th ˘ u´,c d¯ung v ´ o´,i ba sô´ tu.,nhiên liên tiê´p k, k + 1, k + 2. Ta se ch ˜ u´,ng minh cac´ d¯,ang th ˘ u´,c trên d¯ung v ´ o´,i n = k + 3. 2a) Tu`,12 7.2k+3 =127(1 + 7)2k = 12.2k +127.2k; 17 7.2k+2 =177(1 + 7)2k−1 = 17.2k−1 +177.2k−1, suy ra 12 7.2k+3 − 17 7.2k+2 = 12.2k − 17.2k−1 + 12 72k − 17 72k−1 . Nhu,ng v`ı a) d¯ung v ´ o´,i n = k 12 7.2k+3 − 17 7.2k+2 = 12.2k − 17.2k−1 + 2k−1 = 2k+2. Vây. d¯,ang th ˘ u´,c a) d¯ung v ´ o´,i n = k + 3. 2b) Tu`,17 7.2k+3 = 17.2k +177.2k, 7.2k+1 = 12.2k−2 +127.2k−2, 12 suy ra 17 7.2k+3 − 12 7.2k+1 = 17.2k − 12.2k−2 + 17 72k − 12 7.2k−2 . 2.1. Môt sô .´ dang nguyên l . y quy n ´ ap to . an h ´ oc. 29 Nhu,ng v`ı b) vo´,i n = k, ta co´ 17 7.2k+3 − 12 7.2k+1 = 17.2k − 12.2k−2 + 2k+1 = 2k+4. Vây. d¯,ang th ˘ u´,c b) d¯ung v ´ o´,i n = k + 3. Theo nguyên ly quy n ´ ap to . an h ´ oc a), b) . d¯ung v ´ o´,i moi sô .´ tu., nhiên n. J . Chu´,ng minh r `˘ang Vı d´ u 2.5. un =αn+1 − βn+1 α − β, (2.7) α − β, u2 =α3 − β3 nê´uu1 =α2 − β2 α − β(α 6= β) v `a vo´,i môi sô ˜ ´ tu.,nhiên k > 2 c ´o d¯,˘ang thu´,c sau: uk = (α + β)uk−1 − αβuk−2. Lo`,i gi,ai. 1) Vo´,i n = 1 va` n = 2, (2.7) d¯ung do ´ diê ¯`u kiên. d¯a cho. ˜ 2) Gi,a s,u,d¯,ang th ˘ u´,c d¯ung v ´ o´,i n = k − 1 va` n = k − 2 uk−2 =αk−1 − βk−1 α − β, uk−1 =αk − βk α − β khi d¯o´ uk = (α + β)αk − βk α − β− αβαk−1 − βk−1 α − β=αk+1 − βk+1 α − β. J Môt d . ang nguyên l . y quy n ´ ap m . anh ho .,n nguyên ly quy n ´ ap ta . d¯a˜ biê´t cung râ ˜ ´t du¯,o.,c hay dung. ` Ð.inh ly 2.2. ´ Cho môt d ˜ay m . ênh . dê¯ ` P(1), P(2), . . . , P(n), . . . Nê´u 30 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. A) P(1) l `a kh,˘ang d¯.inh d ´ung, v `a ¯ B) vo´,i môi sô ˜ ´ tu.,nhiên k ≥ 1, nhu˜,ng kh,˘ang d¯.inh P(1), P(2), . . . , P(k) d ´ung suy ra kh ¯,˘ang d¯.inh P(k + 1) c ˜ung d ´ung, ¯ th`ı P(n) d ´ung v ¯ o´,i tâ´t c,a sô´ tu.,nhiên n ≥ 1. Dang n . ay kh ` ac v ´ o´,i cac d ´ ang tru .,o´,c la gi `,a thiê´t manh ho .,n,o, bu,o´,c quy nap.. Ta gi,a thiê´t tâ´t c,a kh,ang ˘ d¯.inh P(1), P(2), . . . , P(k) d¯ung suy ra ´ P(k + 1) cung ˜ d¯ung. D ´ ê d ˜ ang ch ` u´,ng minh hai cach ´ phat biê ´,u Ð.inh ly´ 1.1. va Ð` .inh ly´ 2.2 tu,o,ng du¯,o,ng nhau. Nhu,ng trong thu.,c tê´ ap d ´ ung v . ao b ` ai to ` an c ´ u thê .,dung Ð ` .inh ly´ 2.2 dê˜ gi,ai ho,n. . Chu´,ng minh r `˘ang nê´u x +1xl `a sô´ nguyên th`ı xn +1xn Vı d´ u 2.6. c ˜ung l `a sô´ nguyên vo´,i moi sô .´ tu.,nhiên du,o,ng n. Lo`,i gi,ai. Bu,o´,c co,s,o,: Khi n = 1 mênh . dê¯` hiê,n nhiên d¯ung. ´ Bu,o´,c quy nap.: Gi,a s,u,vo´,i moi sô .´ tu.,nhiên tu`,1 d꯴n k, xk +1xkla` nhu˜,ng sô´ nguyên. Ta câ`n chu´,ng minh r `ang ˘ xk+1 +1 sô´ nguyên. Thât v . ây,. xk+1 +1 xk+1cung l ˜ a` xk+1= (x +1x)(xk +1xk) − (xk−1 +1 Theo gi,a thiê´t c,a 3 biê,u thu´,c x +1x, xk +1xk, xk−1 +1 xk−1). diên c ˜ ac sô ´ ´ nguyên. Vây. xk+1 +1 xk−1dê¯`u biê,u xk+1cung l ˜ a m` ôt sô .´ nguyên. J . Chu´,ng minh r `˘ang moi sô .´ tu.,nhiên lo´,n ho,n 1 c´o thê, Vı d´ u 2.7. biê,u di˜ên du,o´,i dang t´ıch c .,ua nhu˜,ng sô´ nguyên tô´. 2.1. Môt sô .´ dang nguyên l . y quy n ´ ap to . an h ´ oc. 31 Lo`,i gi,ai. Bu,o´,c co,s,o,: Hiê,n nhiên mênh . dê¯` d¯ung v ´ o´,i moi sô .´ nguyên tô´, tru,o`,ng ho.,p d¯.ac bi ˘ êt. n = 2. Bu,o´,c quy nap.: Gi,a s,u, mênh . dê¯` d¯ung v ´ o´,i moi sô .´ tu.,nhiên k, ma` 2 ≤ k < n. Ngh˜ıa la m` oi sô .´ 2 ≤ k < n dê¯`u biê,u diên du ˜,o´,i dang . t´ıch cac th ´ u`,a sô´ nguyên tô´. Ta xet hai tru ´,o`,ng ho.,p 1) Nê´u n la sô ` ´ nguyên tô´th`ı mênh . dê¯` d¯ung. ´ 2) Nê´u n la h ` o.,p sô´ th`ı theo d¯.inh ngh˜ıa ho.,p sô´ tô`n tai hai sô .´ nguyên n1 < n va` n2 < n sao cho n = n1n2. Theo gi,a thiê´t quy nap. n1 va` n2 dê¯`u biê,u diên˜ du¯,o.,c thanh t ` ´ıch cac sô ´ ´ nguyên tô´. Do d¯o suy ra ´ n cung biê ˜,u diên˜ du¯,o.,c thanh t ` ´ıch cac sô ´ ´ nguyên tô´. J Chu´ y: ´ Ta cung c ˜ o thê ´,chu´,ng minh su.,biê,u diên trong b ˜ ai n ` ay` cho moi sô .´tu.,nhiên la duy nhâ ` ´t. . Chu´,ng minh r `˘ang môi c ˜.˘ap sô´ nguyên n ≥ 1 v `a b > 1 Vı d´ u 2.8. tô`n tai biê .,u di˜ên du,o´,i dang . n = csbs + cs−1bs−1 + · · · + c1b + c0, (2.8) ,o,dây ¯ s ≥ 0 l `a môt sô .´ nguyên, v `a 0 ≤ ci ≤ b − 1 vo´,i moi.i = 0, 1, . . . ,s − 1 v `a 0 < cs ≤ b − 1. Lo`,i gi,ai. Ta lâ´y sô´ bâ´t ky` b > 1 va` ap d ´ ung phu .,o,ng phap ch ´ u´,ng minh quy nap to . an h ´ oc.. Bu,o´,c co,s,o,: Vo´,i n = 1, ta lâ´y s = 0, c0 = 1 ≤ b − 1. Ta nhân. du¯,o.,c dang . d¯,ang th ˘ u´,c (2.8) dang . 1 = c0. Bu,o´,c quy nap.: Gi,a s,u,biê,u diên ( ˜ 2.8) d¯ung v ´ o´,i moi sô .´tu.,nhiên k nh,o ho,n n. Theo d¯.inh l´ı co,b,an c,ua sô´ hoc v . o´,i n va` b co thê ´,t`ım du¯,o.,c sô´ nguyên không âm n1 va` r, sao cho n = bn1 + r, 0 ≤ r ≤ b − 1. 32 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. Dê thâ ˜ ´y n1 < n. thât v . ây, nê .´u ta co´ n1 ≥ n, th`ı v`ı b > 1,r ≥ 0 ta co´ n = bn1 + r > n, vô ly.´ Ta xet hai tru ´,o`,ng ho.,p 1) Nê´u n1 = 0, th`ı n = r, th`ı (2.8) tu,o,ng u´,ng vo´,i biê,u diên v ˜ o´,i s = 0, c0 = r. 2) Nê´u n1 ≥ 1, th`ı 1 ≤ n1 < n, theo gi,a thiê´t quy nap biê .,u diên ( ˜ 2.8) d¯ung v ´ o´,i moi sô .´tu.,nhiên k ≤ n. Ngh˜ıa la v ` o´,i n1 ta co´ n1 = rtbt + rt−1bt−1 + · · · + r0 vo´,i môt sô .´ nao` d⯴y t va` 0 ≤ ri ≤ b − 1 (i = 0, 1, .., t),rt > 0. Khi d¯o´ n = bn1 + r = rtbt+1 + rt−1bt + · · · + r0b + r, ngh˜ıa la, biê `,u diên (2.8) tu ˜,o,ng u´,ng vo´,i s = t + 1, cs = rt, . . . , c1 = r0, c0 = r. J Chu´ y: ´ Ta cung c ˜ o thê ´,chu´,ng minh su.,biê,u diên trong b ˜ ai n ` ay` cho moi sô .´ tu.,nhiên la duy nhâ ` ´t. Ðây la` d¯.inh l´ı vê` su.,biê,u diên˜ môt sô .´tu.,nhiên n theo co,sô´ b. Con m ` ôt sô .´ dang kh . ac n ´ u˜,a c,ua nguyên ly quy n ´ ap to . an h ´ oc. chung ta s ´ e x ˜ et sau. ´ 2.2. MÊNH Ð .`Ê TRONG NGUYÊN LY QUY N ´ AP TO . AN H ´ OC. Trong cac v ´ ´ı du tru .,o´,c ta thâ´y r `ang ˘ da sô ¯´ viêc. ap d ´ ung nguyên . ly quy n ´ ap to . an h ´ oc l . a s ` u.,biê´n dô¯,i công thu´,c ho .ac biê ˘,u thu´,c toan´ hoc. Trong m . uc nh .,o nay ch ` ung tôi nhâ ´ ´n manh . d꯴n viêc. ap d ´ ung . nguyên ly quy n ´ ap trên c . ac m ´ ênh . dê¯` không ph,ai la công th ` u´,c ho .ac biê ˘,u thu´,c toan h ´ oc. Trong tru .,o`,ng ho.,p nhu,vây c . ac bu ´,o´,c 2.2. Mênh . dê¯` trong nguyên ly quy n ´ ap to . an h ´ oc. 33 P(k) c,ua mênh . dê¯` kh,ang ˘ d¯.inh du¯,o.,c xac´ d¯.inh mê`m d,eo ho,n thông qua cac v ´ ´ı du sau: . . Chu´,ng minh r `˘ang tô,ng lâp phu .,o,ng c,ua ba sô´tu.,nhiên Vı d´ u 2.9. liên tiê´p chia hê´t cho 9. Lo`,i gi,ai. Bu,o´,c co,s,o,: Tô,ng 13 + 23 + 33chia hê´t cho 9. Ngh˜ıa la` mênh . dê¯` c,ua bai to ` an l ´ a` d¯ung, khi sô ´ ´ dâ¯`u tiên c,ua 3 sô´ liên tiê´p la 1. ` Bu,o´,c quy nap.: Gi,a s,u, mênh . dê¯` kh,ang ˘ d¯.inh c,ua bai to ` an´ d¯ung ´ vo´,i k, ngh˜ıa la` k3 + (k + 1)3 + (k + 2)3chia hê´t cho 9. Ta se ch ˜ u´,ng minh r `ang v ˘ o´,i ba sô´ tu.,nhiên liên tiê´p b´at˘ dâ¯`u tu`,(k + 1) kh,ang ˘ d¯.inh c,ua bai to ` an c ´ ung ˜ d¯ung, n ´ oi c ´ ach kh ´ ac´ (k + 1)3 + (k + 2)3 + (k + 3)3se chia hê ˜ ´t cho 9. Thât v . ây,. (k + 1)3 + (k + 2)3 + (k + 3)3 = (k3 + (k + 1)3 + (k + 2)3) + 9(k2 + 3k + 3). Tô,ng ba sô´ liên tiê´p b´at˘ dâ¯`u tu`,k + 1 biê,u diên nhu ˜,tô,ng c,ua hai sô´ hang . dê¯`u chia hê´t cho 9, th`ı tô,ng nay c ` ung chia hê ˜ ´t cho 9. J . Chu´,ng minh r `˘ang moi sô .´ nguyên dô¯ `ng (tiê`n Viêt. Vı d´ u 2.10. Nam1) lo´,n ho,n 6 c´o thê,dô¯,i ra tiê`n l ,e không du,b `˘ang nhu˜,ng dô¯ `ng tiê`n gô`m nhu˜,ng to`,2 dô¯ `ng v `a 5 dô¯ `ng. Lo`,i gi,ai. Bu,o´,c co,s,o,: Vo´,i sô´ tiê`n 7 dô¯`ng, mênh . dê¯` kh,ang ˘ d¯.inh d¯ung: 7=5+2. ´ Bu,o´,c quy nap.: Gi,a s,u,kh,ang ˘ d¯.inh d¯ung v ´ o´,i sô´ k ≥ 7 dô¯`ng. Ðê, chu´,ng minh diê ¯`u kh,ang ˘ d¯.inh cung ˜ d¯ung v ´ o´,i sô´ k + 1 dô¯`ng. Ta xet´ hai kh,a nang: ˘ 11 dô¯`ng,o,dây ta hiê ¯,u la 1000 ` dô¯`ng trên thu.,c tê´. 34 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. 1) k du¯,o.,c dô¯,i ch,ı b`ang m ˘ ôt lo . ai tiê .`n to`,2 dô¯`ng. 2) k du¯,o.,c dô¯,i b`ang c ˘ ac lo ´ ai tiê .`n, ´ıt nhâ´t co m´ ôt t . o`,loai 5 . dô¯`ng. Ta ph,ai chu´,ng minh k + 1 dô¯`ng cung ˜ dô¯,i du¯,o.,c b`ang c ˘ ac lo ´ ai. tiê`n d¯a cho. V ˜ o´,i sô´(k + 1) dô¯`ng th`ı ta dô¯,i nhu,sau: - Nê´u k dô¯`ng,o,tru,o`,ng ho.,p 1), th`ı ´ıt nhâ´t ph,ai co 4 t ´ o`,2 dô¯`ng, v`ı k > 6. Ðê,dô¯,i k + 1 dô¯`ng, ta lâ´y 2 to`,loai 2 . dô¯`ng dô¯,i thanh 1 t ` o`, loai 5 . dô¯`ng. - Nê´u k dô¯`ng trong tru,o`,ng ho.,p 2), th`ı dê¯,dô¯,i k + 1 dô¯`ng, ta lâ´y môt t . o`,loai 5 . dô¯`ng dô¯,i lâ´y 3 to`,loai 2 . dô¯`ng. Theo nguyên ly quy n ´ ap to . an h ´ oc kh .,ang ˘ d¯.inh d¯ung v ´ o´,i moi. sô´ n dô¯`ng vo´,i n > 6. J . Chu´,ng minh r `˘ang n du¯,o`,ng th,˘ang kh ´ac nhau trên Vı d´ u 2.11. môt m. .˘at ph,˘ang di qua m ¯ ôt. diê ¯,m chia m.˘at ph,˘ang ra 2n phâ`n. Lo`,i gi,ai. Bu,o´,c co,s,o,: Vo´,i n = 1 mênh . dê¯` kh,ang ˘ d¯.inh la` d¯ung, v ´ `ı môt. du¯,o`,ng th,ang chia m ˘ .at ph ˘,ang ra hai phâ ˘ `n. Bu,o´,c quy nap.: Gi,a s,u, mênh . dê¯` d¯ung v ´ o´,i sô´ n nao` d¯o, ngh ´ ˜ıa la` n du¯,o`,ng th,ang kh ˘ ac nhau ´ di qua m ¯ ôt. diê ¯,m chia m.at ph ˘,ang ra ˘ 2n phâ`n. Ðê,chu´,ng minh mênh . dê¯` kh,ang ˘ d¯.inh cung ˜ d¯ung v ´ o´,i n + 1 du¯,o`,ng th,ang, ta ch ˘ u´ y r ´`ang nê ˘ ´u du.,ng du¯,o`,ng th,ang ˘ di qua ¯ diê ¯,m d¯a cho v ˜ a không tr ` ung v ` o´,i du¯,o`,ng th,ang n ˘ ao trong sô ` ´ cac´ du¯,o`,ng th,ang c ˘ on l ` ai, th .`ı chung ta s ´ e nh ˜ ân thêm 2 phâ .`n nu˜,a c,ua m.at˘ ph,ang. Nhu ˘,vây sô .´ phâ`n c,ua m.at ph ˘,ang ˘ d¯a c ˜ o l ´ a` 2n công v . o´,i 2, ho .ac l ˘ a` 2(n + 1). J . Trong th `anh phô´ c´o n nh `a. T`ım sô´ lo´,n nhâ´t nhu˜,ng Vı d´ u 2.12. h `ang r `ao kh´ep k´ın không c ´˘at nhau c´o thê,xây du.,ng du¯,o.,c trong 2.2. Mênh . dê¯` trong nguyên ly quy n ´ ap to . an h ´ oc. 35 th `anh phô´, nê´u môi h `ang r `ao vây quanh ´ıt nhâ ˜ ´t môt nh `a v `a . không c ´o hai h `ang r `ao n `ao vây quanh môt c . um nh `a. . Lo`,i gi,ai. Bu,o´,c co,s,o,: Khi n = 1 sô´ hang r ` ao câ ` `n t´ınh la` X1 = 1. Khi n = 2 ta co thê ´,quây môi nh ˜ a m` ôt h . ang r ` ao sau ` d¯o l ´ ai. du.,ng môt h . ang r ` ao quây c `,a hai nha. Nhu `,vây sô .´hang r ` ao` X2 = 3. Khi n = 3 ta co thê ´,quây môi nh ˜ a m` ôt h . ang r ` ao, sau ` d¯o quây ´ hai nha bâ ` ´t ky b ``ang m ˘ ôt h . ang r ` ao v ` a sau c ` ung l ` a m` ôt h . ang r ` ao` quây c,a ba nha. Ta c ` o´ X3 = 5. Do d¯o gi ´,a thiê´t quy nap: . Xn = 2n − 1. Ðê,chu´,ng minh công thu´,c la` d¯ung, ta c ´ o nh ´ ân x . et sau: Ðô ´ ´i vo´,i môt th . anh phô ` ´ n nha` theo cac´ diê ¯`u kiên. dâ¯`u bai, luôn xây d ` u.,ng du¯,o.,c d¯ung ´ n hang ` rao "riêng" c `,ua môi nh ˜ a v ` a ch `,ı co m´ ôt h . ang r ` ao "chung" cho c `,a thanh phô ` ´. Bu,o´,c quy nap.: Gi,a s,u,công thu´,c Xn = 2n − 1 d¯ung v ´ o´,i moi. n ≤ k va ta câ ` `n chu´,ng minh no c ´ ung ˜ d¯ung v ´ o´,i n = k + 1. Ta xet h ´ ê thô .´ng hang r ` ao v ` o´,i sô´ hang r ` ao l ` o´,n nhâ´t co thê ´, du.,ng du¯,o.,c trong môt th . anh phô ` ´ co´ k + 1 nha v ` a tho `,a man c ˜ ac´ diê ¯`u kiên c .,ua dâ¯`u bai. Theo nh ` ân x . et trong h ´ ê thô .´ng d¯o luôn c ´ o´ 1 (va ch `,ı 1) hang r ` ao l ` o´,n quây c,a thanh phô ` ´. Gi,a s,u,hang r ` ao` d¯o b ´ .i b,o di th ¯ `ı luc´ d¯o th ´ anh phô ` ´ du¯,o.,c quây thanh 2 khu b ``ang 2 ˘ hang r ` ao. Khu th ` u´,nhâ´t ch,ang h ˘ an l . a` m nha, khu th ` u´,hai co´ l nha:` m ≥ 1; l ≥ 1; m + l = k + 1. Hê thô .´ng hang r ` ao quây khu th ` u´,nhâ´t cung l ˜ a l ` o´,n nhâ´t tu´,c la` co tâ ´ ´t c,a 2m − 1 hang r ` ao, v ` a quây khu th ` u´,hai co´ 2l − 1 hang r ` ao` (theo gi,a thiê´t quy nap). Không thê .,co h´ ang r ` ao n ` ao c ` o thê ´,quây 36 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. dô¯`ng tho`,i nhu˜,ng ngôi nha t ` u`,2 khu dang x ¯ et´ d¯o. Do ´ d¯o ch ´,ı con` lai m. ôt h . ang r ` ao duy nhâ ` ´t. Ðo l ´ a h` ang r ` ao chung quây c `,a thanh ` phô´. Nhu,vây ta c . o´ Xk+1 = (2m − 1) + (2l − 1) + 1 = 2(m + l) − 1 = 2(k + 1) − 1. J . Tu`,2n sô´ 1, 2, 3, . . . , 2n ta lâ´y ra môt c ´ach bâ .´t k `y n + 1 Vı d´ u 2.13. sô´. Chu´,ng minh r `˘ang trong sô´ c ´ac sô´ lâ´y ra d ´o c´o ´ıt nhâ ¯ ´t môt sô .´ chia hê´t cho môt sô .´ kh ´ac. Lo`,i gi,ai. (Phu,o,ng phap gi ´,ai sau dây l ¯ a c `,ua M. Fritman).2 Khi n = 1 mênh . dê¯` d¯ung l ´ a hiê `,n nhiên. Gi,a s,u, mênh . dê¯` d¯ung v ´ o´,i n − 1 ngh˜ıa la t ` u`,2(n − 1) sô´ 1, 2, . . . , 2(n − 1) (,o,dây ¯ n ≥ 2) co thê ´,chon ra . du¯,o.,c n sô´ sao cho trong d¯o c ´ o´ ´ıt nhâ´t môt sô .´ chia hê´t cho môt sô .´ khac. ´ Ta chu´,ng minh mênh . dê¯`d¯ung v ´ o´,i n. Gi,a s,u,tu`,2n sô´1, 2, . . . , 2n ta co thê ´,chon. du¯,o.,c n + 1 sô´ sao cho trong d¯o không c ´ o sô ´ ´ nao l ` a` bôi sô .´ c,ua sô´ khac. Ta k ´ y hi ´ êu t . âp tâ .´t c,a n + 1 sô´ d¯o l ´ a` Xn+1. Ðô´i vo´,i tâp. Xn+1 x,ay ra 4 tru,o`,ng ho.,p. 1. Xn+1 không chu´,a c,a 2n − 1 va` 2n, 2. Xn+1 chu´,a 2n − 1 va không ch ` u´,a 2n, 3. Xn+1 không chu´,a 2n − 1 va ch ` u´,a 2n, 4. Xn+1 chu´,a c,a 2n − 1 va` 2n. Tru,o`,ng ho.,p 1: Ta b,o di t ¯ u`, Xn+1 môt sô .´ bâ´t ky, c ` on l ` ai. n sô´ ma` môi sô ˜ ´ dê¯`u không lo´,n ho,n 2n − 2 va trong sô ` ´ d¯o không c ´ o sô ´ ´ nao` 2Bai n ` ay c ` ung c ˜ o thê ´,gi,ai b`ang phu ˘,o,ng phap Ðirichlet trong [1] ´ 2.2. Mênh . dê¯` trong nguyên ly quy n ´ ap to . an h ´ oc. 37 la b ` ôi c .,ua môt sô .´ khac. ´ Tru,o`,ng ho.,p 2: Ta b,o tu`, Xn+1 sô´ 2n − 1, con l ` ai l . a` n sô´ ma m` oi. sô´ dê¯`u không lo´,n ho,n 2n − 2 va không c ` o sô ´ ´ nao l ` a b ` ôi c .,ua môt sô .´ khac. ´ Tru,o`,ng ho.,p 3: Ta b,o tu`, Xn+1 sô´ 2n, con l ` ai l . a` n sô´ ma m` oi sô .´ dê¯`u không lo´,n ho,n 2n − 2 va không c ` o sô ´ ´ nao l ` a b ` ôi c .,ua môt sô .´ khac. ´ Tru,o`,ng ho.,p 4: Tru,o´,c hê´t ta thâ´y trong Xn+1 không chu´,a sô´ n do d¯o trong tru ´,o`,ng ho.,p nay ta b `,o tu`, Xn+1 hai sô´ 2n − 1 va` 2n thêm vao sô ` ´ n ta cung nh ˜ ân. du¯,o.,c n sô´ ma m` oi sô .´ dê¯`u không lo´,n ho,n 2n − 2. Ta se ch ˜ u´,ng minh r `ang trong ˘ n sô´ d¯o không c ´ o sô ´ ´ nao` chia hê´t cho sô´ khac. Ðê ´,chu´,ng minh diê ¯`u nay ta ch `,ı câ`n chu´,ng minh: 1) Trong sô´ d¯o tr ´ u`,sô´ n không co sô ´ ´ nao chia hê ` ´t cho n va` 2) Sô´ n không chia hê´t cho sô´ nao kh ` ac, ngo ´ ai` n. Ðiê`u thu´,nhâ´t la hiê `,n nhiên v`ı tâ´t c,a cac sô ´ ´ d¯o´ dê¯`u không lo´,n ho,n 2n − 2. Ðiê`u thu´,hai cung l ˜ a hiê `,n nhiên v`ı trong Xn+1 sô´ 2n không chia hê´t cho môt sô .´ nao kh ` ac. ´ Vây nê .´u mênh . dê¯` không d¯ung cho ´ 2n sô´ th`ı cung ˜ d¯ung cho ´ 2(n − 1) sô´. Ðiê`u nay mâu thu ` ân v ˜ o´,i gi,a thiê´t quy nap. V . ây m . ênh . dê¯` d¯a cho ˜ d¯ung v ´ o´,i 2n sô´ 1, 2, . . . , 2n vo´,i n la sô ` ´ tu.,nhiên bâ´t ky.` J 38 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. 2.3. BU,O´,C QUY NAP ÐU .,O.,C XÂY DU.,NG TRÊN P(k) Trong chu´,ng minh b`ang phu ˘,o,ng phap quy n ´ ap to . an h ´ oc, kh . o´ khan nhâ ˘ ´t la bu `,o´,c quy nap chuyê .,n tu`, mênh . dê¯` P(k) sang mênh . dê¯` P(k + 1). Trong phâ`n nay c ` ung nhu ˜,cac v ´ ´ı du.,o, muc sau ta . xem xet k ´ y c ˜ ac kh ´,a nang biê ˘ ´n dô¯,i quy nap tr . u.,c tiê´p tu`,kh,ang ˘ d¯.inh d¯ung c ´,ua P(k) sang kh,ang ˘ d¯.inh d¯ung c ´,ua P(k + 1). . Chu´,ng minh r `˘ang Vı d´ u 2.14. 2n−1(an + bn) > (a + b)n, (2.9) ,o,dây ¯ a + b > 0, a 6= b, n > 1. Lo`,i gi,ai. Bu,o´,c co,s,o,: Vo´,i n = 2 d¯,ang th ˘ u´,c (2.9) co d´ ang . 2(a2 + b2) > (a + b)2. (2.10) V`ı a 6= b ta co bâ ´ ´t d¯,ang th ˘ u´,c d¯ung ´ (a − b)2 > 0, công hai vê .´ bâ´t d¯,ang th ˘ u´,c nay v ` o´,i (a + b)2, ta co ( ´ 2.10). Bu,o´,c quy nap.: Gi,a s,u,(2.9) d¯ung v ´ o´,i sô´ n = k nao` d¯o,´ 2k−1(ak + bk) > (a + b)k. (2.11) Ðê,chu´,ng minh (2.9) cung ˜ d¯ung cho ´ n = k + 1, ta nhân hai vê´ (2.11) vo´,i a + b v`ı a + b > 0 ta nhân bâ .´t d¯,ang th ˘ u´,c d¯ung ´ 2k−1(ak + bk)(a + b) > (a + b)k+1. (2.12) Nhu,vây. dê¯,chu´,ng minh (2.9) d¯ung v ´ o´,i n = k + 1 bây gio`,ta ch,ı câ`n chu´,ng minh 2k(ak+1 + bk+1) > 2k−1(ak + bk)(a + b). (2.13) Sau khi biê´n dô¯,i va` do¯,n gi,an hai vê´ta du¯,o.,c bâ´t d¯,ang th ˘ u´,c tu,o,ng du¯,o,ng ak+1 + bk+1 > akb + bka, tu`,d¯o suy ra ´ (ak − bk)(a − b) > 0. (2.14) 2.3. Bu,o´,c quy nap. du¯,o.,c xây du.,ng trên P(k) 39 Xet hai tru ´,o`,ng ho.,p: 1) Nê´u a > b, va` diê ¯`u kiên. d¯a cho l ˜ a` a > −b, suy ra a > |b|. V`ı vây. ak > bk. Do d¯o bâ ´ ´t phu,o,ng tr`ınh (2.14) d¯ung. ´ 2) Nê´u a < b, ly lu ´ ân tu .,o,ng tu.,phâ`n trên ta co´ ak < bk, trong tru,o`,ng ho.,p nay ( ` 2.14) cung ˜ d¯ung. T ´ om l ´ ai, ( . 2.14) d¯ung v ´ o´,i moi. a 6= b, do d¯o ( ´ 2.9) d¯ung v ´ o´,i n = k + 1. J . Cho d ˜ay sô´ 0 < a1 < a2 < · · · < an, v `a ei = ±1, Vı d´ u 2.15. i = 1, 2, . . . Chu´,ng minh r `˘angn∑ i=1 eiai nhân ´ıt nhâ .´t C2n+1gi ´a tr.i kh ´ac nhau khi ei thay dô¯,i dâ´u trong tô,ho.,p 2n kh ,a n ˘ang xâ,y ra. Lo`,i gi,ai. Bu,o´,c co,s,o,: Khi n = 1, tô`n tai d¯ung 2 gi ´ a tr ´ .i khac nhau ´ c,ua tô,ng ( a va` −a) va` C22 = 1, nhu,vây m . ênh . dê¯` d¯ung. ´ Bu,o´,c quy nap.: Gi,a s,u, mênh . dê¯` d¯ung v ´ o´,i n = k; ngh˜ıa la`k∑ eiai i=1 nhân.´ıt nhâ´t C2k+1gia tr ´ .i khac nhau. Gi ´,a s,u,thêm môt phâ .`n t,u, ak+1, ma` ak+1 > ak. Ta câ`n ph,ai ch,ı ra r `ang tô ˘,ng se c ˜ o´ C2k+2gia´ tr.i. Theo gi,a thiê´t quy nap. d¯a c ˜ o s ´˜an˘ C2k+1gia tr ´ .i c,ua tô,ng khac´ nhau sinh b,o,i a1, a2, . . . , ak; ta câ`n t`ım nhu˜,ng gia tr ´ .i khac nhau ´ c,ua tô,ng, co sô ´ ´ lu,o.,ng la` C2k+2 − C2k+1 = k + 1. T`ım cac tô ´,ng d¯o´ b`ang c ˘ ach sau ´ dây: Ð ¯ .at˘ S =k∑ i=1 ai(nhu,vây th .`ı S ≥k∑ i=1 eiai vo´,i moi. su.,lu.,a chon.ei), va ch ` u´ y r ´`ang c ˘ ac tô ´,ng sau S + ak+1, S + (ak+1 − ak), S + (ak+1 − ak−1), . . . , S + (ak+1 − a1) co gi ´ a tr ´ .i khac nhau v ´ a` lo´,n ho,n thu.,c su.,S. Nhu,vây tô .`n tai. k + 1 gia tr ´ .i khac nhau n ´ u˜,a c,ua tô,ng d¯a cho. ˜ J . Nê´u a > 0 v `a b > 0, th`ı (n − 1)an + bn ≥ nan−1b, vo´,i Vı d´ u 2.16. 40 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. n l `a sô´ nguyên du,o,ng; d¯,˘ang thu´,c xâ,y ra khi v `a ch ,ı khi a = b. Lo`,i gi,ai. Mênh . dê¯` d¯ung v ´ o´,i n = 1. Gi,a s,u, mênh . dê¯` d¯ung v ´ o´,i n = k, (k − 1)ak + bk ≥ kak−1b Ðê,xây du.,ng mênh . dê¯` vo´,i n = k + 1, ta tiê´n hanh c ` ac bu ´,o´,c 1) Nhân hai vê´ bâ´t d¯,ang th ˘ u´,c vo´,i a (k − 1)ak+1 + bka ≥ kakb. 2) Công thêm . ak+1 vao bâ ` ´t d¯,ang th ˘ u´,c trên kak+1 + bka ≥ kakb + ak+1. 3) Chuyê,n bka sang vê´ ph,ai ta co´ kak+1 ≥ kakb + ak+1 − bka. 4) Công thêm . bk+1 vao hai vê ` ´ c,ua bâ´t d¯,ang th ˘ u´,c nay` kak+1 + bk+1 ≥ kakb + ak+1 − bka + bk+1. Theo gi,a thiê´t quy nap th .`ı bâ´t d¯,ang th ˘ u´,c trên tr,o,thanh ` d¯,ang ˘ thu´,c khi va ch `,ı khi a = b. Ðê,chu´,ng minh P(k + 1) d¯ung, ta ch ´,ı ra vê´ ph,ai c,ua bâ´t d¯,ang th ˘ u´,c sau cung th `,oa man˜ kakb + ak+1 − bka + bk+1 ≥ (k + 1)akb va bâ ` ´t d¯,ang th ˘ u´,c tr,o,thanh ` d¯,ang th ˘ u´,c khi va ch `,ı khi a = b. Thât. vây, ta biê .´n dô¯,i tu`,du,o´,i lên kakb + ak+1 − bka + bk+1 ≥ (k + 1)akb, −akb + ak+1 − bka + bk+1 ≥ 0, ak(a − b) + bk(b − a) ≥ 0, (ak − bk)(a − b) ≥ 0. 2.3. Bu,o´,c quy nap. du¯,o.,c xây du.,ng trên P(k) 41 Bâ´t d¯,ang th ˘ u´,c nay` d¯ung (do ´ a − b va` ak − bkco c ´ ung dâ ` ´u), suy ngu,o.,c lai bâ .´t d¯,ang th ˘ u´,c ta câ`n chu´,ng minh la` d¯ung v ´ a` d¯,ang th ˘ u´,c xâ,y ra khi va ch `,ı khi a = b. J . Chu´,ng minh r `˘ang Vı d´ u 2.17. Sn = 1 − 2 + 3 − 4 + · · · + (−1)n−1.n = (−1)n−1 n + 1 2 ,o,dây ¯ [x] l `a sô´ nguyên lo´,n nhâ´t nh ,o ho,n x, n l `a sô´ nguyên du,o,ng. Lo`,i gi,ai. Ðê,chu´,ng minh du¯,o.,c bai to ` an, ta ch ´ u´,ng minh công thu´,c sauhn 2 vo´,i moi. n. Thât v . ây,. i + n + 1 2 = n a) vo´,i n = 2m la sô ` ´ ch˜an, ta c ˘ o´ hn 2 i + n + 1 2 = [m] + m +12 = m + m = n. b) vo´,i n = 2m + 1 la sô ` ´ l,e hn 2 i + n + 1 2 = m +12 + [m + 1] = m + m + 1 = n. Bu,o´,c co,s,o,: S1 = 1 = (−1)0 1 + 1 2 , mênh . dê¯` d¯ung v ´ o´,i n = 1 Bu,o´,c quy nap.: Gi,a s,u,d¯,ang th ˘ u´,c d¯ung v ´ o´,i n = k, ngh˜ıa la` Sk = 1 − 2 + 3 − 4 + · · · + (−1)k−1.k = (−1)k−1 k + 1 2 . Khi d¯o´ Sk+1 = Sk + (−1)k(k + 1) = (−1)k−1 k + 1 2 + (−1)k(k + 1) = (−1)k k + 1 − k + 1 2 = (−1)k. k + 2 2 . 42 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. Ð,ang th ˘ u´,c sau cung suy ra t ` u`,d¯,ang th ˘ u´,c,o,phâ`n trên. Ð,ang th ˘ u´,c c,ua dê¯` ra d¯ung v ´ o´,i n = k + 1. J 2.4. BU,O´,C QUY NAP ÐU .,O.,C XÂY DU.,NG TRÊN P(k + 1) Bu,o´,c quy nap trong nguyên l . y quy n ´ ap to . an h ´ oc câ .`n kh,ang ˘ d¯.inh P(k + 1) suy tu`,P(k). Nhu,ng nhiê`u khi viêc biê .´n dô¯,i tru.,c tiê´p tu`,P(k) sang P(k + 1) g .ap râ ˘ ´t nhiê`u kho kh ´ an ho ˘ .ac không ˘ co hu ´,o´,ng ch´ınh xac. Khi ´ d¯o ta ph ´,ai lam ngu `,o.,c lai. dê¯,biê,u diên˜ P(k + 1) ra mênh . dê¯` c,ua P(k) va tiê ` ´n hanh quy n ` ap. Phâ .`n nay` va phâ ` `n tru,o´,c liên quan mât thiê .´t va tu `,o,ng du¯,o,ng nhau. . Chu´,ng minh r `˘ang sô´ zn = 32n+1 + 40n − 67 chia hê´t Vı d´ u 2.18. cho 64 vo´,i moi sô .´ tu.,nhiên n. Lo`,i gi,ai. Bu,o´,c co,s,o,: z1 = 33 + 40 − 67 = 0 chia hê´t cho 64. mênh . dê¯` d¯ung v ´ o´,i n = 1 Bu,o´,c quy nap.: Gi,a s,u,zn chia hê´t cho 64. Khi d¯o´ zn+1 = 32n+3 + 40n − 27 = 9(32n+1 + 40n − 67) − 320n + 576 = 9.zn − 64(5n − 9) cung chia hê ˜ ´t cho 64. Bai to ` an´ d¯ung v ´ o´,i moi. n. J . K ´y hiêu. Rn = Vı d´ u 2.19. r 2 + q 2 +p2 + · · · +√2 c ˘an bâc hai . n lâ`n. Chu´,ng minh r `˘ang cosπ2n =12Rn−1, sin π2n =12√2 − Rn−2 vo´,i moi. n ≥ 3. Lo`,i gi,ai. Bu,o´,c co,s,o,: cosπ4= sin π4=√22, mênh . dê¯` d¯ung v ´ o´,i n = 3 v`ı 2.4. Bu,o´,c quy nap. du¯,o.,c xây du.,ng trên P(k + 1) 43 cosπ23 = cosπ8= vuut1 + cosπ4 2= p 2 +√2 2=R22, sin π23 = sin π8= vuut1 − cosπ4 2= p 2 −√2 2= √2 − R1 2. Bu,o´,c quy nap.: Gi,a s,u, mênh . dê¯` d¯ung v ´ o´,i sô´tu.,nhiên k ≥ 3. Khi d¯o´ cosπ 2k+1= sin π 2k+1= vuut1 + cosπ2k 2= vuut1 − cosπ2k 2= √2 + Rk−1 2=Rk 2, √2 − Rk−1 2. Nhu,vây, m . ênh . dê¯` d¯ung v ´ o´,i n = k + 1. Theo nguyên ly quy n ´ ap. toan h ´ oc c . ac công th ´ u´,c d¯ung v ´ o´,i moi. n ≥ 3. J . Chu´,ng minh r `˘angn55+n42+n33−n30 l `a sô´ nguyên Vı d´ u 2.20. vo´,i n = 0, 1, 2, ... Lo`,i gi,ai. Bu,o´,c co,s,o,: Mênh . dê¯` d¯ung v ´ o´,i n = 0. Bu,o´,c quy nap.: Gi,a s,u, mênh . dê¯` d¯ung v ´ o´,i n = k. Ta câ`n ph,ai chu´,ng minh 5+(k + 1)4 (k + 1)5 2+(k + 1)3 3−k + 1 30 la sô ` ´ nguyên. Ta khai triê,n biê,u thu´,c trên 5+k4 + 4k3 + 6k2 + 4k + 1 k5 + 5k4 + 10k3 + 10k2 + 5k+ +k3 + 3k2 + 3k + 1 3−k + 1 30 . 2+ 44 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. Nhom l ´ ai. dê¯,xuâ´t hiên. P(k) 5+k42+k33−k30!+ ((k4 + 2k3 + 2k2 + k) + (2k3 + 3k2 + 2k) + (k2 + k) + 1) k5 Nhu,vây nh . om th ´ u´,nhâ´t theo gi,a thiê´t la sô ` ´nguyên va c ` ac nh ´ om´ sau cung l ˜ a sô ` ´nguyên, suy ra tô,ng c,ua chung l ´ a sô ` ´nguyên va` d¯o´ cung l ˜ a m` ênh . dê¯` bai to ` an v ´ o´,i n = k + 1. J . Chu´,ng minh r `˘ang vo´,i moi sô .´nguyên n ≥ 2 v `a |x| < 1 Vı d´ u 2.21. th`ı bâ´t d¯,˘ang thu´,c sau luôn d ´ung: ¯ (1 − x)n + (1 + x)n < 2n. Lo`,i gi,ai. Bu,o´,c co,s,o,: Khi n = 2 bâ´t d¯,ang th ˘ u´,c d¯ung hiê ´,n nhiên. Bu,o´,c quy nap.: Gi,a s,u,bâ´t d¯,ang th ˘ u´,c d¯ung v ´ o´,i n = k. Ta ph,ai chu´,ng minh bâ´t d¯,ang th ˘ u´,c cung ˜ d¯ung v ´ o´,i n = k + 1; do gi,a thiê´t dâ¯`u bai v ` a gi `,a thiê´t quy nap ta c . o´ (1 − x)k+1 + (1 + x)k+1 < [(1 − x)k + (1 + x)k][(1 − x) + (1 + x)] < 2k.2 = 2k+1. Nhu,vây bâ .´t d¯,ang th ˘ u´,c du¯,o.,c chu´,ng minh vo´,i n = k + 1. J . Vo´,i moi. x trong 0 ≤ x ≤ π, chu´,ng minh r `˘ang Vı d ´ u 2.22. | sin nx| ≤ n sin x,,o,dây ¯ n l `a sô´ nguyên không âm. Lo`,i gi,ai. Bu,o´,c co,s,o,: Vo´,i n = 1 bâ´t d¯,ang th ˘ u´,c d¯ung l ´ a tâ ` ´t nhiên. Bu,o´,c quy nap.: Gi,a s,u,bâ´t d¯,ang th ˘ u´,c d¯ung v ´ o´,i n = k: | sin kx| ≤ k sin x. Ta câ`n chu´,ng minh bâ´t d¯,ang th ˘ u´,c cung ˜ d¯ung ´ 2.5. Quy nap to . an h ´ oc v . a ph ` ep truy hô ´ `i 45 vo´,i n = k + 1. Ta xet´ | sin(k + 1)x| = | sin(kx + x)| = | sin(kx) cos x + cos(kx) sin x| = | sin(kx) cos x| + | cos(kx) sin x| = | sin(kx)|| cos x| + | cos(kx)|| sin x| ≤ |k sin x| + | sin x| ≤ (k + 1) sin x. Nhu˜,ng bâ´t d¯,ang th ˘ u´,c trên du¯,o.,c suy ra b,o,i 0 ≤ x ≤ π nên sin x ≥ 0 va` | cos kx| ≤ 1. Nhu,vây ta . d¯a ch ˜ u´,ng minh bâ´t d¯,ang ˘ thu´,c d¯ung cho ´ n = k + 1. Suy ra no´ d¯ung v ´ o´,i moi. n ≥ 1. J 2.5. QUY NAP TO . AN H ´ OC V . A PH ` EP TRUY H ´ ÔI ` Nhiê`u bai to ` an ta ´ d¯a x ˜ et c ´ o liên quan ´ d꯴n day sô ˜ ´ nhu,câ´p sô´ công, câ .´p sô´nhân, ... môi sô ˜ ´hang c .,ua chung ´ du¯,o.,c biê,u diên b ˜ `ang ˘ cach lâ ´ ´y nhu˜,ng gia tr ´ .i c,ua sô´hang tru .,o´,c no, ngo ´ ai nh ` u˜,ng sô´hang . kh,o,i dâ¯`u c,ua day. Nh ˜ u˜,ng công thu´,c sô´ hang chung c .,ua day nhu ˜, vây. du¯,o.,c du¯,a ra va coi nhu `,la` d¯.inh ngh˜ıa môt d . ay. Phu ˜,o,ng phap´ cho môt d . ay nhu ˜,vây râ .´t giô´ng vo´,i nguyên ly quy n ´ ap to . an h ´ oc.. Ta co thê ´,dung quy n ` ap. dê¯,d¯.inh ngh˜ıa môt kh . ai ni ´ êm m . o´,i. Nhu˜,ng nha to ` an h ´ oc g . oi n . o l ´ a` loai. d¯.inh ngh˜ıa quy nap., nhu,ng cac nh ´ a` khoa hoc m . ay t ´ ´ınh goi n . o l ´ a` d¯.inh ngh˜ıa hô`i quy. Ðê,hiê,u vâ´n dê¯` nay ta x ` et m ´ ôt v .´ı du. Ð . .inh ngh˜ıa giai thu`,a c,ua môt sô .´ nguyên, ky hi ´ êu l . a` P(n) = n!, nhu,sau: nê´u n = 0 ta gan´ P(n) = 1 va nê ` ´u vo´,i môi˜ n > 0 gan gi ´ a tr ´ .i P(n) = n ·(n − 1)· . . . · 2 · 1 ngh˜ıa la t ` ´ıch n sô´ nguyên du,o,ng dâ¯`u tiên. Ta t´ınh môt sô .´ gia tr ´ .i dâ¯`u 46 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. 0! = 1, 1! = 1 = 1 · 0!, 2! = 2 · 1 = 2 · 1! = 2, 3! = 3 · 2 · 1 = 3 · 2! = 6. Nhu,vây v . o´,i moi sô .´ tu.,nhiên n, ho .ac l ˘ a` n = 0 co P(n)=1; ho ´ .ac l ˘ a` n > 0 co´ P(n) = n · (n − 1)!. Ðiê`u nay g ` o.,i y ta ´ d¯.inh ngh˜ıa theo quy nap c .,ua P(n) nhu,sau: Bu,o´,c co,s,o,: Nê´u n = 0, th`ı n! = 1 va` Bu,o´,c quy nap.: Nê´u n! d¯a x ˜ ac´ d¯.inh, th`ı ta co thê ´,xac´ d¯.inh (n + 1)! b`ang ˘ (n + 1) · n!. Bu,o´,c quy nap trong . d¯.inh ngh˜ıa trên trong tin hoc ngu .,o`,i ta thu,o`,ng goi l . a` Bu,o´,c hô`i quy va g ` oi. d¯.inh ngh˜ıa kiê,u nhu,trên la` d¯.inh ngh˜ıa theo hô`i quy. Ta thâ´y r `ang ˘ d¯.inh ngh˜ıa hô`i quy ,o,trên hoan to ` an nhu `,nguyên ly quy n ´ ap to . an h ´ oc. Bu .,o´,c co,s,o,cho ta gia´ tr.i tai sô .´tu.,nhiên ban dâ¯`u 0. Bu,o´,c hô`i quy cho ta biê´t nê´u ta d¯a˜ biê´t d¯.inh ngh˜ıa tai. n th`ı ta co thê ´,d¯.inh ngh˜ıa du¯,o.,c tai. n + 1 (bu,o´,c tiê´p theo). Nhu,vây. d¯.inh ngh˜ıa dâ¯`y d¯,u cho moi sô .´tu.,nhiên n. Ð.inh ngh˜ıa xuâ´t phat t ´ u`,0 va t ` u`,ng bu,o´,c liên tiê´p d¯.inh ngh˜ıa P(n) cho nhu˜,ng sô´ tu.,nhiên cang ng ` ay c ` ang l ` o´,n. Nhu,ng dê¯,t´ınh toan´ P(n) ta di ngu ¯,o.,c lai, t . u`, mênh . dê¯` lo´,n nhâ´t d꯴n mênh . dê¯` nh,o nhâ´t. V´ı du ta t .´ınh 3! = 3 · 2! = 3 · 2 · 1! = 3 · 2 · 1 · 0! = 3 · 2 · 1 · 1 = 6 Theo d¯.inh ngh˜ıa muô´n t´ınh gia tr ´ .i P(n) ta kiê,m tra xem nê´u n = 0 th`ı ap d ´ ung bu .,o´,c co,s,o,c,ua d¯.inh ngh˜ıa; ngu,o.,c lai ta tr . u`,n 2.5. Quy nap to . an h ´ oc v . a ph ` ep truy hô ´ `i 47 di¯ 1 dê¯,du¯,a bai to ` an vê ´ ` sô´ nguyên nh,o ho,n, nhu,vây bu .,o´,c hô`i quy gi,am bâc c .,ua bai to ` an´ d꯴n khi vê` bu,o´,c co,s,o,va t ` ´ınh toan xong ´ hoan to ` an. ` Râ´t nhiê`u ngôn ngu˜,lâp tr .`ınh cung cho ta t ˜ ´ınh toan´ du¯,o.,c công thu´,c theo d¯.inh ngh˜ıa hô`i quy, ch,ang h ˘ an nhu .,câu lênh sau trong . ngôn ngu˜,lâp tr .`ınh Pascal: if n = 0 then Pn := 1 else Pn := n · (n − 1)!; Dong l ` ênh trên n . oi v ´ o´,i chu,o,ng tr`ınh biên d.ich r `ang: ˘ 1. Kiê,m tra xem n = 0 co´ d¯ung không ? ´ 2. Nê´u tr,a lo`,i la Ð` ung, th ´ `ı gan´ P(n) = 1; 3. Nê´u tr,a lo`,i la Sai, th ` `ı gan´ P(n) := n · (n − 1)!; Ðê,t´ınh tiê´p tuc m . ay ph ´,ai goi d . ong l ` ênh lâ .`n nu˜,a dê¯,t´ınh (n − 1)! va c ` u´,tiê´p tuc nhu .,vây t . o´,i khi n = 0. Môt câu l . ênh không thê .,hiên. hê´t viêc t .´ınh toan hô ´ `i quy. Trong toan h ´ oc v . a tin h ` oc ngu .,o`,i ta tao ra c . ac thu ´ ât to . an thê ´,hiên chu tr .`ınh t´ınh toan. C ´ o nhiê ´ `u cach mô t ´,a thuât. toan nhu ´,liêt kê t . u`,ng bu,o´,c thu.,c hiên. ho .ac b ˘`ang so ˘,dô¯` khô´i (biê,u dô¯`). H`ınh 2.1. Nhu,chung ta ´ d¯a thâ ˜ ´y thuât to . an c ´ ung l ˜ a m` ôt công c . u mô t .,a viêc th . u.,c hiên nguyên l . y quy n ´ ap to . an h ´ oc, nhâ .´t la c ` ac biê ´,u dô¯` 48 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. thuât to . an hô ´ `i quy. Ta lâ´y v´ı du t .`ım thuât to . an t ´ ´ınh giai thu`,a c,ua sô´tu.,nhiên cho tru,o´,c? 1. Cho gia tr ´ .i sô´tu.,nhiên n; 2. Ð.at kê ˘ ´t qu,a Pn := 1 va biê ` ´n d꯴m m := n; 3. Kiê,m tra m = 0? nê´u d¯ung ´ di¯ d꯴n bu,o´,c 5; nê´u sai d꯴n bu,o´,c 4; 4. T´ınh Pn := Pn ∗ m va` m := m − 1; di¯ d꯴n bu,o´,c 3; 5. Kê´t thuc. ´ So,dô¯` khô´i thê,hiên qua H .`ınh 2.1. Nhu,vây vi . êc chuyê .,n tu`,công thu´,c hô`i quy ho .ac c ˘ ac m ´ ênh . dê¯` hô`i quy sang thuât to . an v ´ a biê `,u dô¯` thê,hiên qu . a tr ´ `ınh t´ınh toan´ tu`,nhâp d . u˜,liêu v . ao v ` a lâ ` ´y kê´t qu,a ra, cung nhu ˜,cac bu ´,o´,c t´ınh toan´ d¯oi h `,oi ta ph,ai hiê,u thâ´u d¯ao phu ´,o,ng phap quy n ´ ap to . an´ hoc. Trong cuô .´n sach n ´ ay ta s ` e˜ dê¯` câp. d꯴n môt sô .´ bai t ` âp vê .` thuât to . an v ´ a biê `,u dô¯` dê¯,minh hoa.. Ta du¯,a vao` d¯.inh ngh˜ıa hê sô .´ Newton3 Ckn =n! k!(n − k)!, (n = 0, 1, . . . ; k = 0, 1, . . . , n). (2.15) Dung ` d¯.inh ngh˜ıa giai thu`,a va gi `,an u,o´,c thu`,a sô´ chung, ta nhân. du¯,o.,c Ckn =n(n − 1). . .(n − k + 1) k!, (n = 0, 1, . . . ; k = 0, 1, . . . , n) (2.16) Chung ta thiê ´ ´t lâp.tam gi ´ac Pascal theo nguyên t´ac: C ˘ ôt. dâ¯`u tiên va "c ` anh huyê .`n" ch,ı gô`m toan sô ` ´ môt; sô .´ d¯u´,ng,o,hang th ` u´,n va` côt. k, la tô `,ng c,ua hai sô´,o,hang ` n − 1, tai c . ôt th . u´,k − 1 va` k. 3Ky hi ´ êu tu .,o,ng du¯,o,ng Ckn ≡ Ckn. 2.5. Quy nap to . an h ´ oc v . a ph ` ep truy hô ´ `i 49 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 . . . . . . . . . . . . . . . . Chu´,ng minh r `˘ang nhu˜,ng sô´ trong b ,ang trên l `a Vı d ´ u 2.23. nhu˜,ng hê sô .´ Newton: môi sô ˜ ´ d¯u´,ng,o,h `ang thu´,n v `a côt th . u´,k l `a Ckn. Lo`,i gi,ai. Chu´,ng minh b`ang quy n ˘ ap, v . o´,i n = 0 mênh . dê¯` d¯ung. ´ Gi,a s,u,hang th ` u´,n du¯,o.,c tao b .,o,i cac sô ´ ´ C0n, C1n, . . . , Ckn va k ` y´ hiêu. βn+1,0, βn+1,1, . . . , βn+1,n+1 la nh ` u˜,ng sô´,o,hang th ` u´,n + 1. Ta se ch ˜ u´,ng minh r `ang ˘ βn+1,k = Ckn+1. Thât v . ây,. ap d ´ ung nguyên t .´ac˘ tao b .,ang sô´ va gi `,a thiê´t quy nap, ta c . o´ (k − 1)!(n − k + 1)!+n! n + Ckn =n! βn+1,k = Ck−1 k!(n − k)! n − k + 1+1k) = (n + 1)! (k − 1)!(n − k)!(1 =n! Thu.,c tê´ta d¯a ch ˜ u´,ng minh công thu´,c Ck−1 k!(n − k + 1)!. n + Ckn = Ckn+1. (2.17) . H ˜ay viê´t thuât to ´an v `a v˜e so .,dô¯ ` khô´i tu,o,ng u´,ng dê¯, Vı d´ u 2.24. t´ınh hê sô .´ Newton Ckn khi cho n, k(1 ≤ k ≤ n). Lo`,i gi,ai. H`ınh 2.2 thê,hiên biê .,u dô¯` c,ua thuât to . an. ´ 1. Nhâp thông sô .´ n va` k; 2.T´ınh t := k! theo thuât to . an v ´ a so `,dô¯` d¯a biê ˜ ´t; 3. Chuâ,n b.i t´ınh n(n − 1). . .(n − k + 1), biê´n i nhân gi . a tr ´ .i dâ¯`u 50 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. la` n; 4. Ðu,a vao biê ` ´n m chu´,a gia tr ´ .i c,ua mâu sô ˜ ´, kh,o,i dâ¯`u la 1; ` 5. B´at˘ dâ¯`u t´ınh mâu sô ˜ ´ k bu,o´,c vo´,i gia tr ´ .i n(n − 1). . .(i + 1), i < n nhân vo´,i i va nh ` ân gi . a tr ´ .i m = n(n − 1). . . i. 6. Gia tr ´ .i c,ua ch,ı sô´ gi,am di¯ 1. 7. Kiê,m tra ch,ı sô´ co nh ´,o ho,n sô´ hang sau c . ung ` n − k + 1 không? nê´u không d¯ung quay vê ´ ` bu,o´,c 5; nê´u d¯ung ´ di tiê ¯´p bu,o´,c 8. 8. Gan biê ´ ´n b chu´,a gia tr ´ .i thu,o,ng c,ua m = n(n −1). . .(n − k +1) va` t = 1, 2, . . . , k. 9. Kê´t thuc: kê ´ ´t qu,a c = Ckn. J Trong thu.,c tê´ nhiê`u bai to ` an cho d ´ ay sô ˜ ´ a1, a2, . . . , an, . . . xac´ d¯.inh b`ang công th ˘ u´,c hô`i quy an = f(an−1, an−2, . . . , an−k) vo´,i 1 ≤ k ≤ n − 1 va` f la m ` ôt h . am` d¯a˜ biê´t. Cung nhu ˜,d¯.inh ngh˜ıa,o,trên khi cho môt sô .´ sô´ hang ban . dâ¯`u va h ` am` f th`ı cac´ sô´ hang c .,ua day˜ dê¯`u t´ınh du¯,o.,c. Dây sô ˜ ´ nhu, vây. dê¯`u goi l . a d ` ay hô ˜ `i quy. H`ınh 2.2. . Cho d ˜ay sô´ a1, a2, . . . , an, . . . du¯,o.,c d¯.inh ngh˜ıa theo Vı d´ u 2.25. công thu´,c sau: (n + 2)(n + 1)an+2 − n2an = 0, (n = 1, 2, . . .) (2.18) v `a a1 = 0, a2 = 1. H ˜ay t`ım an? 2.5. Quy nap to . an h ´ oc v . a ph ` ep truy hô ´ `i 51 Lo`,i gi,ai. Ta viê´t lai công th . u´,c (2.18 ) an+2 =n2 (n + 1)(n + 2)an. (2.19) Dê thâ ˜ ´y r `ang nh ˘ u˜,ng sô´ hang mang ch .,ı sô´ l,e b`ang 0. Th ˘ ât v . ây,. d¯.at˘ n = 2k − 1, khi d¯o v ´ o´,i k = 1, 2, . . . ta co´ a2k+1 =(2k − 1)2 2k(2k + 1)a2k−1. (2.20) V`ı a1 = 0, tu`,(2.20) theo quy nap suy ra . a3 = 0, a5 = 0, . . .. Khi ta d¯.at˘ n = 2k, th`ı nhu˜,ng sô´ hang ch .˜an c ˘ o công th ´ u´,c a2k+2 =2k2 (k + 1)(2k + 1)a2k. (2.21) Vo´,i k = 1, 2, 3 tu`,(2.21) ta t´ınh du¯,o.,c a4 =22.3.a2 =11.3.1 =13, a6 =2.22 3.5 .a4 =2.4 3.5.13, a8 =2.32 4.7 .a6 =2.4.6 3.5.7.14. Ta so sanh m ´ ôi sô ˜ ´ hang v . o´,i ch,ı sô´ va` du¯,a ra gi,a thiê´t a2k =2.4.6 . . .(2k − 2) 1.3.5 . . .(2k − 1) 1 k. (2.22) Tu`,(2.22) vo´,i k = 2, 3, 4 nhân. du¯,o.,c a2, a4 va` a8,o,trên. Gi,a s,u, (2.22) d¯ung v ´ o´,i sô´ k nao` d¯o, ta s ´ e ch ˜ u´,ng minh no c ´ ung ˜ d¯ung v ´ o´,i k + 1: a2k+2 =2.4.6 . . . 2k 1.3.5 . . .(2k + 1) 1 k + 1. (2.23) 52 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. Thât v . ây, do ( . 2.21) va gi `,a thiê´t quy nap ta c . o´ a2(k+1) =2k2 (k + 1)(2k + 1).2.4 . . .(2k − 2) 1.3 . . .(2k − 1).1k =2.4 . . .(2k − 2)2k 1.3 . . .(2k − 1)(2k + 1).1 k + 1. Nhu,vây, công th . u´,c (2.22) du¯,o.,c chu´,ng minh. Tom l ´ ai,. an =  0 n = 2k − 1 (k = 1, 2, . . .) 2.4 . . .(2k − 2) 1.3 . . .(2k − 1).1kn = 2k.  . Chia m.˘at ph,˘ang th `anh bao nhiêu phâ`n tu`,n du¯,o`,ng Vı d´ u 2.26. th,˘ang, dôi m ¯ ôt c .´˘at nhau v `a không c ´o ba du¯,o`,ng th,˘ang n `ao dô¯ `ng quy? Lo`,i gi,ai. Ta d¯.at˘ F(n) la sô ` ´ phâ`n m.at ph ˘,ang do ˘ n du¯,o`,ng th,ang ˘ tao ra. Ta x . et´ n + 1 du¯,o`,ng th,ang bâ ˘ ´t ky theo gi `,a thiê´t bai ra. ` n du¯,o`,ng th,ang ˘ dâ¯`u chia m.at ph ˘,ang ra ˘ F(n) phâ`n; con` du¯,o`,ng th,ang ˘ thu´,n + 1, g b.i c ´at t ˘ ai. n diê ¯,m khac nhau v ´ o´,i n du¯,o`,ng th,ang ˘ dâ¯`u, nhu,vây. du¯,o`,ng th,ang ˘ g du¯,o.,c chia ra n + 1 phâ`n. Suy ra du¯,o`,ng th,ang ˘ g di qua ¯ n + 1 phâ`n d¯a cho, m ˜ ôi phâ ˜ `n du¯,o.,c chia lam` dôi, ¯ do d¯o´ g tao thêm ra . n + 1 phâ`n mo´,i, ngh˜ıa la` F(n + 1) = F(n) + n + 1. Thay n trong d¯,ang th ˘ u´,c trên b`ang ˘ n − 1, n − 2, . . . , 2, 1 ta co´ F(n) = F(n − 1) + n, F(n − 1) = F(n − 2) + n − 1, . . . . . . F(3) = F(2) + 3, F(2) = F(1) + 2. 2.5. Quy nap to . an h ´ oc v . a ph ` ep truy hô ´ `i 53 Do F(1) = 2 va c ` ông c . ac´ d¯,ang th ˘ u´,c trên ta nhân. du¯,o.,c F(n) = 1 + (1 + 2 + · · · + n) = 1 +n(n + 1) 2. Ho .ac l ˘ a` F(n) = n2 + n + 2 2. J .(B `ai to ´an th ´ap H `a nôi). Cho ba chiê .´c coc. C . oc th . u´, Vı d´ u 2.27. nhâ´t xâu n c ´ai d˜ıa c ´o ¯ du¯,o`,ng k´ınh kh ´ac nhau sao cho c ´ac d˜ıa c ´o ¯ du¯,o`,ng k´ınh lo´,n ho,n,o,du,o´,i. Ch ´ung ta muô´n chuyê,n tâ´t c,a c ´ac d˜ıa, ¯ môi lâ ˜ `n môt chiê .´c, sang coc th . u´,hai m `a c ´ac d˜ıa v ¯ ân xê ˜ ´p thu´,tu.,tu`, lo´,n lên dê¯ ´n nh ,o. Trong tho`,i gian chuyê,n qua c ´ac coc không . du¯,o.,c d¯.˘at d˜ıa l ¯ o´,n lên d˜ıa nh ¯,o (dê¯ `u n `ay câ`n thiê´t c´o coc th . u´,ba). Sô´ lâ`n ´ıt nhâ´t dê¯,chuyê,n to `an bô. d˜ıa trong c ¯ oc m . ôt sang c . oc hai l `a bao . nhiêu? Lo`,i gi,ai. Ky hi ´ êu. Mn la sô ` ´ lâ`n nh,o nhâ´t chuyê,n xong n d¯˜ıa tu`, coc m . ôt sang c . oc hai. R . o r ˜ ang ` M1 = 1, nhu,vây ta gi .,a s,u,n > 1. Ðê,chuyê,n du¯,o.,c d¯˜ıa du,o´,i cung sang c ` ôt hai, ta ph .,ai chuyê,n n − 1 d¯˜ıa,o,trên sang côt ba. Nhu .,vây ta c . o sô ´ ´ lâ`n chuyê,n ´ıt nhâ´t la` Mn−1. Môt lâ .`n chuyê,n d¯˜ıa to nhâ´t sang côt th . u´,hai, va l ` ai ph .,ai thu.,c hiên. Mn−1 lâ`n chuyê,n sô´ n − 1 d¯˜ıa tu`,côt th . u´,ba vê` côt th . u´, hai. Nhu,vây,. Mn = 2Mn−1 + 1, M1 = 1. Dê d ˜ ang b ``ang quy n ˘ ap ta ch . u´,ng minh du¯,o.,c Mn = 2n − 1. Thât. vây, v . o´,i n = 1 công thu´,c d¯ung. Gi ´,a s,u,công thu´,c d¯ung v ´ o´,i sô´n = k, Mk = 2k − 1. Ta xet´ Mk+1 = 2Mk + 1 = 2(2k − 1) + 1 = 2k+1 − 1, do d¯o công th ´ u´,c d¯ung v ´ o´,i n = k + 1. J 54 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. 2.6. QUY NAP TO . AN H ´ OC V . A TÔ `,NG QUAT HO ´ A´ Râ´t nhiê`u bai to ` an d ´ ê gi ˜,ai ho,n,o,dang tô .,ng quat. Nhâ ´ ´t la ch ` u´,ng minh b`ang phu ˘,o,ng phap quy n ´ ap khi d . u.,do¯ an gi ´,a thiê´t quy nap. Ch .,ang h ˘ an nhu .,ta ph,ai chu´,ng minh day m ˜ ênh . dê¯` P(1), P(2), . . . không co´ d¯,u thông tin dê¯,thu.,c hiên bu .,o´,c quy nap. Trong tru .,o`,ng ho.,p d¯o ta x ´ et d ´ ay m ˜ ênh . dê¯` tô,ng quat ho ´,n Q(1), Q(2), . . . ma v ` o´,i môi˜ n mênh . dê¯` Q(n) keo theo ´ P(n), va sau ` d¯o ta l ´ ai. ap d ´ ung phu .,o,ng phap quy n ´ ap cho . Q(1), Q(2), Q(3), . . . Trong muc n . ay ta x ` et m ´ ôt sô .´ v´ı du nhu .,vây: . . T´ınh tô,ng Vı d´ u 2.28. Sn =12+222 + · · · +n2n. (2.24) Lo`,i gi,ai. Ta nhân x . et tô ´,ng trên co thê ´,viê´t lai l . a` Sn(x) = 1x + 2x2 + · · · + nxn. (2.25) Tô,ng ta câ`n t´ınh ch,ı la tru `,o`,ng ho.,p riêng c,ua (2.25) Sn 12 . Ta co thê ´,dung k ` y thu ˜ ât t .´ınh tô,ng,o,cuô´i Chu,o,ng 1 dê¯,co công th ´ u´,c t´ınh tô,ng (2.25)(ban. d¯oc th . u.,c hiên nhu ., môt b . ai t ` âp). Ta . du¯,a ra công thu´,c,o,dây v ¯ a ch ` u´,ng minh b`ang quy n ˘ ap to . an h ´ oc:. S(x) = x − (n + 1)xn+1 + nxn+2 (1 − x)2, (2.26) vo´,i x 6= 1. Vo´,i n = 1 d¯,ang th ˘ u´,c (2.26) co d ´ ang . x =x − 2x2 + x3 (1 − x)2hiê,n nhiên d¯ung. ´ 2.6. Quy nap to . an h ´ oc v . a tô `,ng quat ho ´ a´ 55 Gi,a s,u,(2.26) d¯ung v ´ o´,i sô´tu.,nhiên n. Khi d¯o´ Sn+1 = x + 2x2 + 3x3 + · · · + nxn + (n + 1)xn+1 =x − (n + 1)xn+1 + nxn+2 (1 − x)2+ (n + 1)xn+1 = x − (n + 1)xn+1 + nxn+2 + (n + 1)xn+1 − 2(n + 1)xn+2 + (n + 1)xn+3 (1 − x)2 =x − (n + 2)xn+2 + (n + 1)xn+3 (1 − x)2. Nhu,vây ( . 2.26) d¯ung v ´ o´,i n + 1. Áp dung ( . 2.26) tai gi . a tr ´ .i x =12ta co´ 1 2− (n + 1)1 Sn(12) = 2n+1 + n1 = 2 −n + 2 1 22 2n+2 2n. J . Chu´,ng minh r `˘ang nê´u A1 + · · · + An = π, 0 < Ai ≤ Vı d´ u 2.29. π, i = 1, 2, . . . , n, th`ı sin A1 + sin A2 + · · · + sin An ≤ n sin πn. Lo`,i gi,ai. Chu´,ng minh b`ang quy n ˘ ap to . an h ´ oc. d꯴n bu,o´,c quy nap. k, mênh . dê¯` P(k) d¯ung c ´ o d ´ ang nê .´u A1 + · · · + Ak = π, 0 < Ai ≤ π, i = 1, 2, . . . , k, th`ı sin A1 + · · · + sin Ak ≤ k sin πk. Ðê,chu´,ng minh mênh . dê¯` P(k + 1) d¯ung ta cho tru ´,o´,c A1 + · · · + Ak + Ak+1 = π, 0 < Ai ≤ π, i = 1, . . . , k + 1 ph,ai chu´,ng minh sin A1 + · · · + sin Ak + sin Ak+1 ≤ (k + 1) sin π k + 1. 56 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. Nê´u ta dung gi `,a thiê´t quy nap th .`ı sin A1 + · · · + sin Ak−1 + sin(Ak + Ak+1) ≤ k sin πk không thê,suy ra du¯,o.,c bu,o´,c tiê´p theo. Do viêc tô .,ng c,ua cac´ Ai b`ang ˘ π dân˜ d꯴n han chê .´ râ´t nhiê`u khi chu´,ng minh. Bây gio`,ta xet m ´ ênh . dê¯` rông ho .,n Q(n) : Nê´u 0 < Ai ≤ π, i = 1, . . . , n, khi d¯o´ sin A1 + · · · + sin An ≤ n sin A1 + · · · + An n. Ta thâ´y r `ang ˘ Q(n) suy ra P(n). ro r ˜ ang ` Q(1) d¯ung. Gi ´,a s,u, Q(k) d¯ung, v ´ a gi `,a s,u,co´ 0 < Ai ≤ π, i = 1, . . . , k + 1, khi d¯o´ sin A1 + · · · + sin Ak + sin Ak+1 ≤ k sin(A1 + · · · + Ak k) + sin Ak+1 k + 1sin(A1 + · · · + Ak = (k + 1)[ k k) + 1 k + 1sin Ak+1] k + 1(A1 + · · · + Ak ≤ (k + 1)[sin(k k) + 1 k + 1Ak+1)] ≤ (k + 1) sin(A1 + · · · + Ak + Ak+1 k + 1). Trong biê´n dô¯,i hai bâ´t d¯,ang th ˘ u´,c sau cung câ ` `n ph,ai chu´,ng minh cho hai goc c ´ o´ d¯anh gi ´ a nhu ´,trên co thê ´,chu´,ng minh du¯,o.,c (ban. d¯oc h . ay kiê ˜,m tra lai). Nhu .,vây t . u`,su.,d¯ung ´ d¯´an c ˘,ua mênh . dê¯` Q(k + 1) suy ra P(k + 1) cung ˜ d¯ung. ´ J . Cho uil `a sô´ hang th . u´,i c,ua d ˜ay Fibonacci. Chu´,ng Vı d´ u 2.30. minh r `˘ang u2n+1 + u2n = u2n+1. Lo`,i gi,ai. Kh,ang ˘ d¯.inh d¯ung v ´ o´,i n = 1. Gi,a s,u, mênh . dê¯` d¯ung v ´ o´,i 2.6. Quy nap to . an h ´ oc v . a tô `,ng quat ho ´ a´ 57 n = k. Khi d¯o´ u2k+2 + u2k+1 = (uk+1 + uk)2 + u2k+1 = u2k+1 + 2uk+1uk + u2k + u2k+1 = (u2k+1 + u2k) + (2uk+1uk + u2k+1) = u2k+1 + (2uk+1uk + u2k+1). Theo công thu´,c day Fibonacci th ˜ `ı bu,o´,c quy nap. du¯,o.,c chu´,ng minh hoan to ` an nê ` ´u ta ch,ı ra r `ang ˘ 2uk+1uk + u2k+1 = u2k+2. Do co công ´ thu´,c d¯o nên ´ u2k+1 + (2uk+1uk + u2k+1) = u2k+1 + u2k+2 = u2k+3. Bây gio`,ch,ı con ch ` u´,ng minh 2uk+1uk + u2k+1 = u2k+2. Ta cung tiê ˜ ´n hanh theo quy n ` ap, v . o´,i n = 1 công thu´,c d¯ung hiê ´,n nhiên, gi,a s,u, d¯ung v ´ o´,i n = k ta co´ 2uk+2uk+1 + u2k+2 = 2(uk+1 + uk)uk+1 + u2k+2 = 2u2k+1 + 2ukuk+1 + u2k+2 = (2uk+1uk + u2k+1) + (u2k+1 + u2k+2) = u2k+2 + (u2k+1 + u2k+2). Chung ta l ´ ai vu .,o´,ng ph,ai bai to ` an ban ´ dâ¯`u, nê´u d¯,ang th ˘ u´,c sau d¯ung ´ u2k+1 + u2k+2 = u2k+3. Nê´u co v ´ ây th .`ı u2k+2 + (u2k+1 + u2k+2) = u2k+2 + u2k+3 = u2k+4 va bu `,o´,c quy nap phâ .`n nay ho ` an to ` an xong. ` Kê´t qu,a la nê ` ´u d¯ung m ´ ênh . dê¯` thu´,nhâ´t th`ı d¯ung m ´ ênh . dê¯` thu´, hai va ngu `,o.,c lai. Th . u.,c ra bai to ` an x ´ et hai d ´ ay m ˜ ênh . dê¯` P(n) : u2n+1 + u2n+1 = u2n+1, Q(n) : 2un+2un+1 + u2n+2 = u2n+2. P(1) va` Q(1) dê¯`u d¯ung. Theo l ´ y lu ´ ân c .,ua phâ`n trên thâ´y r `ang ˘ P(k) va` Q(k) d¯ung suy ra ´ P(k + 1) d¯ung, v ´ a v ` o´,i P(k + 1) va` Q(k) lai suy ra . Q(k + 1) d¯ung. Nhu ´,vây t . u`,P(k) va` Q(k) suy ra P(k + 1) va` Q(k + 1) dê¯`u d¯ung. ´ J 58 Chu,o,ng 2. Ky thu ˜ ât phu .,o,ng phap quy n ´ ap to . an h ´ oc. 2.7. BAI T ` ÂP. . 2.31. Cho x1 < x2 < . . . < xn la nh ` u˜,ng sô´ nguyên du,o,ng. Chu´,ng minh bâ´t d¯,ang th ˘ u´,c (x51 + x52 + · · · + x5n) + (x71 + x72 + · · · + x7n) ≥ 2(x31 + x32 + · · · + x3n)2. (2.27) Chu´,ng minh r `ang ˘ d¯,ang th ˘ u´,c ch,ı xâ,y ra khi va ch `,ı khi xk = k (k = 1, 2, . . . , n). . 2.32. Chu´,ng minh bâ´t d¯,ang th ˘ u´,c (a1 + a2 + · · · + ak)2 ≤ k(a21 + a22 + · · · + a2k), (2.28) ,o,dây ¯ k ≥ 1 la sô ` ´tu.,nhiên va` a1, a2, . . . , akla nh ` u˜,ng sô´thu.,c bâ´t ky.` . 2.33. Cho f(x) = (x2 − 1)1/2, x > 1. Chu´,ng minh r `ang ˘ f(n)(x) > 0 vo´,i n l,e va` f(n)(x) < 0 vo´,i n ch˜an. ˘ . 2.34. Chu´,ng minh r `ang phu ˘,o,ng tr`ınh x2 + y2 = znco nghi ´ êm. nguyên (x, y, z) vo´,i moi. n = 1, 2, 3, . . . CHU,O,NG 3 T`IM CÔNG THU´,C TÔ,NG QUAT ´ 3.1. Câ´p sô´công v . a câ ` ´p sô´nhân . . . . . . . . . . . . . . . . . . . . . . . . 59 3.2. T´ınh tô,ng va sô ` ´hang tô .,ng quat ´ . . . . . . . . . . . . . . . . . . . . . . 68 3.3. Phu,o,ng tr`ınh truy hô`i tuyê´n t´ınh . . . . . . . . . . . . . . . . . . . . . . 73 3.4. Tô,ng nhu˜,ng luy th ˜ u`,a cung b ` âc sô .´ tu.,nhiên . . . . . . . . . . 86 3.5. Bai t ` âp.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Phu,o,ng phap quy n ´ ap to . an h ´ oc gô .`m hai bu,o´,c nhu,hai chu,o,ng tru,o´,c ta d¯a kh ˜,ao sat. Bu ´,o´,c co,s,o,chuyê,n sang bu,o´,c gi,a thiê´t quy nap l . a râ ` ´t quan trong, n . o´ d¯oi h `,oi nhiê`u kinh nghiêm gi .,ai toan, ´ phan´ do¯ an´ d¯ung, ´ du¯,a ra kh,ang ˘ d¯.inh chung ch´ınh xac v ´ a c ` o l ´ y.´ Chu,o,ng nay ta d ` u`,ng lai vi . êc thiê .´t lâp m . ôt sô .´ cach t ´ `ım công thu´,c tô,ng quat cho c ´ ac m ´ ênh . dê¯` kh,ang ˘ d¯.inh la d ` ay sô ˜ ´. Sau khi t`ım ra tô,ng ta co thê ´,chu´,ng minh b`ang quy n ˘ ap to . an h ´ oc.. 3.1. C´ÂP SÔ C´ ÔNG V . A C`´ÂP SÔ NHÂN ´ Trong cac chu ´,o,ng tr`ınh phô,thông ta d¯a h ˜ oc câ .´p sô´ công v . a` câ´p sô´ nhân, ,o,dây ta nh ¯´ac l ˘ ai hai công th . u´,c t´ınh tô,ng nhu,ng du¯,o.,c chu´,ng minh b`ang quy n ˘ ap. . 60 Chu,o,ng 3. T`ım công thu´,c tô,ng quat´ . Chu´,ng minh d¯,˘ang thu´,c sau: Vı d´ u 3.1. 1 + q + q2 + · · · + qn =1 − qn+1 1 − q, (3.1) vo´,i moi. q 6= 1 v `a vo´,i moi. n = 0, 1, 2, . . . (câ´p sô´ nhân). Lo`,i gi,ai. Gi,a thiê´t quy nap c . o ngay trong ´ dâ¯`u bai. ` Ð.at˘ Sn = 1 + q + · · · + qn. Vo´,i n = 0, S0 = 1 công thu´,c (3.1) d¯ung. ´ Gi,a s,u,vo´,i sô´tu.,nhiên n = k nao` d¯o ta c ´ o´ d¯,ang th ˘ u´,c Sk =1 − qk+1 1 − q. Ta se ch ˜ u´,ng minh d¯,ang th ˘ u´,c d¯ung v ´ o´,i sô´ tu.,nhiên tiê´p theo, ngh˜ıa la` Thât v . ây,. Sk+1 =1 − qk+2 1 − q. Sk+1 = Sk + qk+1 =1 − qk+1 1 − q+ qk+1 =1 − qk+2 1 − q. J . Cho b v `a d l `a hai sô´. T`ım sô´ hang tô .,ng qu ´at an c,ua Vı d´ u 3.2. d ˜ay, du¯,o.,c x ´ac d¯.inh theo công thu´,c sau (câ´p sô´ công): . a1 = b, an = an−1 + d (n = 2, 3, . . .). Lo`,i gi,ai. Ta câ`n t`ım sô´hang . an theo nhu˜,ng sô´d¯a cho ˜ b va` d, cung ˜ nhu,ch,ı sô´ n d¯a cho. Ta t ˜ ´ınh môt sô .´ gia tr ´ .i: a1 = b, a2 = a1 + d = b + d, a3 = a2 + d = (b + d) + d = b + 2d, a4 = a3 + d = b + 3d. Dê˜ dang ` du¯,a ra gi,a thiê´t quy nap. an = b + (n − 1).d. (3.2) 3.1. Câ´p sô´ công v . a câ ` ´p sô´ nhân 61 Ta se ch ˜ u´,ng minh (3.2) d¯ung v ´ o´,i moi sô .´tu.,nhiên n. Thât v . ây,. Bu,o´,c co,s,o,: Vo´,i n = 1, (3.2) d¯ung v ´ o´,i cach t ´ ´ınh phâ`n trên. Bu,o´,c quy nap.: Gi,a s,u,(3.2) d¯ung v ´ o´,i sô´tu.,nhiên n nao` d¯o. Khi ´ d¯o, t ´ u`,(3.2) cho ta kê´t qu,a an+1 = an + d = [b + (n − 1)d] + d = b + nd. Nhu,vây ( . 3.2) d¯ung v ´ o´,i moi sô .´tu.,nhiên n. J Bây gio`,ta xet câ ´ ´p sô´ công v . a câ ` ´p sô´nhân ma công sai v ` a công ` bôi c .,ua chung không l ´ a h``ang sô ˘ ´, chung biê ´ ´n dô¯,i nhu,sô´hang tô .,ng quat c ´,ua câ´p sô´ công ho . .ac câ ˘ ´p sô´ nhân. . Cho môt d ˜ay sô .´ n sô´ hang . Vı d´ u 3.3. a1 = a1, a2 = a1 + d1, a3 = a2 + d2, . . . , an = an−1 + dn−1, (3.3) ,o,dây d ˜ay sô ¯ ´ d1, d2, . . . , dn−1 l `a môt câ .´p sô´ công v . o´,i công sai d 6= 0 (câ´p sô´ công-c . ông) . Ch . u´,ng minh r `˘ang ak = a1 + (k − 1)d1 +12(k − 1)(k − 2)d, (3.4) Sn = n(a1 + d − d1) + n(n − 1)(2d1 − 3d) 4+n(n + 1)(2n + 1)d 12 . (3.5) Lo`,i gi,ai. Công thu´,c trên co thê ´,chu´,ng minh b`ang phu ˘,o,ng phap´ quy nap nhu .,ng dê¯,ng´an g ˘ on ta ch .,ı dung phu `,o,ng phap t ´ ´ınh toan´ va biê ` ´n dô¯,i. Day sô ˜ ´ (3.3) goi l . a câ ` ´p sô´ công-c . ông v . o´,i sô´ hang th . u´, k, ak, công sai thu´,k, dk va công sai ` d. Dê d ˜ ang c ` o´ ak = a1 + d1 + d2 + · · · + dk−1. Vo´,i day sô ˜ ´ la c ` ac sô ´ ´ gia c,ua (3.3) ta co´ dk = d1 + (k − 1)d, 2k =2d1 + (k − 1)d d1 + d2 + · · · + dk =d1 + dk 2k. 62 Chu,o,ng 3. T`ım công thu´,c tô,ng quat´ Vây. ak = a1 + (k − 1)d1 +12(k − 1)(k − 2)d. Tô,ng c,ua nhu˜,ng sô´ hang câ .´p sô´ công-c . ông t .´ınh du¯,o.,c nhu,sau: Sn = n∑ k=1 ak = n∑ k=1 [(a1 + d − d1) + (d1 −32d)k +d2k2] = n(a1 + d − d1) + (d1 −32d)n∑k=1k +d2n∑k=1k2, Tu`,dây suy ra công th ¯ u´,c (3.5). J . Cho môt d ˜ay sô .´ n sô´ hang . Vı d´ u 3.4. a1 = a1, a2 = a1 + d1, a3 = a2 + d2, . . . , an = an−1 + dn−1, ,o,dây d ˜ay sô ¯ ´ d1, d2, . . . , dn−1 l `a môt câ .´p sô´nhân vo´,i công bôi. q 6= 1 (câ´p sô´ công-nhân). Ch . u´,ng minh r `˘ang ak = a1 +d1(qk−1 − 1) q − 1(3.6) 1 − q) + d1(qn − 1) Sn = n(a1 +d1 (q − 1)2. (3.7) Lo`,i gi,ai. Tu`,gi,a thiê´t c,ua bai to ` an v ´ a công th ` u´,c cho câ´p sô´ công . va câ ` ´p sô´ nhân ta co công th ´ u´,c dk = d1qk−1, d1 + d2 + · · · + dk =d1(qk − 1) q − 1. Ta dê d˜ ang t ` ´ınh du¯,o.,c ak = a1 + d1 + d2 + · · · + dk−1 = a1 +d1(qk−1 − 1) q − 1. 3.1. Câ´p sô´ công v . a câ ` ´p sô´ nhân 63 Tu`,d¯,ang th ˘ u´,c sau cung suy ra ` Sn = n∑ k=1 ak = n∑ k=1 [(a1 +d1 1 − q) + d1 q − 1qk−1] 1 − q) + d1(qn − 1) = n(a1 +d1 . Cho d ˜ay hu˜,u han. n sô´ Vı d´ u 3.5. (q − 1)2. J a1 = a1, a2 = a1q1, a3 = a2q2, . . . , an = an−1qn−1, (3.8) ,o,dây d ˜ay sô ¯ ´ q1, q2, . . . , qn−1 l `a câ´p sô´ công v . o´,i công sai d 6= 0. D ˜ay sô´ (3.8) goi l `a câ .´p sô´ nhân-công v . o´,i sô´ hang th . u´,k, ak, công bôi. thu´,k, qk v `a công sai d. H ˜ay lâp công th . u´,c t´ınh sô´ hang tô .,ng qu ´at c,ua câ´p sô´ nhân-công v `a tô .,ng nhu˜,ng sô´ hang . d⯠`u c,ua n´o. Lo`,i gi,ai. V`ı qk = q1 + (k − 1)d, th`ı ta co´ ak = a1q1q2 . . . qk−1 = a1 k−1 ∏ l=1 ql = a1 k−1 ∏ l=1 [q1 + (l − 1)d] 1 + Sk−2 1dqk−2 1 + Sk−2 = a1[qk−1 + Sk−2 2d2qk−3 1 + · · · k−3dk−3q21 + Sk−2 k−2dk−2q1] ho .ac l ˘ a`  k−2 Sk−2 1, vo´,i k = 2, 3, . . . , n; ak = a1  ∑ l=0 ldlqk−l−1 a1 vo´,i k = 1, ,o,dây ¯ Sn0 = 1 vo´,i n = 0, 1, 2, . . ., con` Snivo´,i 0 < i ≤ n va` i nguyên, la tô `,ng c,ua tâ´t c,a cac t ´ ´ıch dang . p1 p2...pi, Nhu˜,ng thu`,a sô´ c,ua môi˜ t´ıch la` i sô´, hoan to ` an kh ` ac nhau v ´ a nh ` ân gi . a tr ´ .i nguyên tu`,1 d꯴n n. Nê´u trong tô,ng Snita nhom nh ´ u˜,ng sô´ hang không ch . u´,a sô´ n nhu, môt sô .´ hang, v . a c ` ac sô ´ ´ hang c . o ch ´ u´,a n nhu, môt th . u`,a sô´, va` sau d¯o´,o,nhom th ´ u´,hai ta du¯,a n ra ngoai ngo ` .ac, ta s ˘ e nh ˜ ân. du¯,o.,c Sni = Sn−1 i + nSn−1 i−1. (3.9) 64 Chu,o,ng 3. T`ım công thu´,c tô,ng quat´ Ta dung ( ` 3.9) viê´t cac gi ´ a tr ´ .i Snivao b `,ang tam giac m ´,o,rông . d꯴n vô cung nhu `,sau t 0 1 2 3 4 5 6 7 . . . 0 1 . . . 1 1 1 . . . 2 1 3 2 . . . 3 1 6 11 6 . . . 4 1 10 35 50 24 . . . 5 1 15 85 225 274 120 . . . 6 1 21 175 735 1624 1764 720 . . . 7 1 28 322 1960 6769 13132 13068 5040 . . . ... ... ... ... ... ... ... ... ... . . . B,ang trên co nhiê ´ `u t´ınh châ´t râ´t hay, v´ı du. du¯,o`,ng cheo l ´ a` an = n!, n = 0, 1, 2, . . ., nhu,ng ta không nghiên cu´,u,o,dây. ¯ Bây gio`,ta t`ım công thu´,c tô,ng Sn c,ua câ´p sô´ nhân-công. T . u`, (3.9) ta co´ d¯,ang th ˘ u´,c a1 = a1, a2 = a1S00q1, a3 = a1(S10.q21 + S11.d.q1) ............................... ak = a1(Sk−2 0qk−1 1 + Sk−2 1dqk−2 1 + · · · + Sk−2 k−2dk−2q1) Công theo vê .´ c,ua cac´ d¯,ang th ˘ u´,c trên va s `´ap xê ˘ ´p theo sô´ mu˜ tang dâ ˘ `n c,ua q1 ta nhân. du¯,o.,c Sk = a1[1 + q11(1 + S11d1 + S22d2 + · · · + Sk−2 k−1dk−2) + q21(1+ S21d1 + S32d2 + · · · + Sk−2 k−3dk−3) + · · · + qk−2 1(1+ Sk−2 1d) + qk−1 1], 3.1. Câ´p sô´ công v . a câ ` ´p sô´ nhân 65 ho .ac l ˘ a` Sn = a1 " 1 + n−1 ∑ i=1 n−i−1 ∑ k=0 Si+k−1 kdk ! qi1 # . J . Cho d ˜ay hu˜,u han. n sô´ Vı d´ u 3.6. a1 = a1, a2 = a1q1, a3 = a2q2, . . . , an = an−1qn−1, (3.10) ,o,dây d ˜ay sô ¯ ´ q1, q2, .., qn−1 l `a câ´p sô´ nhân vo´,i công bôi. q 6= 1. D ˜ay sô´ hu˜,u han trên g . oi l `a câ .´p sô´ nhân-nhân vo´,i thu`,a sô´ thu´,k l `a ak, k-công bôi l `a . qk v `a công bôi. q. H ˜ay lâp công th . u´,c t´ınh sô´ hang . tô,ng qu ´at v `a tô,ng n sô´ hang . d⯠`u tiên c,ua d ˜ay câ´p sô´ nhân-nhân. Lo`,i gi,ai. Ta d¯a biê ˜ ´t qk = q1qk−1, khi d¯o´ 1q1+2+3+···+(k−2) ak = a1q1q2 . . . qk−1 = a1qk−1 hay la` ak = a1qk−1 1q (k − 2)(k − 1) 2 , Sn = n∑ k=1 ak = a1q n∑ k=1 qk−1 1q k(k − 3) 2 . Nhu˜,ng day sô ˜ ´,o,cac b ´ ai t ` âp trên g . oi l . a c ` ac d ´ ay c ˜ .ap˘ dôi. Ðê ¯, m,o,rông ho .,n nu˜,a du.,a trên co,s,o,c,ua câ´p sô´ công v . a câ ` ´p sô´ nhân ngu,o`,i ta lai gh . ep thêm c ´ ac câ ´ ´p sô´ c .ap˘ dôi m ¯ ôt lâ .`n nu˜,a, ta lâ´y v´ı du sau: Ta x . et d ´ ay h ˜ u˜,u han t . u`,n sô´ b1, b2 = b1 + a1, b3 = b2 + a2, . . . , bn = bn−1 + an−1 ,o,dây d ¯ ay sô ˜ ´ a1, a2, . . . , an−1 la câ ` ´p sô´ công-c . ông v . o´,i công sai d va` công sai thu´,k la` dk. Khi d¯o v ´ `ı bk = b1 + a1 + a2 + · · · + ak−1 va v ` `ı 66 Chu,o,ng 3. T`ım công thu´,c tô,ng quat´ (3.4) ta t`ım du¯,o.,c sô´ hang th . u´,k c,ua câ´p sô´ c .ap ba ˘ bk = b1 + (k − 1)(a1 + d − d1) 4+(k − 1)k(2k − 1)d +(k − 1)k(2d1 − 3d) Tô,ng nhu˜,ng sô´ hang c .,ua day ta t ˜ `ım du¯,o.,c 12 . (3.11) Sn = n∑ k=1 bk = n∑ k=1 [(b1 + d1 − a1 − d) +k(a1 −32d1 +116d) + k2(d12− d) + k2d6 . Ta nhân. du¯,o.,c Sn = n(b1 + d1 − a1 − d) + n(n + 1)(6a1 − 9d1 + 11d) 12 (3.12) 12 +n2(n + 1)2d +n(n + 1)(2n + 1)(d1 − 2d) 24 . J Ðê,minh hoa. ap d ´ ung công th . u´,c trên ta xet b ´ ai t ` âp: . . T`ım sô´ hang tô .,ng qu ´at c,ua d ˜ay câ´p sô´ c .˘ap ba sau dây ¯ Vı d´ u 3.7. 2, 5, 9, 17, 32, 57, 95, . . . (3.13) v `a t´ınh tô,ng n sô´ hang . d⯠`u tiên. Lo`,i gi,ai. Day t ˜ ao ra b .,o,i nhu˜,ng hiêu liên tiê .´p c,ua day˜ d¯a cho l ˜ a` 3, 4, 8, 15, 25, 38, . . . Tiê´p tuc t . ao ra d . ay gô ˜ `m nhu˜,ng hiêu c .,ua cac phâ ´ `n t,u,la` 1, 4, 7, 10, 13, . . . (3.14) dây l ¯ a câ ` ´p sô´ công c . o sô ´ ´hang . dâ¯`u tiên la` d1 = 1 va công sai ` d = 3. V`ı b1 = 2, a1 = 3, theo công thu´,c (3.11) sô´hang tô .,ng quat cho d ´ ay˜ (3.13) la` bn =12(n3 − 5n2 + 14n − 6). 3.1. Câ´p sô´ công v . a câ ` ´p sô´ nhân 67 Vê` tô,ng c,ua n sô´ hang . dâ¯`u theo công thu´,c (3.12) ta co´ Sn =124n(3n3 − 14n2 + 57n + 2). J . T`ım công thu´,c t´ınh tô,ng Vı d´ u 3.8. Sn = 3.2 + 5.5 + 7.8 + · · · + (2n + 1)(3n − 1). Lo`,i gi,ai. Nê´u chung ta l ´ ai l . .ap l ˘ ai c . ach th ´,u, mâ´y gia tr ´ .i ban dâ¯`u va mâ ` `y mo t ` `ım kê´t qu,a th`ı kha vâ ´ ´t v,a. Ta hay nh ˜ `ın ky v ˜ ao` dê¯` bai v ` a` d¯.at sô ˘ ´ hang tô .,ng quat´ an = (2n + 1)(3n − 1). Ta thâ´y r `ang ˘ thu`,a sô´thu´,nhâ´t la câ ` ´p sô´ công v . a th ` u`,a sô´thu´,hai cung l ˜ a câ ` ´p sô´ công. Câu h .,oi d¯.at ra l ˘ a d ` u.,a vao công th ` u´,c d¯a c ˜ o c ´,ua câ´p sô´ công . co t ´ ´ınh du¯,o.,c tô,ng Sn,o,trên không? Bai to ` an c ´ o thê ´,ph,ai du¯,a vê` tru,o`,ng ho.,p tô,ng quat ho ´,n: T´ınh tô,ng Sn = a1b1 + a2b2 + · · · + anbn vo´,i a1, a2, . . . , an la câ ` ´p sô´ công c . o công sai ´ da va` b1, b2, . . . , bn la câ ` ´p sô´ công c . o công sai ´ db. Ta co´ Sn = n∑ k=1 akbk = n∑ k=1 [a1 + (k − 1)da].bk = n∑ k=1 [(a1 − da) + kda].bk = (a1 − da) n∑ k=1 bk + da n∑ k=1 k.bk = (a1 − da)2b1 + (n − 1)db 2n + da n∑ k=1 k.[(b1 − db) + kdb] = (a1 − da)2b1 + (n − 1)db 2n + da(b n∑ k=1 k + dadb n∑ k=1 k2 = (a1 − da)(b1 − db)n +12[da(b1 − db) + db(a1 − da)]n(n + 1)+ +16dadbn(n + 1)(2n + 1). 68 Chu,o,ng 3. T`ım công thu´,c tô,ng quat´ Ho .ac l ˘ a`Sn =13dadbn3 +12(dab1 + dba1 − dadb)n2 +16(6a1b1 − 3dba1 − 3dab1 + dadb)n. (3.15) Áp dung công th . u´,c (3.15) vao v ` ´ı du trên v . o´,i a1 = 3, da = 2, b1 = 2, db = 3. Ta co kê ´ ´t qu,a Sn =12n(4n2 + 7n + 1). Công thu´,c tô,ng quat trên ´ d¯a t ˜ ´ınh du¯,o.,c qua tru.,c tiê´p biê´n dô¯,i. Vo´,i công thu´,c nay ta c ` ung c ˜ o thê ´,chu´,ng minh b`ang quy n ˘ ap to . an h ´ oc. (danh cho b ` an. d¯oc). Nhu .,ng nhiê`u khi chu´,ng minh b`ang quy n ˘ ap. toan h ´ oc d . ân˜ d꯴n biê´n dô¯,i biê,u thu´,c vô cung ph ` u´,c tap l . am n `,an long ch ` ung ta. M ´ ôi phu ˜,o,ng phap ch ´,ı manh v . o´,i môt l . o´,p bai to ` an´ nao` d¯o thôi. ´ 3.2. T´INH TÔ,NG VA S ` Ô H ´ ANG TÔ .,NG QUAT ´ Chu,o,ng tru,o´,c ta d¯a quan s ˜ at c ´ ac phu ´,o,ng an kh ´ ac nhau c ´,ua phu,o,ng phap quy n ´ ap, nhiê .`u khi di t ¯ `ım môt sô .´ hang tô .,ng quat´ ho .ac m ˘ ôt tô .,ng c,ua môt d . ay ngu ˜,o`,i ta ap d ´ ung phu .,o,ng phap quy ´ nap to . an h ´ oc m . ôt c . ach hiê ´,n nhiên do cac bu ´,o´,c hô`i quy liên tiê´p ma ta t ` `ım du¯,o.,c công thu´,c tô,ng quat. Nh ´ u˜,ng v´ı du sau . dây minh ¯ hoa phu .,o,ng phap quy n ´ ap n . ay. ` . Dây sô ˜ ´ a0, a1, a2, . . . du¯,o.,c xây du.,ng theo c ´ach sau: Hai Vı d´ u 3.9. sô´ d⯠`u a0 v `a a1 l `a nhu˜,ng sô´ d ˜a cho, m ¯ ôi sô ˜ ´ sau d ´o l `a trung b`ınh ¯ công c .,ua hai sô´ tru,o´,c d´o. H ˜ay biê ¯,u di˜ên an theo a0, a1 v `a n. Lo`,i gi,ai. Ta co´ a2 =a0 + a1 2, a3 =a1 + a2 2, a4 =a2 + a3 2, a5 =a3 + a4 2, . . . 3.2. T´ınh tô,ng va sô ` ´ hang tô .,ng quat´ 69 tu`,d¯o suy ra ´ a2 − a1 =a0 − a1 2, a3 − a2 =a1 − a2 2, a4 − a3 =a2 − a3 2, . . . Suy raa2 − a1 = −a1 − a0 2 a3 − a2 = −a2 − a1 2=a1 − a0 22 2= −a1 − a0 a4 − a3 = −a3 − a2 ................ 23 Dê thâ ˜ ´y r `ang (phu ˘,o,ng phap quy n ´ ap to . an h ´ oc. du¯,o.,c ap d ´ ung . ,o,dây) ¯ an − an−1 = (−1)n−1a1 − a0 2n−1. Công theo vê .´ c,ua cac´ d¯,ang th ˘ u´,c trên, ta co´ an − a1 = −a1 − a0 2+a1 − a0 23 + · · · + (−1)n−1a1 − a0 2n−1 = −a1 − a0 22 −a1 − a0 2(1 −12+122 + · · · + (−1)n−21 2n−2) =a1 − a0 3{(−1)n−11 Tu`,d¯o suy ra ´ 2n−1 − 1}. an =2a1 + a0 3+ (−1)n−1a1 − a0 3.2n−1. J . D ˜ay sô´ a1, a2, a3, . . . du¯,o.,c x ´ac d¯.inh theo công thu´,c Vı d´ u 3.10. a1 = 2 v `a an = 3an−1 + 1. H ˜ay t´ınh a1 + a2 + · · · + an. Lo`,i gi,ai. Ta xet´ d¯,ang th ˘ u´,c ak = 3ak−1 + 1. Cho k gia tr ´ .i 2, 3, 4, . . . , n va c ` ông l . ai ta nh . ân. du¯,o.,cn∑ k=2 ak = 3 n∑ k=2 ak−1 + n − 1. Ta 70 Chu,o,ng 3. T`ım công thu´,c tô,ng quat´ d¯.at˘ a1 + a2 + · · · + an = S. Khi d¯o ta c ´ o´ S − a1 = 3(S − an) + n − 1. Suy ra S =12{3an − a1 − n + 1}. Ta ch,ı con biê `,u diên˜ an qua a1. Ta co´ an = 3an−1 + 1, an−1 = 3an−2 + 1. Tu`,d¯o suy ra ´ an − an−1 = 3(an−1 − an−2). V`ı thê´ an − an−1 = 3(an−1 − an−2) = 32(an−2 − an−3) = = 33(an−3 − an−4) = · · · = 3n−2(a2 − a1). Nhu,ng a2 = 3a1 + 1 = 7, v`ı vây. an − an−1 = 5.3n−2(quy nap to . an´ hoc. d¯a d ˜ ung `,o,dây). V ¯ o´,i cac gi ´ a tr ´ .i n b`ang ˘ 2, 3, 4, . . . , n ta co´ a2 − a1 = 5.1, a3 − a2 = 5.3, a4 − a3 = 5.32, . . . . . . . . . . . . an − an−1 = 5.3n−2. Công theo c . ac vê ´ ´ c,ua d¯,ang th ˘ u´,c, ta t´ınh du¯,o.,c an − a1 = 5(1 + 3 + 32 + · · · + 3n−2) = 52(3n−1 − 1). Tu`,biê,u thu´,c c,ua S ta co´ S =12{3(an − a1) + 2a1 − n + 1} = =12{152(3n−1 − 1) + 4 − n + 1} =14{5(3n − 1) − 2n}. J . D ˜ay sô´ a1, a2, . . . x ´ac d¯.inh theo công thu´,c Vı d´ u 3.11. an = kan−1 + l (n = 2, 3, . . .). H ˜ay biê,u di˜ên an theo a1, k, l v `a n. 3.2. T´ınh tô,ng va sô ` ´ hang tô .,ng quat´ 71 Lo`,i gi,ai. Ta co´ an = kan−1 + l, an−1 = kan−2 + l. Suy ra an − an−1 = k(an−1 − an−2) = k2(an−2 − an−3) = . . . = kn−2(a2 − a1), tu`,d¯o suy ra ´a2 − a1 = (a2 − a1), a3 − a2 = k(a2 − a1), a4 − a3 = k2(a2 − a1), . . . . . . . . . an − an−1 = kn−2(a2 − a1). Công l . ai c . ac´ d¯,ang th ˘ u´,c trên ta co´ an = kn−1a1 +kn−1 − 1 k − 1l. J . Cho d ˜ay a1, a2, . . . tho ,a m ˜an d¯,˘ang thu´,c sau: Vı d´ u 3.12. an+1 − 2an + an−1 = 1. H ˜ay biê,u di˜ên an theo a1, a2 v `a n. Lo`,i gi,ai. Ta viê´t lai. d¯,ang th ˘ u´,c du,o´,i dang sau: . an+1 − an − (an − an−1) = 1. Ta d¯.at˘ an − an−1 = xn,(n = 2, 3, . . .). Khi d¯o ta c ´ o´ xn+1 − xn = 1. Thay vao` d¯,ang th ˘ u´,c sau cung gi ` a tr ´ .i n b`ang ˘ 2, 3, . . . , n − 1 va c ` ông . lai, ta nh . ân. du¯,o.,c xn − x2 = n − 2. Ta lai thay . n = 3, 4, . . . , n vao` an − an−1 = xn va c ` ông l . ai ta . nhân. du¯,o.,c an − a2 = x3 + x4 + · · · + xn. Hay la` an = a2 + x3 + x4 + · · · + xn. 72 Chu,o,ng 3. T`ım công thu´,c tô,ng quat´ Nhu,ng n∑ k=3 xk = n∑ k=3 (x2 + k − 2) Tu`,d¯o suy ra ´ = (n − 2)x2 + (n − 2) + (n − 3) + · · · + 1 = (n − 2)x2 +(n − 1)(n − 2) 2. an = a2 + (n − 2)x2 +(n − 1)(n − 2) 2 = a2 + (n − 2)(a2 − a1) + (n − 1)(n − 2) 2 =(n − 1)(n − 2) 2+ (n − 1)a2 − (n − 2)a1. J . Cho hai d ˜ay sô´a1, a2, a3, . . . Vı d´ u 3.13. b1, b2, b3, . . . du¯,o.,c x ´ac d¯.inh theo công thu´,c sau: an+1 =an + bn 2; bn+1 =2anbn an + bn ,o,dây ¯ a0 v `a b0 l `a nhu˜,ng sô´ d ˜a cho ¯ a0 > b0 > 0. T´ınh an v `a bn theo a0, b0 v `a n. Lo`,i gi,ai. Dê thâ ˜ ´y r `ang ˘ an+1bn+1 = anbn, va suy ra ` anbn = a0b0 vo´,i moi sô .´ nguyên n. Nhu,ng √an −√bn √an +√bn=an −√anbn an +√anbn=an −pan−1bn−1 an +pan−1bn−1 2−pan−1bn−1 = an−1 + bn−1 2 +pan−1bn−1= an−1+bn−1 √an−1 −pbn−1 √an−1 +pbn−1 !2 . 3.3. Phu,o,ng tr`ınh truy hô`i tuyê´n t´ınh 73 Ta d¯.at˘ √an −√bn √an +√bn= un. Khi d¯o ta c ´ o´ un−1 = u2n−2, un−2 = u2n−3, . . . . . . u2 = u21, u1 = u20. Nâng bâc l . uy th ˜ u`,a c,ua cac´ d¯,ang th ˘ u´,c lâ`n lu,o.,t vo´,i 1, 2, 22, . . . , 2n−2. Ta t´ınh du¯,o.,c un−1 = u2n−1 √an−1 −pbn−1 0. Nhu,ng un−1 = u0 = Nhu,vây ta c . o´ √an−1 +pbn−1=an−1 −√a0b0 an−1 +√a0b0, √a0 −√b0 √a0 +√b0=a0 −√a0b0 a0 +√a0b0. an−1 −√a0b0 an−1 +√a0b0= a0 −√a0b0 a0 +√a0b0 2n−1 . J 3.3. Phu,o,ng tr`ınh truy hô`i tuyê´n t´ınh Muc tru .,o´,c ta thâ´y cac b ´ ai to ` an´ dê¯`u cho day sô ˜ ´ va c ` ac sô ´ ´ hang . du¯,o.,c liên hê v. o´,i nhau b`ang công th ˘ u´,c truy hô`i. Cach gi ´,ai dê¯`u t`ım trong công thu´,c truy hô`i mô´i liên hê. dê¯,t´ınh du¯,o.,c sô´ hang tô .,ng quat v ´ a tô `,ng n sô´ hang . dâ¯`u tiên. Không ph,ai luc n ´ ao ta c ` ung ˜ co c ´ ac phu ´,o,ng tr`ınh truy hô`i d¯ep. d¯e nhu ˜,cac b ´ ai t ` âp phâ .`n tru,o´,c. Muc n . ay ta ch `,ı ra môt c . ach tô ´,ng quat t ´ ´ınh sô´ hang tô .,ng quat v ´ a` tô,ng nhu˜,ng day tho ˜,a man phu ˜,o,ng tr`ınh truy hô`i. 74 Chu,o,ng 3. T`ım công thu´,c tô,ng quat´ Cho k sô´ hang . dâ¯`u c,ua day sô ˜ ´ x1, x2, x3, . . . , xn, . . . (3.16) la` x1 = u1, x2 = u2, . . . , xk = uk. Môi sô ˜ ´ hang th . u´,k + 1 c,ua day˜ (3.16) tô`n tai mô .´i liên hê. xk+n + a1xn+k−1 + a2xn+k−2 + · · · + akxn = bn, (3.17) ,o,dây ¯ a1, a2, . . . , akla nh ` u˜,ng sô´ d¯a cho, c ˜ on` b1, b2, . . . , bn, . . . la d ` ay˜ d¯a cho. Khi ˜ d¯o ( ´ 3.17) cho phep ta t ´ ´ınh du¯,o.,c moi phâ .`n t,u,liên tiê´p c,ua day ( ˜ 3.16) va sau ` d¯o ta cô ´ ´ g´ang biê ˘,u diên sô ˜ ´ hang tô .,ng quat´ c,ua chung. X ´ et v ´ ´ı du. . T`ım công thu´,c tô,ng qu ´at c,ua d ˜ay x ´ac d¯.inh nhu,sau: Vı d´ u 3.14. x1 = 5, x2 = 19, xn − 5xn−1 + 6xn−2 = 0. Lo`,i gi,ai. Tu`, mô´i liên hê hô .`i quy xn = 5xn−1 − 6xn−1, ta t`ım du¯,o.,c x1 = 5 = 32 − 22, x2 = 19 = 33 − 23, x3 = 5x2 − 6x1 = 65 = 34 − 24, x4 = 5x3 − 6x2 = 211 = 35 − 25, x5 = 5x4 − 6x3 = 665 = 35 − 25, x6 = 5x5 − 6x4 = 2059 = 36 − 26. Ta gi,a thiê´t r `ang sô ˘ ´ hang tô .,ng quat c ´,ua day c ˜ o d´ ang . xn = 3n+1 − 2n+1. (3.18) Gi,a thiê´t du¯,o.,c chu´,ng minh b`ang phu ˘,o,ng phap quy n ´ ap. . 1) Ta d¯a kiê ˜,m tra (3.18) d¯ung v ´ o´,i n = 1 va` n = 2. 2) Ta gi,a thiê´t (3.18) d¯ung v ´ o´,i n = k va` n = k + 1, ngh˜ıa la` xk = 3k+1 − 2k+1 va` xk+1 = 3k+2 − 2k+2. Khi d¯o ta t ´ `ım du¯,o.,c xk+2 = 5xk+1 − 6xk = 5(3k+2 − 2k+2) − 6(3k+1 − 2k+1) = (15 − 6)3k+1 − (10 − 6)2k+1 = 3k+3 − 2k+3. 3.3. Phu,o,ng tr`ınh truy hô`i tuyê´n t´ınh 75 Nhu,vây ( . 3.18) d¯ung v ´ o´,i n = k + 2. Theo nguyên ly quy n ´ ap to . an´ hoc suy ra ( . 3.18) d¯ung v ´ o´,i moi. n. J Phu,o,ng tr`ınh (3.17) goi. phu,o,ng tr`ınh hô`i quy tuyê´n t´ınh bâc. k. Nhu˜,ng sô´ a1, a2, a3, . . . , ak goi l . a` nhu˜,ng hê sô .´, con` bn goi l . a` sô´ hang t . u.,do. Khi vo´,i moi. n, bn = 0 phu,o,ng tr`ınh goi l . a` thuâ`n nhâ´t. Bai to ` an´ d¯.at ra l ˘ a t ` `ım cach biê ´,u diên sô ˜ ´ hang tô .,ng quat´ xn qua cac´ d¯ai lu .,o.,ng ban dâ¯`u d¯a cho. Trong m ˜ uc n . ay ta ch `,ı xet´ phu,o,ng tr`ınh truy hô`i bâc hai. . . T`ım sô´ hang tô .,ng qu ´at xn cho phu,o,ng tr`ınh truy hô`i Vı d´ u 3.15. thuâ`n nhâ´t bâc hai: . a0xn+2 + a1xn+1 + a2xn = 0. (3.19) Lo`,i gi,ai. Ta goi.t1 va` t2 la nghi ` êm c .,ua phu,o,ng tr`ınh bâc hai . a0t2 + a1t + a2 = 0 (a0 6= 0, a2 6= 0). Khi d¯o theo công th ´ u´,c Viet a0(t1 + t2) = −a1, a0t1t2 = a2. Phu,o,ng tr`ınh (3.19) co thê ´,viê´t du,o´,i dang . xn+2 − (t1 + t2)xn+1 + t1t2xn = 0. (3.20) Sô´ hang tô .,ng quat c ´,ua day˜ d¯a cho ph ˜ u thu . ôc v . ao hai gi ` a tr ´ .i t1 va` t2 khac nhau ho ´ .ac b ˘`ang nhau: ˘ 1) Tru,o`,ng ho.,p t1 6= t2: Thay n b`ang ˘ n − 2 vao ( ` 3.20) ta nhân. du¯,o.,c xn − (t1 + t2)xn−1 + t1t2xn−2 = 0. (3.21) Ta viê´t lai. xn − t2xn−1 = t1(xn−1 − t2xn−2). (3.22) 76 Chu,o,ng 3. T`ım công thu´,c tô,ng quat´ Thay n b`ang c ˘ ac gi ´ a tr ´ .i n − 1, n − 2, . . . , 4, 3 vao ( ` 3.22) ta nhân. du¯,o.,c xn−1 − t2xn−2 = t1(xn−2 − t2xn−3) xn−2 − t2xn−3 = t1(xn−3 − t2xn−4) . . . . . . x4 − t2x3 = t1(x3 − t2x2) x3 − t2x2 = t1(x2 − t2x1). (3.23) Nhân cac vê ´ ´ tu,o,ng u´,ng c,ua (3.22) va ( ` 3.23), gi,an u,o´,c thu`,a sô´ chung, ta nhân. du¯,o.,c xn − t2xn−1 = tn−2 1(x2 − t2x1). (3.24) Tu,o,ng tu.,viê´t (3.21) du,o´,i dang . xn − t1xn−1 = t2(xn−1 − t2xn−2) va sau ` d¯o thay ´ n b`ang c ˘ ac gi ´ a tr ´ .i n − 1, n − 2, . . . , 4, 3, cung t ˜ ´ınh du¯,o.,c xn − t1xn−1 = tn−2 Tu`,(3.24) va ( ` 3.25) ta co´ t1xn − t2xn = tn−1 2(x2 − t1x1). (3.25) 1(x2 − t2x1) − tn−1 Ho .ac l ˘ a nghi ` êm c .,ua (3.19) co d´ ang . 2(x2 − t1x1). xn = C1tn1 + C2tn2, (3.26) ,o,dây ¯ C1 =x2 − t2x1 t1(t1 − t2), C2 =t1x1 − x2 t2(t1 − t2). (3.27) Ngu,o.,c lai,. C1 va` C2 la nh ` u˜,ng h`ang sô ˘ ´ bâ´t ky, kiê `,m tra tru.,c tiê´p day v ˜ o´,i sô´ hang tô .,ng quat ( ´ 3.26) la nghi ` êm c .,ua phu,o,ng tr`ınh â,n (3.19). Gia tr ´ .i duy nhâ´t c,ua day˜ {xn} du¯,o.,c xac´ d¯.inh, nê´u cho hai gia tr ´ .i ban dâ¯`u c,ua day. Khi ˜ d¯o´ C1 va` C2 xac´ d¯.inh theo công thu´,c (3.27). 3.3. Phu,o,ng tr`ınh truy hô`i tuyê´n t´ınh 77 Tr ,o,lai v .´ı du trên th .`ı t1 = 3, t2 = 2 la nghi ` êm c .,ua phu,o,ng tr`ınh bâc hai .t2 − 5t + 6 = 0. Khi d¯o nê ´ ´u C1 va` C2 la nh ` u˜,ng h`ang ˘ sô´ bâ´t ky, th ` `ı day v ˜ o´,i sô´ hang tô .,ng quat´ xn = C1.3n + C2.2n la nghi ` êm c .,ua phu,o,ng tr`ınh truy hô`i xn − 5xn−1 + 6xn−2 = 0. Vo´,i x1 = 5, x2 = 19, ta xac´ d¯.inh du¯,o.,c C1 = 3, C2 = −2 va nhu `,vây sô .´ hang tô .,ng quat c ´,ua day l ˜ a` xn = 3n+1 − 2n+1. Trong tru,o`,ng ho.,p nghiêm.t1, t2 la nh ` u˜,ng sô´ phu´,c., ngh˜ıa la` t1 = ρ(cos α + i sin α), t2 = ρ(cos α − i sin α), theo công thu´,c Moivre ta co´ tn1 = ρn(cos nα + i sin nα), tn2 = ρn(cos nα − i sin nα) va nghi ` êm tô .,ng quat ( ´ 3.26) tr,o,thanh ` xn = P1ρncos nα + P2ρnsin nα, (3.28) ,o,dây ¯ P1 va` P2 la h``ang sô ˘ ´ bâ´t ky. Ðê `,xac´ d¯.inh h`ang ˘ P1 va` P2 trong (3.28) khi cho hai gia tr ´ .i dâ¯`u x1 va` x2, ta co´ P1 = C1 + C2 =(t1 + t2)x1 − x2 t1t2, P2 = i(C1 − C2) = i(t1 + t2)x2 − (t21 + t22)x1 t1t2(t1 − t2), ho .ac l ˘ a` P1 =2ρcos α.x1 −1ρ2.x2, P2 =cotgα ρ2x2 −cos 2α ρ sin α.x1. (3.29) 2) Tru,o`,ng ho.,p t1 = t2: Nhu,trong tru,o`,ng ho.,p tru,o´,c chung ta ´ suy ra tu`,(3.24) va ( ` 3.25) vo´,i t1 = t2 xn − t1xn−1 = tn−2 1(x2 − t1x1). (3.30) 78 Chu,o,ng 3. T`ım công thu´,c tô,ng quat´ Ðê,xac´ d¯.inh du¯,o.,c xn câ`n t`ım môt phu .,o,ng tr`ınh nu˜,a cho xn va` xn−1. Tu`,phu,o,ng tr`ınh xn − 2t1xn−1 + t21xn−2 = 0 co thê ´,viê´t du,o´,i dang . (n − 2)xn − 2(n − 2)t1xn−1 + (n − 2)t21.xn−2 = 0 ho .ac l ˘ a` (n − 2)xn − (n − 1)t1xn−1 = t1[(n − 3)xn−1 − (n − 2)t1xn−2]. (3.31) Sau khi thê´ n tu,o,ng u´,ng b`ang ˘ n − 1, n − 2, . . . , 4, 3 vao ( ` 3.31) ta nhân. du¯,o.,c (n − 3)xn−1 − (n − 2)t1xn−2 = t1[(n − 4)xn−2 − (n − 3)t1xn−3], (n − 4)xn−2 − (n − 3)t1xn−3 = t1[(n − 5)xn−3 − (n − 4)t1xn−4], . . . . . . 2x4 − 3t1x3 = t1(x3 − 2t1x2), x3 − 2t1x2 = −t21x1.(3.32) Lâ`n lu,o.,t thê´ cac vê ´ ´tu,o,ng u´,ng c,ua (3.32) vao ( ` 3.31) ta nhân. du¯,o.,c (n − 2)xn − (n − 1)t1xn−1 = −tn−1 1.x1. (3.33) Tu`,(3.30) va ( ` 3.33) ta t`ım du¯,o.,c (n − 1)xn − (n − 2)xn = (n − 1)tn−2 1(x2 − t1x1) + tn−1 1x1, ho .ac l ˘ a` ,o,dây ¯ xn = (C1 + C2.n)tn1, (3.34) t21, C2 =x2 − t1x1 C1 =2t1x1 − x2 t21. Ban. d¯oc c . o thê ´,kiê,m tra dê d˜ ang ( ` 3.34) la kê ` ´t qu,a c,ua (3.26) khi ta cho t2 = t1. J 3.3. Phu,o,ng tr`ınh truy hô`i tuyê´n t´ınh 79 . T`ım sô´ hang tô .,ng qu ´at c,ua d ˜ay x ´ac d¯.inh theo công Vı d´ u 3.16. thu´,c sau: x1 = 10, x2 = −12, xn + 4xn−2 = 0. Lo`,i gi,ai. Tu`,phu,o,ng tr`ınh t2 + 4 = 0 ta t´ınh du¯,o.,c t1 = 2i = 2(cos π2 + i sin π2), t2 = −2i = 2(cos π2 − i sin π2) hay la` ρ = 2, α = π2. Khi d¯o nghi ´ êm c .,ua phu,o,ng tr`ınh truy hô`i la` xn = (P1 cosnπ2+ P2 sin nπ2)2n. Tu`,(3.39) suy ra P1 = 3, P2 = 5, do d¯o sô ´ ´ hang tô .,ng quat ph ´,ai t`ım la` xn = (3 cos nπ2+ 5 sin nπ2)2n. ho .ac l ˘ a` xn =   3.2n vo´,i n = 4k 5.2n vo´,i n = 4k + 1 −3.2n vo´,i n = 4k + 2 −5.2n vo´,i n = 4k + 3 . Bây gio`,ta quan tâm câu h ,oi t`ım nghiêm riêng c .,ua Vı d´ u 3.17. phu,o,ng tr`ınh truy hô`i không thuâ`n nhâ´t bâc hai v . o´,i hê sô .´ h `˘ang sô´ a0xn+2 + a1xn+1 + a2xn = bn (a0 6= 0, a2 6= 0). (3.35) Lo`,i gi,ai. Ta cung x ˜ et nghi ´ êm.t1, t2 c,ua phu,o,ng tr`ınh a0t2 + a1t + a2 = 0. 1) Tru,o`,ng ho.,p t1 6= t2: Khi d¯o theo phâ ´ `n trên tn1va` tn2la nh ` u˜,ng nghiêm riêng c .,ua phu,o,ng tr`ınh thuâ`n nhâ´t (3.17) va c ` o nghi ´ êm. theo công thu´,c (3.26). Nghiêm riêng c .,ua phu,o,ng tr`ınh (3.35) ta se t ˜ `ım theo phu,o,ng phap biê ´ ´n dô¯,i h`ang sô ˘ ´ nhu,sau: Ta ph,ai t`ım nghiêm riêng . ξn co´