Phương pháp quy nạp toán học - Nguyễn Hữu Điển - TOANMATH.com

(1)

(2)

(3)

NGUY ÊN H ˜ U ˜ ,

U ÐIÊ ,

N

PHU , O ,

NG PH ´ AP

QUY N .AP TO ´AN H .OC

(T ´ai b,

an lâ`n th ´u,hai)

NH `A XUÂT B´ ,

AN GI ´AO D .UC

(4)

c

Ebook 1.0 cua cuôń s ách nguyên gôć t ùban in, c ác b .an tham kh,

ao, cho ý kiêń sai sót v à lò,i khuyên t ái b,

an. M .oi liên h.ê T ´ac gi,

a: Nguy˜ên H˜u,u Ðiê, n Ði .ên tho .ai: 0989061951 Email: huudien@vnu.edu.vn Web: http://nhdien.wordpress.com

Ch.iu tr ´ach nhi.êm xuâ´t b, an:

Gi ám ¯dôć Ngô Trâ`n ái Tô,

ng biên t .âp V ˜u Du,o,

ng Th .uy Biên t .âp n.ôi dung:

Ngô Long H .âu Biên t .âp t ´ai b,

an:

Tru,o,ng Công Th `anh Tr`ınh b `ay b`ıa:

T .a Tr.ong Tr´ı Chê´ b,

an:

Ngu˜ên H˜u,u Ðiê, n

51

GD−0005/796-00 M ˜a sô´: 8H663M0

(5)

L ` O ,

I N ´ OI Ð ` ÂU

M .ôt phu,o,

ng ph áp râ´t m .anh trong toán h.oc d ùng nghiên c ú,u v à ch ú,ng minh c ác gi,

a thuyê´t l à nguyên l ý quy n .ap toán h.oc. Có vô sô´ c ác v´ı d .u trong các môn h.oc ,

o,chu,o,ng tr`ınh phô,

thông d ùng nguyên l ý n ày ¯dê,

di˜ên gi,

ai v `a mô t, a. Nhu,

ng ¯dê, hiê,

u thâ´u ¯d ´ao vê`

k ˜y thu .ât áp d .ung trong h.oc t .âp, sáng t .ao râ´t ´ıt sách ¯du, .o,

c b `an t´o, i.

T ài li .êu nu,ó,c ngoài c˜ung ¯dã có m.ôt sô´ sách nói riêng vê` vâń ¯dê`

n `ay, theo tôi c ˜ung chu,

a ¯dâ`y ¯d,

u v à râ´t nhiêù ngu,ò,i khó tiê´p xúc

¯ du,

.o,c v´o,

i t ài li .êu này. Tôi m .anh d .an thu th .âp và kh,

ao s át nguyên l ý quy n .ap toán h.oc theo m.oi kh´ıa c .anh và minh h.oa b`˘ang các b ài t .âp trong chu,

o,

ng tr`ınh phô,

thông. Ðây l à lo .ai sách cung câ´p v à th,

ao lu .ân nh˜u,ng phu,o,

ng ph ´ap h .oc t .âp v`a gi,

ai b ài t .âp cho các b .an yêu th´ıch toán h.oc, các thâ`y cô giáo, sinh viên các tru,ò,ng su, ph .am và các b .an ,

o,l´o,

p h .oc sinh gi,

oi l àm t ài li .êu tiê´p t .uc phát triê,

n. Chu, o,

ng ¯dâù xem xét c ác kh´ıa c .anh c,

ua nguyên l ´y quy n .ap to ´an h .oc. Do khuôn khô,

c,

ua cuôń s ách ch úng tôi ¯d ã không ch ú,ng minh c .˘an k˜e s .u,

tu, o,

ng ¯du, o,

ng c,

ua nguyên l ý quy n .ap toán h.oc và tiên ¯dê` th ú,

t .u,

; s .u,tu,o,

ng ¯du,o,ng c,

ua c ác d .ang nguyên lý quy n .ap to án h .oc..v.v. Chu,

o,

ng hai kh,

ao s át c ác kh´ıa c .anh k˜y thu .ât c, ua nguyên l ý n ày. T ù,chu,o,ng ba m˜ôi chu,o,ng d ùng kh,

ao s át c ác b ài t .âp vê` m.ôt lo .ai ch,

u ¯dê` ch,

ı ´ap d .ung phu,o,

ng ph ´ap quy n .ap to´an h .oc nhu,

: Sô´ h .oc, D˜ay sô´, H`ınh h.oc, Ða th ´u, c, Tô,

h .o,

p, Liên phân sô´ ...

T `ai li .êu ch ´ung tôi tham kh,

ao có h .an và ch´˘ac còn nhiêù bài t .âp hay chu,a nói tó,

i, ho .˘ac c´o sai s´ot trong thê,

hi .ên ý tu,,o,ng mong b .an ¯d .oc cho ý kiêń s,

u, a ¯dô,

i v `a bô,

sung. M .oi liên h.ê g, u,

i vê` ¯d.ia ch, ı:

Nh `a xuâ´t b,

an Gi ´ao d .uc, 81 Trâ`n Hu,

ng Ð .ao, H`a N.ôi.

H à N .ôi, tháng 5 n˘am 2000 T ác gi,

a

3

(6)

CHU , O ,

NG 1

NGUYÊN L ´ Y QUY N .AP TO ´AN H .OC

1.1.Suy di˜ên v à quy n .ap. . . . 4 1.2.Nguyên lý quy n .ap toán h .oc. . . . 6 1.3.Giai ¯do .an quy n .ap và gi,

a thiê´t quy n .ap. . . . 8 1.4.Hai bu,o´,

c c,

ua nguyên lý quy n .ap toán h .oc. . . . 14 1.5.Khi n ào dùng phu,o,ng ph áp quy n .ap. . . . 19 1.6.B ài t .âp. . . . 22

1.1. Suy di˜ ên v ` a quy n .ap

Ðê,

minh h .oa hai kh´ai ni.êm râ´t hay g .˘ap trong th .u,

c tê´ l à suy di˜ên v à quy n .ap, ta lâý câu ca dao Vi.êt Nam ai c ˜ung biê´t:

¨Sô´ cô có m.e có cha M.e cô ¯d àn b à cha cô ¯d àn ông

Sô´ cô có v .o,có chô`ng Sinh con ¯dâù lòng ch,

˘ang g ´ai th`ı trai.¨

Ðây l `a câu ¯do ´an c,

ua ông thâ`y bói, ta ¯d ã biê´t thâ`y bói ch, ı do án mò thôi, nhu¯ ,ng ông thâ`y bói trong câu ca dao n ày râ´t khôn l à d ùng m .ôt kh,

˘ang ¯d.inh luôn luôn ¯d úngäi c ˜ung có m.e, có cha¨. T ù,

dó d `¯ u áp d .ung cho ngu,ò,i ¯dêń bói c .u thê,

n ào c ˜ung ¯d úng luôn, ngh˜ıa l à kh,

˘ang ¯d.inh riêng c ˜ung ¯d úng. Bu,ó,c suy lu.ân t ù,kh,

˘ang d.inh chung ´ap d .ung cho nh˜u¯ ,ng kh,

˘ang ¯d.inh riêng bi.êt g.oi làphép suy di ˜ên. Phép suy di˜ên ,

o,

v´ı d .u trên là luôn ¯d úng vó,

i hai câu ¯dâ`u,

(7)

1.1. Suy di ˜ên v `a quy n .ap 5 nhu,ng c´o thê,

sai, o,

hai câu sau. Trong to án h .oc râ´t hay d ùng phép suy di˜ên, ch,

˘ang h .an, nê´u hai g´oc trong c,

ua m .ôt tam giác ¯d ã cho l à 30⁰ v à 70⁰, th`ı ¯diêù kh,

˘ang ¯d.inh sau ¯d úng: ¨ Góc th ú,ba c, ua tam gi ác ¯d ã cho l à 80⁰¨. M .ênh ¯dê` chung ,

o,dây l `a: ¨Tô¯ ,

ng c ´ac g´oc trong c,

ua m .ôt tam gi´ac l`a180⁰¨.

Bây gi`o,

ta ¯d .oc l .ai chuy.ên cu,`o,i dân gian Vi.êt nam:

¨Bô´n ông thâ`y b´oi r,

u nhau ¯di xem voi. T´o,

i ch˜ô voi ¯d ´u,

ng, bôń thâ`y bói chen v ào, sò,

t .ân tay xem con voi nó thê´ nào. Vê` tó, i ch .o,, bôń thâ`y h .op nhau b`ınh phâ,

m.

Thâ`y s`o,

¯ du,

.o,

c c ái vòi voi nói:

- Tu,,o,

ng voi l .a l´˘am, t´e ra ch,

ı giô´ng con ¯d,

ıa c .u,c ló,n. Tôi sò,v ào nó uôń cong ngu,ò,i l.ai.

Thâ`y ôm ph,

ai c ´ai chân, v .ôi c˜ai:

- Voi ch,

ı h .êt nhu,

c ái c .ôt nhà thôi. Tôi ôm vào vù,

a tay c ´ai c .ôt c ´ai.

Thâ`y n ´˘am ph,

ai c ´ai tai voi, chê:

- C ´ac b ´ac ch,

ı n´oi m`o. Con voi th .ât ra t .u, a nhu,

c ´ai qu .at to tu,´o,ng.

Thâ`y t ´um ph,

ai c ´ai ¯duôi voi, cu,`o,i khâ, y:

- Ba b ´ac n´oi sai c,

a. Tôi ¯d ã t úm nó trong tay, th`ı ¯d úng l à m .ôt c ái chô,

i xê, d .ai.¯

Không ai ch.iu ai, bôń thâ`y to tiêńg cãi nhau ô`n ào m.ôt góc ch .o,... ¨

M˜ôi ông thâ`y bói ¯dêù d ùng 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 t´o,

i ph ´at biê, u kh,

˘ang ¯d.inh chung ¯du, .o,

c g .oi l`aph´ep quy

(8)

6 Chuong 1. Nguyên l ´y quy n .ap to´an h.oc n .ap. Kh,

˘ang ¯d.inh chung , o,

dây l à ¨con v .ât ¯¯ dó l à con voi¨. Nhu, v .ây 4 ông thâ`y bói ¯dêù ph át biê,

u kh,

˘ang ¯d.inh chung sai. Ch´˘ac có m.ôt ông n ào ¯dó s áng m ´˘at th`ı s˜e ¯d úng. Ta thâý r `˘ang phu,o,ng ph áp quy n .ap có thê,

¯ du,

a ¯dê´n kê´t qu,

a nh .ân ¯d.inh sai. Phu, o,

ng ph ´ap quy n .ap râ´t hay ¯du,

.o,

c d `ung trong nghiên c ´u,

u khoa h .oc, nhâ´t l`a to´an h.oc.

Nhu,

v .ây ch ´ung ta ph, ai hiê,

u phu, o,

ng ph áp quy n .ap thê´ nào ¯dây v à áp d .ung thê´ nào ¯dê,

nh .ân ¯du, .o,

c m .ênh ¯dê` kh,

˘ang ¯d.inh ¯d ´ung.

1.2. Nguyên l´ y quy n .ap to´an h .oc

Ðê,

ng ´˘an g .on ta k´y hi.êu m.ôt kh,

˘ang ¯d.inh to´an h.oc l`a P(x), , o,

¯

dây x l à m .ôt biêń sô´. Ngu,ò,i ta thu,ò,ng ¯du,a vê` d.ang m.ênh ¯dê` ¨ Vó,

i m .oi x (trong m .ôt t .âp Sn ào ¯dó),P(x)¨. Trong cuôń s ách n ày ta lâýx =nl à nh˜u,

ng sô´ t .u,

nhiên¹,Sl `a t .âp c´ac sô´ t .u,

nhiên (bao gô`m to `an b .ô c´ac sô´ nguyên du,

o,

ng). Ta s, u,

d .ung m.ôt t´ınh châ´t râ´t quan tr .ong c,

ua t .âp sô´ t .u,

nhiên, thu,`o,ng ngu,`o,i ta công nh.ân nhu, m .ôt tiên ¯dê` ( ¯du,

.o,

c g .oi l`a tiên ¯dê` th ´u, t .u,).

Tiên ¯dê`:Trong m ˜ôi t .âp h.o,p kh ´ac r ˜ông c, ua nh ˜u,

ng sô´ t .u,nhiên c´o m .ôt phâ`n t ,

u,nh, o nhâ´t.

Cho m˜ôi sô´ t .u,nhiên n u´,ng v´o,

i m .ôt kh,

˘ang ¯d.inhP(n). V´ı d .u, vó,i 1 ta cho tu,o,ng ú,ng vó,i kh,

˘ang ¯d.inhP(₁): ¨sô´ 1 l à m .ôt sô´ l, e¨, sô´ 2 cho tu,o,ng t ú,ng vó,i P(2): ¨ sô´ 2 l à m .ôt sô´ ch˜˘an¨; ... B`˘ang phu,

o,ng ph ´ap nhu,

v .ây ch ´ung ta t .ao ra d˜ay kh,

˘ang ¯d.inh riêng P(1),P(2), . . . ,P(n), . . .. Nguyên l ´y quy n .ap to´an h.oc cho ta m.ôt phu,

o,

ng ph ´ap kiê,

m tra kh,

˘ang ¯d.inhP(n)d ´¯ung ho .˘ac sai v´o,

i m .oin.

Nguyên l ´y quy n .ap to´an h.oc ¯du, .o,

c thê,

hi .ên qua ¯d.inh l´ı sau:

1Trong s ách n ày khi nói ¯dêń sô´ t .u,nhiên, ta hiê,

u ¯dó l à sô´ t .u,nhiên kh ác sô´

0.

(9)

1.2. Nguyên l ý quy n .ap toán h.oc 7 Ð.inh l ý 1.1. Chon₀l à m .ôt sô´ nguyên du,o,ng v àP(n)l à m.ênh ¯dê`

c´o ngh˜ıa v ´o,

i m .oi sô´ t .u,nhiênn≥ n₀. Nêú A)P(n₀)l à ¯d úng v à

B) Nêú P(k) d ´¯ung, th`ı P(k+1) c ˜ung ¯d úng v ó,i m ˜ôi sô´ t .u,nhiên k ≥n₀,

khi ¯d´o m.ênh ¯dê`P(n)d ´¯ung v ´o,

i m .oi sô´ t .u,nhiênn≥ n₀. Ch ´u,ng minh.Ta s˜e ch ´u,ng minh b `˘ang ph,

an ch ´u,ng. Gi, a s,

u,ngu, .o,c l .ai, m.ênh ¯dê` kh,

˘ang ¯d.inhP(n)trong Ð.inh l´ı 1.1 không ¯d úng vó,i m .ôt sô´ t .u,nhiênn≥ n₀ n ào ¯dó. Ngh˜ıa l à tô`n t .ai m.ôt sô´ t .u,nhiên m ≥ n₀, m à P(m) không ¯d úng. Ta lâý sô´ t .u,nhiên m nh,

o nhâ´t m à P(m) không ¯d úng ( ¯diêù n ày th .u,

c hi .ên ¯du, .o,

c do tiên ¯dê` th ´u, t .u,

). Theo ¯diê`u ki .ên A), ta c´o bâ´t ¯d,

˘ang th ´u,

c m> n₀, t `u,

¯

d´o suy ra m−1 ≥ n₀. T `u,

bâ´t ¯d,

˘ang th ´u, c v `u,

a l .âp và cách ch.on sô´ t .u, nhiên msuy ra P(m−1)l à ¯d úng, nhu,

ng n´o không k´eo theo ¯du, .o,

cP(m)

¯

d úng cho sô´ tiê´p theom= (m−1) +1. Ðiêù n ày tr ái vó, i gi,

a thiê´t

B). J

Xuâ´t ph ´at t `u,

m .ênh ¯dê` kh,

˘ang ¯d.inh vó,i c ác tru,ò,ng h.o,p riêng, ch,

˘ang h .an nhu,

c ´ac sô´ 1, 2, ho .˘ac 3 c´o thê, nâ,

y sinh gi,

a thiê´t m .ênh dê` ¯¯ d ´ung v´o,

i m .oi sô´ t .u,

nhiên. Sau ¯d´o ¯dê, ch ´u,

ng minh gi,

a thiê´t c, ua ta v `u,

a xây d .u,

ng ngu,ò,i ta lý lu.ân theo nguyên l ý quy n .ap to án h .oc. Phu,

o,

ng ph ´ap ch ´u,

ng minh nhu,

v .ây g.oi l`aphu, o,

ng ph áp quy n .ap to án h.oc. Theo ¯d.inh l´ı trên phu,o,ng ph áp n ày gô`m hai bu,ó,c, th ú,nhâ´t ta kiê,

m tra kh,

˘ang ¯d.inh m.ôt t´ınh châ´t vó,i n = n0, g .oi l àBu,ó,c co,s ,o,; sau ¯dó ch ú,ng minh r `˘ang nêú vó,i m˜ôik ≥ n0, P(k) tho,

a m ãn t´ınh châ´t ¯d ã biê´t, th`ı suy raP(_k+₁)c ˜ung có t´ınh châ´t âý, g .oi làBu,ó,c quy n .ap. Kê´t lu .ân làP(n)có t´ınh châ´t ¯d ã cho vó,i m .oi n ≥ n₀. C ách ch ú,

ng minh theo quy n .ap toán h.oc là tránh

(10)

8 Chuong 1. Nguyên l ´y quy n .ap to´an h.oc cho ta ph,

ai kiê,

m tra vô h .an bu,´o,c c´ac kh,

˘ang ¯d.inh c,

ua m .ênh ¯dê`.

1.3. Giai ¯ do .an quy n .ap v`a gi ,

a thiê´t quy n .ap

Phu, o,

ng ph ´ap quy n .ap to´an h.oc râ´t hay ¯du, .o,

c ´ap d .ung trong nghiên c ´u,

u v à t`ım tòi trong to án h .oc, các ngành khoa h.oc khác.

Ðê, hiê,

u c ´ach ´ap d .ung phu, o,

ng ph ´ap quy n .ap cho ¯dâ`y ¯d,

u, ta xem x´et m .ôt sô´ v´ı d .u sau ¯dây nhu,

m .ôt phép¨suy lu .ân có lý¨ m à G.

Polya ¯d ˜a ¯dê` c .âp.

V´ı d .u 1.1. Cho tru,´o,c m.ôt sô´ t.u,nhiênn. H ˜ay t`ım tô,

ng c ´ac sô´ t .u, nhiên1, 2, . . . ,n.

L `o,i gi ,

ai.Ta k ´y hi .êuSnl `a tô, ng ph,

ai t`ım, ngh˜ıa l `a

Sn =1+2+· · ·+n. (1.1) Ta hy v .ong l`a t`ım ra công th ´u,

c ng ´˘an g .on ¯dê,

t´ınh tô,

ng trên, công th ´u,

c ¯dó gi úp ta t´ınh nhanh, g .on ho,n l à ph, ai th .u,

c hi .ên lâ`n lu, .o,t c ´ac ph´ep c .ông trong tô,

ng. Ta c ˜ung biê´t ¯dây l à câ´p sô´ c .ông, nêú b .an ¯d .oc ¯d ã biê´t vê` câ´p sô´ n ày, th`ı ta có thê,

c´o ngay công th ´u,c t´ınh tô,

ng. Nhu,ng ,

o,dây ta muôń minh h .oa quá tr`ınh áp d .ung nguyên¯ l ý quy n .ap toán 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 S_n t `u, d¯,

˘ang th ´u,c (1.1) v´o,

i m .ôt v`ai sô´ t .u,nhiên liên tiê´p, ch,

˘ang h .an b´˘at ¯dâ`u t`u,1. Nh˜u,ng kê´t qu,

a t´ınh to án c ác tru,ò,ng h.o,p riêng ta xê´p v ào b,

ang

n 1 2 3 4 5 6

S_n 1 3 6 10 15 21 M .uc ¯d´ıch c,

ua ta l `a t`ım ¯du, .o,

c quy lu .ât chung (kh,

˘ang ¯d.inh chung), v´o,i b,

ang trên, m˜ôi sô´ t .u,nhiên ,

o,h `ang trên trong b,

ang cho tu,o,ng

(11)

1.3. Giai ¯do .an quy n .ap v`a gi,

a thiê´t quy n .ap 9

u´,ng v´o,i c ´ac sô´,

o,h `ang du,´o,i. T`ım ra quy lu.ât c

ua m .ôt bài toán ph .u, thu .ôc vào râ´t nhiêù yêú tô´: s .u,

khéo léo trong quan s át; s .u, nh .ay c,

am d .u,do ´an v `a kiê¯ ,

m tra c,

ua ta; t `u,

c ác kinh nghi .êm ¯d ã tr, ai qua trong t´ınh to án c ác b ài to án tu,

o, ng t .u,

, t `u, kh,

a n ˘ang liên h .ê b`ai to ´an tu,

o, ng t .u,

v´o,

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,,

h àng trên b `˘ang 2 lâ`n sô´ ¯dâù tiên tu,o,ng ú,ng ,

o,h `ang 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 .âygiai do .an quy n .ap¯ c,

ua ch úng ta ¯d ã th ành công: T`ım ra quy lu .ât vó,i c ác tru,ò,ng h.o,

p riêngn=1, 2, 3, 4, 5, 6.

Tiê´p t .uc m.ôt c´ach t .u,nhiên l `a m, o,

r .ông quy lu .ât trên cho b, ang sô´ v´o,

i c ´ac sô´ t .u,

nhiên bâ´t k `y. Ta ¯du,a ra gi,

a thiê´t th´ıch h .o,p v´o,i quy lu .ât v`u,

a t`ım ¯du, .o,

c. Ð .˘at

1+2+· · ·+n= ⁿ(n+1)

2 . (1.2)

M .ôt gi,

a thiê´t ta ¯d ˜a l `am nhu,

v .ây ¯du, .o,

c g .oi l`a gi,

a thiê´t quy n .ap. Nhu,ng câu h,

oi ¯d .˘at ra l`a ¯d,

˘ang th ´u,

c (1.2) có ¯d úng vó,

i m .oi n = 1, 2, . . . hay không? Rõ r àng nêú (1.2) ¯d úng vó,

i m .oi sô´ t .u, nhiên th`ı b `˘ang c ách thaynb `˘angn+1ch úng ta s˜e có ¯d,

˘ang th ´u, c 1+2+· · ·+n+ (n+1) = (n+1)(n+2)

2 . (1.3)

Tr ´ai l .ai, gi,

a thiê´t (1.2) l à ¯d úng vó,

i m .oi n = 1, 2, . . ., nê´u 1) n´o

¯

d úng vó,i n = 1 v à 2) nó ¯d úng vó,i m˜ôi sô´k suy ra c ˜ung ¯d úng vó,i c,

a k+1. Ðiêù n ày không có c ách n ào kh ác l à ph,

ai áp d .ung nguyên l ý quy n .ap toán h.oc. Ngh˜ıa là ch úng ta ph,

ai kiê, m tra nh˜u,

ng ¯diê`u ki .ên A) v`a B) c,

ua ¯d.inh l´ı 1.1.

Bu,ó,c co, s ,o,: vó,in = ₁, công th ú,

c (1.2) ¯d úng (nó còn ¯d úng cho c, a n=2, 3, 4, 5, 6).

(12)

10 Chuong 1. Nguyên l ý quy n .ap toán h.oc Bu,ó,c quy n .ap: Bây giò,ch úng ta ch ú,ng minh công th ú,

c (1.2) ¯d ´ung cho c,

a ¯diê`u ki .ên B). V´o,

i m .uc ¯d´ıch ¯d´o ta gi,

a thiê´t công th ´u,c (1.2)

¯

d ´ung v´o,

i m .ôt sôń = k ≥ 1n ào ¯dó v à s˜e ch ú,

ng minh ¯d,

˘ang th ú,c (1.2) ¯d úng vó,in=k+1. Ta biêń ¯dô,

i 1+2+· · ·+k+ (k+1) = ^k(k+₁)

2 + (k+1) = (k+₁)(k+₂)

2 .

Kê´t qu,

a l à (1.2) ¯d úng vó,in=k+1. Theo nguyên l ý quy n .ap toán h .oc công th ú,

c (1.2) ¯d ´ung v´o,

i m .oin=1, 2, . . . J

T´om l .ai, qua v´ı d .u ¯do, n gi,

an trên ta thâý c ác bu,ó,c quá tr`ınh t`ım tòi v à ch ú,

ng minh nguyên l ´y quy n .ap to´an h.oc.

V´ı d .u 1.2. T´ınh tô, ng S_n= ¹

a(a+1)+ ¹

(a+1)(a+2)+· · ·+ ¹

(a+ (n−1))(a+n) v ´o,

ia6=0,−1,−2, . . . ;n=1, 2, . . . L `o,i gi,

ai.Vi .êc tru,´o,c tiên ta ph,

ai t`ım ra công th ´u,c gi,

a thiê´t quy n .ap cho tô,

ng trên. Ta t´ınh S₁= ¹

a(_a+₁)^, S₂=S₁+ ¹

(a+₁)(a+₂) = ¹

a(a+₁)+ ¹

(a+₁)(a+₂) = ² a(a+₂)^, S₃=S₂+ ¹

(a+₂)(a+₃) = ³ a(a+₃)^, S₄=S₃+ ¹

(a+₃)(a+₄) = ⁴ a(a+₄)^. Ch ´ung ta c´o thê,

du¯ ,a ra gi,

a thiê´t r `˘ang S_n = ⁿ

a(a+n)^. ^(1.4)

(13)

Bu,´o,c co,s ,o,: Nhu,

d ˜a kiê¯ ,

m tra , o,trên.

Bu,´o,c quy n .ap: Gi,

a thiê´t (1.4) ¯d ´ung v´o, i sô´ t .u,

nhiên n=kn `ao ¯d´o.

Khi ¯d´o

S_k+₁= S_k+ ¹

(a+k)(a+k+₁) = ^k

a(a+k)+ ¹

(a+k)(a+k+₁)

= ¹

a+k.k²+ (a+1)k+a a(a+k+1) ^.

Nhu,ngk²+ (a+1)k+a= (a+k)(k+1), suy ra S_k+1= ¹

a+k.(a+k)(k+1)

a(a+k+1) = ^k+1 a(a+k+1)^. T `u,

kê´t qu, a v `u,

a t´ınh v `a bu,´o,c co, s,o, suy ra gi,

a thiê´t quy n .ap (1.4) l à ¯d úng vó,

i m .oi sô´ t .u,

nhiênn≥1. J

V´ı d .u 1.3. T´ınh tô, ng S_n= ²

1−a² + ²

1+a² + ⁴

1+a⁴ +· · ·+ ²

n

1+a²ⁿ v ´o,

in=1, 2, . . . ;|a| 6=1.

L `o,i gi,

ai. Ta phân t´ıch: Sô´ lu, .o,

ng sô´ h .ang c, ua tô,

ng l `a n+1;

tr `u,

sô´ h .ang ¯dâù tiên, còn l .ai các sô´ h .ang khác ¯dêù có d .ang 2^k

1+a²^k (k=1, 2, . . . ,n). Ta t´ınh S₁ = ²

1−a² + ²

1+a² = ⁴ 1−a⁴, S₂ =S₁+ ⁴

1+a⁴ = ⁴

1−a⁴ + ⁴

1+a⁴ = ⁸ 1−a⁸, S₃ =S₂+ ⁸

1+a⁸ = ⁸

1−a⁸ + ⁸

1+a⁸ = ¹⁶ 1−a¹⁶. Do4 = ₂²_{, 8} = ₂³ v à16 = ₂⁴ t ù,c ác biê,

u th ´u,c c,

ua S₁,S₂ v `aS₃ c´o thê,

¯

du,a ra gi, a thiê´t:

(14)

12 Chuong 1. Nguyên l ´y quy n .ap to´an h.oc

Sn = ²

n+1

1−a²ⁿ⁺¹, (n =1, 2, . . .). (1.5) Bu,ó,c co, s ,o,: Vó,i n = 1, công th ú,

c (1.5) ¯d ´ung nhu,d ˜a kiê¯ ,

m tra , o, trên.

Bu,´o,c quy n .ap: Gi, a s,

u,

(1.5) ¯d ´ung v´o,

i sô´ t .u,nhiên n = k n `ao ¯d´o.

Khi ¯d´o

S_k+1 = ²

1−a² + ²

1+a² + ⁴

1+a⁴ +· · ·+ ²

k

1+a²^k + ²

k+1

1+a²^k⁺¹

= ²

k+1

1−a²^k⁺¹ + ²

k+1

1+a²^k⁺¹ = ²

k+2

1−a²^k⁺². Ð,

˘ang th ´u,

c (1.5) c ˜ung ¯d ´ung v´o,

i n= k+1. Nhu,

v .ây, t`u,

nguyên l ´y quy n .ap to´an h.oc ¯d,

˘ang th ´u,

c (1.5) ¯d ´ung v´o,

i m .oin≥1. J

V´ı d .u 1.4. T´ınh tô, ng c,

uansô´ l,

e t .u,nhiên ¯dâ`u tiên.

L `o,i gi ,

ai.Ta k ´y hi .êu tô, ng ph,

ai t`ım l `aSn: Sn=1+3+5+· · ·+ (2n−1). Ðê,

xây d .u,ng gi,

a thiê´t quy n .ap to´an h.oc ta t´ınh tô, ng,

o,

m .ôt sô´ gi´a tr.i ¯du,

.o,

c li .êt kê trong b,

ang sau:

n 1 2 3 4 5 6

Sn 1 4 9 16 25 36 Bây gi`o,

ph .u thu.ôc v`ao s .u,quan s ´at c,

ua ta v `a kinh nghi .êm trên kê´t qu,

a riêng ¯dê, d .u,

do ´an m .ênh ¯¯ dê` tô,

ng qu át chung. D˜ê thâý c ác sô´ ,

o,

h àngS_n dêù l à sô´ ch´ınh phu¯ , o,

ng: S₁ = 1²,S₂ = 2²,S₃ = 3²,S₄ = 4², S₅ = 5²,S₆ = 6². Nhu,

v .ây ta c´o thê,

¯ du,

a ra gi, a thiê´t chung l `a

S_n=n². (1.6)

(15)

Ta s˜e ch ´u,

ng minh (1.6) ¯d ´ung v´o,

i m .oi sô´ t .u,nhiênn.

Bu,´o,c co,s ,o,: V´o,

i n= 1, tô, ng ch,

ı c´o m .ôt sô´ h .angSn= 1; biê, u th ´u,

c n²=1v´o,in=1, nhu,

v .ây (1.6) ¯d ´ung.

u,

(1.6) ¯d ´ung v´o,

i n = k, (S_k = k²). ta s˜e ch ´u,

ng minh (1.6) ¯d ´ung v´o,

i n = k+1:S_k+1 = (k+1)². Th .ât v .ây, S_k+1= S_k+ (2k+1) =k²+ (2k+1) = (k+1)². J

Ta xét thêm m .ôt v´ı d .u n˜u,a theo c ách l àm c,

ua G. Polya.

V´ı d .u 1.5. T´ınh tô,

ng b`ınh phu,o,ng c,

uansô´ t .u,nhiên ¯dâ`u tiên.

L `o,i gi ,

ai.Ta tiêń h ành t`ım công th ú,c cho gi,

a thiê´t quy n .ap. Ð .˘at T_n =1²+2²+· · ·+n².

Ta h ˜ay t`ım m .ôt sô´ gi´a tr.i c, ua tô,

ng khi chon=1, 2, . . . , 6.

n 1 2 3 4 5 6

Tn 1 5 14 30 55 91 Nh`ın v `ao b,

ang trên ta kh´o c´o thê,

t`ım ra quy lu .ât chung choT_n. V´o,

i thông tin ´ıt , oi nhu,

v .ây không cho kê´t qu,

a g`ı, nhu, ng v´o,

i kinh nghi .êm ta c´o thê,

liên h .ê v´o,

i c ´ac v´ı d .u ¯d ˜a gi,

ai v à so s ánh nh˜u,ng d ãy sô´ trong v´ı d .u 1.1 và ch`ıa khoá 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

S_n 1 1

5 3

14 6

30 10

55 15

91 21 Dòng cuôí c ùng trong b,

ang ta c´o thê,

viê´t l .ai: 1 1 = ³

3, 5 3, 14

6 = ⁷

3, 30

10 = ⁹ 3, 55

15 = ¹¹ 3 , 91

21 = ¹³

3 . Bây gi`o,

ta c´o thê,

¯ du,

a ra gi, a thiê´t

(16)

14 Chuong 1. Nguyên l ´y quy n .ap to´an h.oc r `˘ang T_n

Sn

= ²ⁿ+₁

3 . T `u,kê´t qu,

a v´ı d .u 1.1 ta c´o Tn= ²ⁿ+1

3 .n(n+1)

2 ho .˘ac l`a

1²+2²+· · ·+n² = ⁿ(n+1)(2n+1)

6 . (1.7)

Ta ch ´u,

ng minh b `˘ang quy n .ap toán h.oc cho công th ú,c (1.7) d ´¯ung vó,

i m .oi sô´ t .u,nhiênn. 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.

u,

(1.7) ¯d ´ung v´o,

i sô´ t .u,nhiênn= kn ào ¯dó. Ta s˜e ch ú,

ng minh r `˘ang nó c ˜ung ¯d úng vó,in=k+1, ngh˜ıa l à 1²+2²+· · ·+k²+ (k+1)² = (k+1)(k+2)(2k+3)

6 .

Th .ât v .ây,

T_k+1= T_k+ (k+1)² = ^k(k+1)(2k+1)

6 + (k+1)²

= (k+1)^k(2k+1) +6(k+1)

6 = (k+1)(k+2)(2k+3)

6 .

Nhu,

v .ây bài toán ¯d ã gi,

ai xong. J

1.4. Hai bu , o ´ ,

c c ,

ua nguyên l´ y quy n .ap to´an h .oc

Nhu,

ta ¯d ã biê´t nguyên l ý quy n .ap toán h.oc gô`m hai phâ`n, vi .êc kiê,

m tra c,

a hai câ`n ¯du, .o,

c tôn tr .ong 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 s˜e nh .ân

¯ du,

.o,c nh˜u,

ng kê´t lu .ân sai. Thông qua c´ac v´ı d .u sau ¯dê,

minh h .oa v `a hiê,

u ¯diê`u n `ay ho,n.

V´ı d .u 1.6. Ch ´u,ng minh r `˘ang m .oi sô´ t .u,nhiên ¯dê`u b `˘ang sô´ t .u, nhiên liê`n sau.

(17)

1.4. Hai bu,´o,c c,

ua nguyên l ý quy n .ap toán h.oc 15 L ò,

i gi,

ai.Ta ch ´u,

ng minh theo phu, o,

ng ph ´ap 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ô´ t .u,

nhiên n = k n ào ¯dó, ngh˜ıa l à

k= (k+1). (1.8)

Ch ´ung 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 n .ap (1.8) c .ông hai vê´ ¯d,

˘ang th ´u,c v´o,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`ı nó ¯d úng vó,

in = k+1, do ¯dó m .ênh ¯dê` b ài to án ¯d úng vó,

i m .oin. J

H .ê qu, a c,

ua b ài to án n ày l à tâ´t c,

a c ´ac sô´ t .u,

nhiên ¯dêù b `˘ang nhau. Ðiêù n ày th .ât vô lý, v .ây cách ch ú,

ng minh sai , o,

¯

dâu? D˜ê d àng thâý ngay trong ch ú,

ng minh áp d .ung nguyên lý quy n .ap to án h .oc nhu,

ng b,

o qua kiê,

m tra tru,`o,ng h.o,

pn=1.

Ðiêù ki .ên A) và B) trong Ð.inh l´ı 1.1 có m.ôt ý ngh˜ıa ¯d .˘ac bi.êt:

Ðiê`u ki .ên A) t .ao ra co,s, o,

dê¯ , th .u,

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ô¯ h .an trên co,

s, o,

diê`u ki .ên A); nguyên t´˘ac ¯¯ di t `u,

tru,`o,ng h.o,

p riêng n `ay sang tru,`o,ng h.o,

p riêng kh ´ac; t `u,

kdê´n¯ k+1.

, O,

v´ı d .u .1.6 ta không kiê,

m tra ¯diê`u ki .ên A) c,

ua Ð.inh l´ı 1.1, nên không t .ao ra co,s,

o,dê¯ , th .u,

c hi.ên quy n .ap, v`ı v .ây không c´o ngh˜ıa g`ı khi th .u,

c hi .ên kiê,

m tra ¯diê`u ki .ên B) c,

ua Ð.inh l´ı 1.1, th .u,

c châ´t l `a không c´o g`ı ¯dê, m,

o,

r .ông c,

a. Ta x´et thêm v´ı d .u:

V´ı d .u 1.7. Ch ´u,ng minh r `˘ang v ´o,

i m .oi sô´ t .u,nhiênnbâ´t ¯d ,

˘ang th ´u,c sau ¯d ´ung

2ⁿ >2n+1. (1.10)

(18)

16 Chuong 1. Nguyên l ý quy n .ap toán h.oc L ò,

i gi, ai.Gi,

a thiê´t bâ´t ¯d,

˘ang th ´u,

c (1.10) ¯d ´ung v´o,

in = k, v´o, ikl `a m .ôt sô´ t .u,

nhiên n ào ¯dó, ngh˜ıa l à ta có

2^k >2k+1. (1.11)

Ta s˜e ch ´u,

ng minh bâ´t ¯d,

˘ang th ´u,

c (1.10) ¯d úng vó,in=k+1 2^k⁺¹ >2(k+1) +1. (1.12) Th .ât v .ây,2^k l à m .ôt sô´ không nh,

o ho,n2v´o,

i m .oi sô´ t .u,nhiên kh ´ac không. Ta c .ông vê´ tr´ai c,

ua (1.11) v´o,i2^kv `a c .ông vê´ ph, ai c,

ua (1.11) v´o,i2. Ta nh .ân ¯du,

.o,c

2^k+2^k >2k+1+2.

Ngh˜ıa l `a

2^k⁺¹ >2(k+1) +1.

B ài to án ¯d ã gi,

ai xong. J

Tâ´t nhiên v´ı d .u n`ay c ˜ung m´˘ac sai lâ`m nhu,

v´ı d .u tru,´o,c không kiê,

m traBu,´o,c co,s ,o,. Th .u,c châ´t c,

ua c ách ch ú,ng minh trên l à bâ´t

¯ d,

˘ang th ´u,

c (1.10) ¯d úng vó,in=k+1, nêú nó ¯d úng vó,in=k. Ðiêù n ày không suy ra bâ´t ¯d,

˘ang th ´u,

c ¯d ´ung v´o,

i ´ıt nhâ´t m .ôt giá tr.i c, ua n, ch ú,chu,a nói tó,i vó,

i m .oi sô´ t .u,nhiênn.

Nhu,ng ta c´o thê, th,

u,v´o,in=1ho .˘acn=2bâ´t ¯d,

˘ang th ´u,c (1.10) sai. V´o,in≥3bâ´t ¯d,

˘ang th ´u,

c (1.10) ¯d ´ung. Gi ´a tr.i sô´ t .u,nhiên nh, o nhâ´tn=₃bâ´t ¯d,

˘ang th ´u,

c (1.10) ¯d úng ( ¯diêù ki .ên A) vó,in₀=₃v à l .˘ap l .ai cách ch ú,ng minh ,

o,trên t `u,gi,

a thiê´t (1.10) ¯d úng vó,in=k suy ra nó ¯d úng vó,in=k+1( ¯diêù ki .ên B). V`ı v .ây theo nguyên lý quy n .ap toán h.oc ta có kê´t lu .ân: Bâ´t ¯d,

˘ang th ´u,

c (1.10) ¯d ´ung v´o,i m .oi sô´ t .u,

nhiên n ≥ 3(ch ´u,

không ph, ai v´o,

i m .oi sô´ t .u,

nhiên nhu,

¯

dê` b `ai ra).

Trong vi .êc ´ap d .ung phu,o,

ng ph áp quy n .ap toán h.oc mà ch, ı ch ú,

ng minh ¯diê`u ki .ên A) c,

ua Ð.inh l´ı 1.1 th`ı m´o,i ch, ı ¯du,

a ra ¯du, .o,c

(19)

1.4. Hai bu,´o,c c,

ua nguyên l ´y quy n .ap to´an h.oc 17 co,s,

o, dê¯ ,

quy n .ap ch ´u,

không c´o nguyên t ´˘ac n `ao ¯dê, m,

o,

r .ông co,s, o,

¯

d´o (nhu,d.inh l´ı l´o¯ ,

n Fermat). Ta x´et m .ôt sô´ v´ı d .u:

V´ı d .u 1.8. Ch ´u,ng minh r `˘ang nh ˜u,

ng gi ´a tr.i c,

ua h àm sô´ f(n) = n²−n+41v ó,i n=0, 1, . . .l à nh ˜u,ng sô´ nguyên tô´.

L `o,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 c´o thê,

t´ınh to ´an tiê´p t .uc gi´a tr.i c,

ua f(n)cho tó,in=₄₀, tâ´t c, a gi á tr.i này ¯dêù l à sô´ nguyên tô´. Nhu,ng vó,in = 41ta có f(41) = 41²−41+41 = 41². Kê´t qu,

a f(41)không ph,

ai l `a sô´ nguyên tô´, nên kê´t lu .ân c,

ua b ài to án l à không ¯d úng. J Nhu,

v .ây ta thâ´y m.ôt m.ênh ¯dê` c´o thê,

d ´¯ung v´o,i 40 tru,`o,ng h.o,p riêng, nhu,

ng không ¯d ´ung v´o,

i m .oi tru,`o,ng h.o,p n´oi chung.

V´ı d .u 1.9. Ða th ´u,

c xⁿ−1, v ´o,i n l `a sô´ t .u,

nhiên du,

o,ng. Ða th ú, c n ày liên quan ¯dêń b ài to án h`ınh h .oc chia ¯du,ò,ng tròn ran phâ`n b `˘ang nhau, nên ¯da th ú,c n ày ¯du,

.o,

c râ´t nhiê`u l˜ınh v .u,

c to án h .oc nghiên c ú,u v à ¯dê` c .âp ¯dêń. Ð .˘ac bi.êt c ác nh à to án h.oc quan tâm t ó,i vâń ¯dê` phân t´ıch ¯da th ú,c n ày ra c ác th ù,a sô´ l à c ác ¯da th ú,c v ó,

i h.ê sô´ nguyên±1, li.êu ¯diêù ¯dó còn ¯d úng v ó,

i m .oin?

L `o,i gi,

ai. B `˘ang c ´ach khai triê,

n c ác tru,ò,ng h.o,p riêng, c ác nh à to án h .oc nh .ân thâý r`˘ang tâ´t c,

a c ác h .ê sô´ trong các thù,

a sô´ ¯du, .o,c khai triê,

n có gi á tr.i tuy.êt ¯dôí không qu á 1. Ch,

˘ang h .an, x−1= x−1,

x²−1= (x−1)(x+1), x³−1= (x−1)(x²+x+1), x⁴−1= (x−1)(x+1)(x²+1),

(20)

18 Chuong 1. Nguyên l ´y quy n .ap to´an h.oc x⁵−₁= (x−₁)(x⁴+x³+x²+x+₁)_,

x⁶−1= (x−1)(x+1)(x²+x+1)(x²−x+1). Nh˜u,ng cô´ g ´˘ang ch ´u,

ng minh ¯diê`u nghi ng`o,

d ´¯ung v´o,

i m .oin c, ua c ác nh à to án h .oc không thành công. M.ôt thò,i gian sau, nh à to án h .oc Nga V. Ivanov (n˘am 1941) ch,

ı ra r `˘ang v´o,

i ¯da th ú,c xⁿ−1, diêù nghi ngò¯ ,ch,

ı ¯d úng vó,i c ác tru,ò,ng h.o,p nh,

o ho,n 105. Nhu,ng v´o,in=₁₀₅, m .ôt th`u,a sô´ c,

uax¹⁰⁵−₁l `a

x⁴⁸+x⁴⁷+x⁴⁶−x⁴³−x⁴²−2x⁴¹−x⁴⁰−x³⁹+x³⁶+ +x³⁵+x³⁴+x³³+x³²+x³¹−x²⁸−x²⁶−x²⁴−x²²−x²⁰+x¹⁷ +x¹⁶+x¹⁵+x¹⁴+x¹³+x¹²−x⁹−x⁸−2x⁷−x⁶+x⁵+x²+x+1.

Th `u,

a sô´ n `ay không c´o t´ınh châ´t c,

ua c ´ac ¯da th ´u,

c m à c ác nh à to án

h .oc muô´n. J

V´ı d .u 1.10. Ch ´u,ng minh r `˘ang v ´o,

i m .oi sô´n m.ênh ¯dê` sau ¯dây

¯

d úng: ¨Nêúav àbl à nh ˜u,

ng sô´ t .u,nhiên du,o,ng, m `amax(a,b) =n, th`ıa= b¨.

L `o, i gi ,

ai. Bu,ó,c co, s ,o,: Vó,i m˜ôin k ý hi .êu A_n l à m .ênh ¯dê` c, ua b ài to án ¯d ã cho. Rõ r àng A₁l à ¯d úng, v`ı nêúmax(a,b) =1, th`ı hai sô´

a v `abph,

ai tr ùng nhau v à b `˘ang 1 (doav àbl à sô´ t .u,

nhiên).

u,

A_kl à ¯d úng. Nêúav àbl à nh˜u,

ng sô´ t .u,nhiên sao chomax(a,b) = k+1. Ta xét hai sôá₁ = a−1v àb₁ = b−1, khi ¯dó max(a₁,b₁) = k, t ù,

¯

d´o suy ra a₁ = b₁, v`ı gi,

a thiê´t A_k l `a

¯

d úng, do ¯dóa =b, ngh˜ıa l àA_k+1c ˜ung ¯d úng. Theo nguyên l ý quy n .ap toán h.ocA_n d ´¯ung vó,

i m .oi sô´ t .u,

nhiênn.

H .ê qu,

a: Cho a v `a b l `a hai sô´ t .u,

nhiên bâ´t k `y. Ta t´ınh ¯du, .o,c max(a,b) =k, m `akl `a m .ôt sô´ t .u,

nhiên. Theo v´ı d .u trên A_nd ´¯ung

(21)

1.5. Khi n `ao d `ung phu,o,

ng ph ´ap quy n .ap 19

v´o,

i m .oin, th`ı nó c ˜ung ¯d úng vó,i A_k. T ù,

d´o suy ra¯ a =b. Ngh˜ıa l `a tâ´t c,

a c ´ac sô´ t .u,

nhiên ¯dê`u b `˘ang nhau. Th .ât vô l´y!

Trong v´ı d .u trên c´ach ch ´u,ng minh sai , o,

dâu? Ta xem l .ai toàn¯ b .ô cách ch ú,

ng minh v à nguyên l ý quy n .ap toán h.oc. Bu,ó,c quy n .aptrong ch ú,ng minh không nh ´˘ac tó,

i ¯diê`uk ≥ 1, khi bu,´o,c quy n .ap chuyê,

n tiê´p t `u,

A_k sang A_k₊₁. Th .u,c tê´ trong t´ınh to ´an ch ´u,ng minh không ¯d,

am b,

aok ≥₁. J

1.5. Khi n ` ao d` ung phu , o ,

ng ph ´ ap quy n .ap

Phu, o,

ng ph áp quy n .ap toán h.oc râ´t có tác d .ung trong nghiên c ú,

u, d .u,

¯

do ´an kê´t qu,

a v `a ch ´u,

ng minh kiê,

m nghi .êm kê´t qu, a.

Nhu,

ng nhiê`u khi ch´ınh phu, o,

ng ph áp quy n .ap toán h.oc làm vi.êc ch ú,

ng minh d ài dòng, biêń ¯dô, i ph ú,

c t .ap gây râ´t nhiêù khó kh˘an trong ch ú,ng minh. Nhiêù b ài to án gi,

ai b `˘ang phu,o,ng ph ´ap quy n .ap c´o thê,

gi,

ai b `˘ang m .ôt phu,o,ng ph áp kh ác. Ch´ınh G. Polya có nói: ¨Nhiêù b ài to án ch ú,

ng minh b `˘ang quy n .ap toán h.oc có thê, ch ú,

ng minh b `˘ang c ách kh ác, c ách kh ác ¯dó n `˘am trong ch´ınh c ách ch ú,

ng minh quy n .ap to´an h.oc khi ta phân t´ıch k˜y n.ôi dung ch ´u,ng minh¨.

Trong to án h .oc ngu,ò,i ta hay dùng ký hi.êu ∑ l à m .ôt tô, ng.

Thu,`o,ng tô,

ng có d .ang Aα+Aα+1+· · ·+A_β (αv à β l à nh˜u,ng sô´

nguyên)v `a ¯du, .o,

c viê´t

∑

β k=α

A_k ( ¯d .oc l`a tô, ng c,

ua A_k,k ch .ay t`u, α dê´n¯ β). Nhu,

v .ây

Aα+A_α+1+· · ·+A_β =

∑

β k=α

A_k k g .oi l`ach,

ı sô´ c, ua tô,

ng, còn αv à β l à gi á tr.i ¯dâù v à gi á tr.i cuôí c,

ua ch,

ı sô´k. M˜ôi sô´ h .ang bên tr´ai c, ua ¯d,

˘ang th ´u,

c l à ¯d úng vó, i m .ôt

(22)

20 Chuong 1. Nguyên l ý quy n .ap toán h.oc gi á tr.ik(k=_α,α+_{1, . . . ,}β). V´ı d .u

∑

n k=1

k² =1²+2²+· · ·+n²,(n≥1),

n+1 k=−

∑

1

10^2k =10⁻²+10⁰+10²+· · ·+10²⁽ⁿ⁺¹⁾,(n≥ −2). Ph´ep lâ´y tô,

ng c´o nh˜u,

ng t´ınh châ´t sau: Nêú choa v àbl à nh˜u, ng sô´, ta có c ác ¯d,

˘ang th ´u,c

∑

β k=α

aA_k = a

∑

β k=α

A_k,

∑

β k=α

(aA_k+bB_k) =a

∑

β k=α

A_k+b

∑

β k=α

B_k. K ´y hi .êu tô,

ng không ph .u thu.ôc v`ao ch,

ı sô´, nhu,

ng ph .u thu.ôc vào gi á tr.i ban ¯dâù v à gi á tr.i cuôí c ùng

∑

β k=α

A_k =

∑

β i=α

A_i =

β−α i

∑

=0

A_α+i

Tr, o,

l .ai nh˜u,

ng v´ı d .u , o,

phâ`n tru,ó,c, trong quá tr`ınh t´ınh toán quy n .ap t´ınh tô,

ng

1²+2²+· · ·+n² =

∑

n k=₁

k²

B `˘ang c ´ach ´ap d .ung t´ınh châ´t c,

ua k ´y hi .êu tô,

ng v à công th ú,c tô, ng c ác sô´ t .u,

nhiên

∑

n k=1

k= ⁿ(n+1)

2 ,(n≥1).Th .ât v .ây, d˜ê thâ´y

∑

n k=0

(k+1)³−

∑

n k=0

k³ = (n+1)³.

(23)

1.5. Khi n `ao d `ung phu,o,

ng ph ´ap quy n .ap 21

Vê´ tr ´ai c, ua ¯d,

˘ang th ´u,c trên c´o thê, biê,

n ¯dô, i

∑

n k=0

(k+₁)³−

∑

n k=0

k³=

∑

n k=0

[(k+₁)³−k³] =

∑

n k=0

(3k²+3k+₁)

=3

∑

n k=1

k²+3

∑

n k=1

k+

∑

n k=0

1.

Nhu,

v .ây t`u, c ´ac ¯d,

˘ang th ´u,

c trên r ´ut ra (n+1)³ =3

∑

n k=1

k²+3n(n+1)

2 + (n+1), Chuyê,

n vê´ v à t´ınh to án ta có

∑

n k=1

k²= ¹

3[(n+1)³−3n(n+1)

2 −(n+1)] = ¹

6n(n+1)(2n+1). T´ınh tô,

ng sau ¯dây (b `ai.1.2)

∑

n k=1

1

(a+k−1)(a+k)^, ⁿ=1, 2, ..;a6=0,−1,−2, . . . Ta s,

u,

d .ung ¯d,

˘ang th ´u, c sau

1

(a+k−₁)(a+k) = ¹

a+k−₁ − ¹ a+k. Ð .˘atb_k = ¹

a+k, nhu, v .ây

∑

n k=1

1

(a+k−1)(a+k) =

∑

n k=1

(b_k₋₁−b_k) =b₀−b_n

= ¹ a− ¹

a+n = ⁿ a(a+n)^. Cuô´i c `ung ta nh .ân ¯du,

.o,c

∑

n k=₁

1

(a+k−1)(a+k) = ⁿ a(a+n)^. Vâ´n ¯dê` c,

ua phâ`n n `ay ta c`on ¯dê` c .âp tiê´p ,

o,Chu,o,ng 3.

(24)

22 Chuong 1. Nguyên l ´y quy n .ap to´an h.oc

1.6. B ` ai t .âp

..

.1.11. T´ınh tô,

ng b `˘ang c ´ach xây d .u,ng gi,

a thiê´t v à ch ú,ng minh b `˘ang quy n .ap toán h.oc các tô,

ng sau:

a)S_n=1²−2²+· · ·+ (−1)ⁿ⁻¹n²; b)S_n=₁³+₂³+· · ·+n³;

c)S_n=1.1!+2.2!+· · ·+n.n!.

. .

.1.12. Ch ´u,

ng minh ´ıt nhâ´t b `˘ang hai c ách c ác công th ú, c sau:

a)1²+3²+· · ·+ (2n−1)² = ¹

3n(2n−1)(2n+1), n =1, 2, . . . b)1.2.3+2.3.4+· · ·+n(n+1)(n+2) = ¹

4n(n+1)(n+2)(n+ 3),n=1, 2, . . .

c) 1 1.2 + ¹

2.3+· · ·+ ¹

n(n+1) = ⁿ

n+1,n=1, 2, . . . .

.

.1.13. Chon>1l `a sô´ t .u,

nhiên. Ta ¯d .˘atx₀= ¹

n;x_k = ¹

n−k(x₀+ x₁+· · ·+x_k₋₁),k = 1, 2, . . . ,n−1. H ˜ay t´ınh tô,

ngx₀+x₁+· · ·+ x_n−1.

(25)

CHU , O ,

NG 2

K˜ Y THU .ÂT D`UNG PHU , O ,

NG PH ´ AP QUY N .AP TO ´AN H .OC

2.1.M .ôt sô´ d .ang nguyên lý quy n .ap toán h .oc. . . . 23 2.2.M .ênh ¯dê` trong nguyên lý quy n .ap toán h .oc. . . . 31 2.3.Bu,

´ o,

c quy n .ap ¯du, .o,

c xây d .u,

ng trênP(k). . . . 36 2.4.Bu,o´,

c quy n .ap ¯du, .o,

c xây d .u,

ng trênP(k+1). . . . 40 2.5.Quy n .ap toán h .oc và phép truy hôì. . . . 43 2.6.Quy n .ap toán h .oc và tô,

ng qu át ho á. . . . 51 2.7.B ài t .âp. . . . 55

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 l´ı 1.1 cho ta co, s,

o, m,

o,

r .ông b´˘at ¯dâ`u t `u,

gi ´a tr.in₀. Ðiê`u ki .ên B) c,

ua Ð.inh l´ı 1.1 cho ta m.ênh ¯dê` kh,

˘ang d.inh¯ P(n) d ´¯ung vó,i n₀+1,n₀+2, . . .. Th .u,c tê´ nhiêù khi trong bu,ó,c quy n .ap ph,

ai ¯d`oi h,

oi hai gi ´a tr.i n = k−1 v `a n = k c, ua m .ênh ¯dê`, ¯dê,

suy ra m .ênh ¯dê` ¯d úng vó,i n = k+1. Trong tru,ò,ng h .o,p n àybu,ó,c co,s ,o,ph,

ai kiê,

m tra không nh˜u,ng ch,

ı vó,in0, m à c, a vó,i n₀+₁. Tô,

ng qu ´at ho,n ta c´o thê,

ph ´at biê,

u l .ai ¯d.inh l´ı , o,phâ`n tru,´o,c nhu, sau:

Ð.inh l ´y 2.1. Chopl `a sô´ nguyên du,o,

ng v à d ãy c ác m.ênh ¯dê`

P(1),P(2), . . . ,P(n), . . .

(26)

24 Chuong 2. K ˜y thu .ât d ùng phuong ph áp quy n .ap toán h.oc nêú

A)P(1),P(2), . . . ,P(p)l `a nh ˜u,

ng m.ênh ¯dê` ¯d ´ung v `a

B) V ó,i m ˜ôi sô´ t .u,nhiênk ≥ pc ác 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 úng,

th`ı m.ênh ¯dê`P(n)d ´¯ung v ´o,

i m .oi sô´ nguyên du,o,ngn. Ch ´u,

ng minh ¯d.inh l´ı này hoàn toàn l .˘ap l .ai nhu,

d.inh l´ı 1.1.¯ Sau ¯dây ta x´et m .ôt sô´ v´ı d .u s,

u,

d .ung d .ang ¯d.inh l´ı 2.1.

V´ı d .u 2.1. Chov₀ = 2,v₁ = 3 v à v ó,i m ˜ôi sô´ t .u,nhiênk có ¯d ,

˘ang th ú,c sau:v_k+1=3v_k−2v_k−1. Ch ú,ng minh r `˘angvn=2ⁿ+1. L ò,

i gi ,

ai.Bu,´o,c co,s ,o,: V´o,

in=0v àn=1kê´t lu .ân bài toán ¯d úng, do ¯diêù ki .ên bài ¯d ã cho.

u,r `˘ang v_k₋₁ = 2^k⁻¹+1;v_k = 2^k+1, khi

¯ d´o

v_k+₁=3(2^k+1)−2(2^k⁻¹+1) =2^k⁺¹+1.

Theo nguyên l ý quy n .ap toán h.oc d .ang ¯d.inh l´ı 2.1, suy ra vn = 2ⁿ+1d ´¯ung vó,

i m .oi sô´ t .u,nhiênn. J

V´ı d .u 2.2. Cho x1 v `ax2 l `a nghi.êm c,

ua phu,o,ng tr`ınh x²−27x+ 14= ₀;nl `a m .ôt sô´ t .u,nhiên bâ´t k`y. Ch ´u,ng minh r `˘ang tô,

ngS_n= xⁿ₁+xⁿ₂ không chia hê´t cho 715.

L `o,i gi ,

ai.Theo công th ´u,c Vietx₁+x₂ =27;x₁x₂ =14.

Bu,ó,c co,s ,o,: C ác sô´S₁ = 27;S₂ = (x₁+x₂)²−2x₁x₂ = 701v à S₃ = (x₁+x₂)[(x₁+x₂)²−3x₁x₂] = 27·687dêù không chia hê´t¯ cho 715. Suy ra m .ênh ¯dê` c,

ua b ài to án ¯d úng vó,

in=1, 2, 3.

u,

m .ênh ¯dê` ¯d ´ung v´o,i n = k−2,n = k−

(27)

2.1. M .ôt sô´ d .ang nguyên l´y quy n .ap to´an h.oc 25 1,n=k, ta t´ınh

x^k₁⁺¹+x^k₂⁺¹= (x₁+x₂)(x^k₁+x^k₂)−x₁x₂(x^k₁⁻¹+x₂^k⁻¹)

= (x₁+x₂)[(x₁+x₂)(x^k₁⁻¹+x₂^k⁻¹)−

−x₁x₂(x₁^k⁻²−x^k₂⁻²)]−x₁x₂(x^k₁⁻¹+x^k₂⁻¹)

=715(x^k₁⁻¹+x₂^k⁻¹)−378(x₁^k⁻²+x^k₂⁻²).

Do ¯dóx^k₁⁺¹+x^k₂⁺¹không chia hê´t cho 715, v`ı 378 không chia hê´t cho 715, nói c ách kh ác m .ênh ¯dê` ¯d úng vó,in=k+1. J V´ı d .u 2.3. Ch ú,ng minh v ó,

i m .oi sô´ th .u,cx>0v `a m .oi sô´ t .u,nhiên nbâ´t ¯d,

˘ang th ´u,c sau ¯d ´ung xⁿ+xⁿ⁻²+xⁿ⁻⁴+· · ·+ ¹

xⁿ⁻⁴ + ¹ xⁿ⁻² + ¹

xⁿ ≥n+1. (2.1) L `o,

i gi ,

ai.1a) V´o,

in=1bâ´t ¯d,

˘ang th ´u,

c (2.1) c´o d .ang x+ ¹

x ≥2. (2.2)

Bâ´t ¯d,

˘ang th ´u,c (2.2) suy ra t `u,

bâ´t ¯d,

˘ang th ´u,c hiê,

n nhiên: (_x− 1)² ≥₀.

1b) V´o,in=2bâ´t ¯d,

˘ang th ´u,c (2.1) c´o d .ang x²+1+ ¹

x² ≥3. (2.3)

Bâ´t ¯d,

˘ang th ´u,

c (2.2) ¯d ´ung v´o,

i m .oix>0, v .ây nó c ˜ung ¯d úng vó,ix², x²+ ¹

x² ≥2.

C .ông hai vê´ c,

ua bâ´t ¯d,

˘ang th ú,c sau c ùng vó,

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,

in = k, m `a kl `a m .ôt sô´

t .u,

nhiên n `ao ¯d´o

x^k+x^k⁻²+x^k⁻⁴+· · ·+ ¹

x^k⁻⁴ + ¹ x^k⁻² + ¹

x^k ≥k+1, (2.4)

(28)

26 Chuong 2. K ˜y thu .ât d ùng phuong ph áp quy n .ap toán h.oc ta s˜e ch ú,

ng minh khi ¯d´o bâ´t ¯d,

˘ang th ´u,

c (2.1) ¯d úng vó,in= k+₂, hay l à

x^k⁺²+x^k+x^k⁻²+· · ·+ ¹ x^k⁻² + ¹

x^k + ¹

x^k⁺² ≥k+3. (2.5) Th .ât v .ây, trong (2.2) thê´xb,

o,ix^k⁺², ta nh .ân ¯du, .o,c x^k⁺²+ ¹

x^k⁺² ≥2. (2.6)

C .ông vê´ tu, o,

ng ´u, ng c,

ua c ´ac bâ´t ¯d,

˘ang th ´u,

c (2.4) v `a (2.6), ta s˜e c´o (2.5).

Tóm l .ai: Bu,ó,c co, s ,o,: Trong 1a) v à 1b) ta ¯d ã ch ú,

ng minh bâ´t

¯ d,

˘ang th ´u,

c ¯d ´ung chon=1v `an=2.

Bu,ó,c quy n .ap: Trong 2) ta ¯d ã ch ú,ng minh t ù,gi,

a thiê´t ¯d ´ung c,

ua (2.1) vó,in=ksuy ra nó ¯d úng vó,in=k+₂. Kê´t qu, a l à + T ù,

1a) v `a 2) cho ta kh,

˘ang ¯d.inh l`a bâ´t ¯d,

˘ang th ´u,

c (2.1) ¯d ´ung v´o,

i m .oi sô´ l, en. + T `u,

1b) v `a 2) cho ta kh,

˘ang ¯d.inh l`a bâ´t ¯d,

˘ang th ´u,

c (2.1) ¯d ´ung v´o,

i m .oi sô´ ch˜˘ann.

Nhu,

v .ây, bâ´t ¯d,

˘ang th ´u,

c (2.1) ¯d ´ung v´o,

i m .oi sô´ t .u,nhiênn. J V´ı d .u 2.4. Ch ´u,ng minh r `˘ang v ´o,

i m .oi sô´ t .u,nhiên n d¯ ,

˘ang th ´u,c sau ¯d ´ung:

a) 12

7 .2ⁿ

− 17

7 .2ⁿ⁻¹

=2ⁿ⁻¹; b)

17 7 .2ⁿ

− 12

7 .2ⁿ⁻²

=2ⁿ⁺¹, o,,dây¯ [a]l `a sô´ nguyên l ´o,n nhâ´t nh,

o ho,na. L `o,i gi,

ai.Bu,´o,c co,s ,o,: V´o,in = _{1, 2, 3}nh˜u, ng ¯d,

˘ang th ´u,

c trên ¯d ´ung b `˘ang c ´ach kiê,

m tra tr .u,c tiê´p.

(29)

2.1. M .ôt sô´ d .ang nguyên lý quy n .ap toán h.oc 27 Bu,ó,c quy n .ap: Gi,

a thiê´t r `˘ang hai ¯d,

˘ang th ´u,

c ¯d ´ung v´o,i ba sô´

t .u,nhiên liên tiê´pk,k+1,k+2. Ta s˜e ch ´u,

ng minh c ´ac ¯d,

˘ang th ú,c trên ¯d úng vó,in=k+3.

2a) T `u, 12

7 .2^k⁺³ = ¹²

7 (1+7)2^k =12.2^k+¹² 7 .2^k; 17

7 .2^k⁺² = ¹⁷

7 (1+7)2^k⁻¹=17.2^k⁻¹+¹⁷ 7 .2^k⁻¹, suy ra

12 7 .2^k⁺³

− 17

7 .2^k⁺²

=12.2^k−17.2^k⁻¹+ 12

7 2^k

− 17

7 2^k⁻¹

. Nhu,

ng v`ı a) ¯d ´ung v´o,in=k 12

7 .2^k⁺³

− 17

7 .2^k⁺²

=12.2^k−17.2^k⁻¹+2^k⁻¹ =2^k⁺². V .ây ¯d,

˘ang th ´u,

c a) ¯d ´ung v´o,in=k+3.

2b) T `u,

17

7 .2^k⁺³=17.2^k+¹⁷ 7 .2^k, 12

7 .2^k⁺¹=_12.2^k⁻²+ ¹² 7 .2^k⁻², suy ra

17 7 .2^k⁺³

− 12

7 .2^k⁺¹

=17.2^k−12.2^k⁻²+ 17

7 2^k

− 12

7 .2^k⁻²

. Nhu,ng v`ı b) v´o,in=k, ta c´o

17 7 .2^k⁺³

− 12

7 .2^k⁺¹

=_17.2^k−_12.2^k⁻²+₂^k⁺¹ =₂^k⁺⁴_. V .ây ¯d,

˘ang th ´u,

c b) ¯d ´ung v´o,in=k+3.

Theo nguyên l ý quy n .ap toán h.oc a), b) ¯d úng vó,

i m .oi sô´ t .u,nhiên

n. J

V´ı d .u 2.5. Ch ´u,ng minh r `˘ang un= ^α

n+1−βⁿ⁺¹

α−β , (2.7)

(30)

28 Chuong 2. K ˜y thu .ât d ùng phuong ph áp quy n .ap toán h.oc

nê´u u₁= ^α

2−β²

α−β ,u₂ = ^α

3−β³

α−β (α6=β) v à v ó,i m ˜ôi sô´ t .u,nhiênk>2có ¯d,

˘ang th ´u,c sau:

u_k = (α+β)u_k−1−αβu_k−2. L `o,i gi ,

ai.1) Vó,in=1v àn =2, (2.7) ¯d úng do ¯diêù ki .ên ¯d ã cho.

2) Gi, a s,

u,

¯ d,

˘ang th ´u,

c ¯d ´ung v´o,

in=k−1v `an=k−2 u_k−2 = ^α

k−1−β^k⁻¹

α−β ,u_k−1= ^α

k−β^k α−β khi ¯d´o

u_k = (α+β)^α

k−β^k

α−β −αβα^k⁻¹−β^k⁻¹ α−β = ^α

k+1−β^k⁺¹

α−β . J M .ôt d .ang nguyên l´y quy n .ap m .anh ho,

n nguyên l ´y quy n .ap ta ¯d ˜a biê´t c ˜ung râ´t ¯du,

.o,c hay d `ung.

Ð.inh l´ı 2.2Cho m .ôt d ˜ay m.ênh ¯dê`

P(1),P(2), . . . ,P(n), . . . Nê´u

A) P(1) l `a kh ,

˘ang ¯d.inh ¯d ´ung, v `a

B) v ´o,i m ˜ôi sô´ t .u, nhiên k ≥ 1, nh ˜u,ng kh ,

˘ang d.inh¯ P(1),P(2), . . . ,P(k)d ´¯ung suy ra kh,

˘ang ¯d.inhP(k+1)c ˜ung ¯d ´ung, th`ıP(n)d ´¯ung v ´o,i tâ´t c,

a sô´ t .u,nhiênn≥₁. D .ang này khác vó,

i c ác d .ang tru,ó,c là gi,

a thiê´t m .anh ho,n , o, bu,´o,c quy n .ap. Ta gi,

a thiê´t tâ´t c, a kh,

˘ang ¯d.inhP(1),P(2), . . . ,P(k) d ´¯ung suy ra P(k+1)c ˜ung ¯d úng. D˜ê d àng ch ú,ng minh hai c ách ph át biê,

u ¯d.inh l´ı 1.1. v`a ¯d.inh l´ı 2.2 tu,o,

ng ¯du,o,ng nhau. Nhu,ng trong th .u,

c tê´ áp d .ung vào bài toán c .u thê,

d `ung ¯d.inh l´ı 2.2 d˜ê gi, ai ho,n.

(31)

2.1. M .ôt sô´ d .ang nguyên