Các bài toán về dãy số nguyên

LaTeX in HTML

Bổ đề quan trọng

(Biểu thức cổ định của dãy tuyến tính cấp hai) Cho dãy số (an) xác định bởi an+2=aan+1an+bnN.

Khi đó, biểu thức an+12anan+2ban+1 luôn nhận giá trị không đổi.

Chứng minh.

Thật vậy, ta có biến đổi sau

xn+12xnxn+2bxn+1=xn+1(xn+1b)xn(axn+1xn+b)=xn+1(axnxn1)xn(axn+1xn+b)=xn2xn1xn+1bxn

Đẳng thức trên đúng với mọi n0 nên

xn+12xnxn+2bxn+1=x12x0x2bx1=const.

Bổ đề quan trọng

(Về sự tuần hoàn của các số dư) Cho dãy số nguyên {xn} xác định bởi công thức truy hồi xn+k=a1xn+k1++akxnk số hạng đầu tiên nguyên. Khi đó, với mọi số nguyên dương N, dãy số dư của xn khi chia cho N sẽ tuần hoàn kể từ một lúc nào đó. Tức là tồn tại n0 đủ lớn và T nguyên dương sao cho : xn+Txn(modN) với mọi nn0 Đặc biệt, nếu gcd(ak,N)=1 thì dãy số dư của xn khi chia cho N sẽ tuần hoàn. Tức là tồn tại T nguyên dương sao cho : xn+Txn(modN) với mọi n

Chứng minh.

Xét Nk+1 bộ số dư của (xi,xi+1,,xi+k1), với 1iNk+1 khi chia cho N. Ta có tối đa Nk bộ phân biệt như vậy, do đó theo nguyên lý Dirichlet thì có j,l phân biệt mà

xj+ixl+i(modN)i=1,k1.

Từ đây, ta suy ra

xj+ixl+i(modN)i.akxj1akxl1(modN),

Nếu gcd(ak,N)=1 thì xj1xl1(modN). Cứ tiếp tục như vậy, ta thu được T:=|jl| là chu kì cần tìm.

Bài toán (VMO 2019-2020)

Cho dãy số (an) xác định bởi a1=5,a2=13an+2=5an+16an với mọi n2.

a) Chứng minh rằng hai số hạng liên tiếp của dãy trên nguyên tố cùng nhau.

b) Chứng minh rằng nếu p là ước nguyên tố của a2k thì p1 chia hết cho 2k+1 với mọi số tự nhiên k.

Lời giải. a) Cách 1. Ta thấy (an) là dãy sai phân tuyến tính cấp hai có phương trình đặc trưng x2=5x6 với hai nghiệm là x1=2, x2=3 nên dễ dàng tìm được công thức tổng quát là

an=2n+3n,n.

Đến đây, giả sử có n1 để an, an+1 có ước nguyên tố chung là p. Rõ ràng gcd(p,6)=1. Ta có

{p2n+3np2n+1+3n+1{p32n+3n+1p22n+3n+1p2n,

vô lý vì gcd(p,6)=1.

Cách 2.an+25an+1(mod6)a1=5, a2=13 nên các số hạng của dãy luôn nguyên tố cùng nhau với 6. Giả sử tồn tại số nguyên tố p5 để pan, an+1 với nZ+. Suy ra

p5an6an1p6anpan1.

Từ đó thực hiện liên tiếp thao tác này thì suy ra pa1, a2, vô lý vì gcd(a1,a2)=1.

b) Bổ đề. Cho ab là các số nguyên tố cùng nhau và n là một số nguyên dương. Chứng minh rằng bất kỳ ước số dương lẻ nào của a2n+b2n đều đồng dư với 1 modulo 2n+1.

Chứng minh. Ta chỉ cần chứng minh rằng bất kỳ ước nguyên tố lẻ p nào của a2n+b2n đều đồng dư với 1 modulo 2n+1. Lưu ý rằng p không là ước của ab, vì gcd(a,b)=1. Gọi c là một số nguyên sao cho bc1(modp), khi đó p là ước của (ac)2n+1. Khi đó, k=ordp(ac) là ước của 2n+1, vì p là ước của (ac)2n+11, và không là ước của 2n, vì nếu không ta sẽ có p là ước của (ac)2n1p là ước của (ac)2n+1((ac)2n1)=2, điều này mâu thuẫn. Do đó, k=2n+1 và vì k là ước của p1, ta hoàn thành chứng minh.

Áp dụng bổ đề ta có ngay điều phải chứng minh.

Bài toán (VMO 2024-2025)

Với mỗi số nguyên n0, đặt un=(2+5)n+(25)n.

a) Chứng minh rằng un là số nguyên với mọi n0. Khi n thay đổi, số dư của un khi chia cho 24 lớn nhất bằng bao nhiêu?

b) Tìm tất cả các cặp số nguyên (a,b) với a,b nhỏ hơn 500 sao cho với mọi n lẻ ta có unanbn (mod 1111).

Lời giải. a) Từ giả thiết, ta dễ dàng chứng minh được un+2 = 4un+1 + un với mọi số tự nhiên n. Đến đây, bằng tính toán trực tiếp, ta dễ thấy dãy số dư khi chia các số hạng của dãy (un) cho 24 tuần hoàn theo chu kỳ 8: 2, 4, 18, 4, 10, 20, 18, 20. Như vậy, khi n thay đổi, số dư của un khi chia cho 24 lớn nhất là 20.

b) Xét một cặp số (a, b) thỏa mãn yêu cầu đề bài. Cho n = 1 và n = 3, ta được ab ≡ 4 (mod 1111) và a3b3 ≡ 76 (mod 1111). Từ đó

76 ≡ (ab)3 + 3ab(ab) ≡ 64 + 12ab (mod 1111).

Suy ra ab ≡ 1 (mod 1111), hay b(b + 4) ≡ 1 (mod 1111). Một cách tương đương, ta có

(b + 2)2 ≡ 5 (mod 1111).

Từ đó (b + 2)2 ≡ 5 (mod 11) và (b + 2)2 ≡ 5 (mod 101).

Vì (b + 2)2 ≡ 5 ≡ 16 (mod 11) nên b ≡ 2, 5 (mod 11).

Vì (b + 2)2 ≡ 5 ≡ 452 (mod 101) nên b ≡ 43, 54 (mod 101).

Kết hợp hai kết quả lại, ta suy ra b phải có một trong các dạng 1111k + 750, 1111k + 761, 1111k + 346 hoặc 1111k + 357 với k nguyên. Mà 1 ≤ b < 500 nên b ∈ {346, 357}. Kết hợp với ab (mod 1111) và 1 ≤ a < 500, ta được (a, b) ∈ {(350, 346), (361, 357)}.

Bây giờ, ta sẽ chứng minh hai cặp số (350, 346) và (361, 357) thỏa mãn yêu cầu đề bài. Dễ thấy với hai cặp số (a, b) như trên, ta có a2 ≡ 4a + 1 (mod 1111) và b2 ≡ −4b + 1 (mod 1111). (Ta có thể suy ra điều này từ ab ≡ 4 (mod 1111) và ab ≡ 1 (mod 1111) mà không phải tính toán gì.)

Bằng quy nạp, ta sẽ chứng minh với mọi số tự nhiên m, thì u2m+1a2m+1b2m+1 (mod 1111) với mọi số nguyên dương n lẻ và u2m = a2m + b2m (mod 1111). Với m = 0 và m = 1, khẳng định hiển nhiên đúng. Giả sử khẳng định đúng đến m với m nguyên dương. Sử dụng giả thiết quy nạp, ta có

u2m+2 = 4u2m+1 + u2m = 4(a2m+1b2m+1) + a2m + b2m
= (4a + 1)a2m + (1 − 4b)b2ma2m+2 + b2m+2 (mod 1111).

Từ đó

u2m+3 = 4u2m+2 + u2m+1 = 4(a2m+2 + b2m+2) + a2m+1b2m+1
= (4a+1)a2m+1 + (4b − 1)b2m+1a2m+3b2m+3 (mod 1111).

Như vậy, khẳng định cũng đúng với m + 1. Theo nguyên lý quy nạp, ta có khẳng định đúng với mọi số tự nhiên m.

Vậy, có hai cặp số thỏa mãn yêu cầu đề bài là (350, 346) và (361, 357).

Bài toán (Poland Finals 2002)

Cho k là một số nguyên dương cố định. Xét dãy (an) thỏa mãn :

{a1=k+1an+1=an2kan+k,n1

Chứng minh rằng với mọi số nguyên dương m khác n thì am,an nguyên tố cùng nhau.

Lời giải

Ta có :

an+1k=an(ank)=anan1(an1k)==anan1an2a1(a1k)=anan1a1

Không giảm tổng quát, ta giả sử m>n. Khi đó gọi p là một ước nguyên tố chung của gcd(am,an). Ta có :

amk=am1am2an1a1:ppk

Suy ra :

pank=an1(an1k)=an12kan1pan12pan1

Và lại suy ra :

pan1k=an22kan2pan22pan2

Cứ tiếp tục quá trình này ta suy ra pa1=k+1, suy ra p1. Mâu thuẫn.

Như vậy gcd(am,an) không có một ước nguyên tố nào, tức là gcd(am,an)=1. Điều phải chứng minh.

Bài toán

Xét dãy số (an) thỏa mãn:

{a0=0,a1=1,a2=2,a3=6an+4=2an+3+an+22an+1an

a) Chứng minh rằng với mọi số nguyên dương n thì nan.

b) Chứng minh rằng với k là số nguyên dương bất kỳ thì dãy a11,a22,a33,,ann chứa vô hạn các số hạng chia hết cho k.

Lời giải

a) Ta thấy

a11=1=F1,a22=1=F2,a33=2=F3,a44=3=F4,a55=5=F5,

Vậy ta có dự đoán:

an=nFn

Và chứng minh dự đoán này bằng quy nạp, giả sử điều đó đúng đến n+3. Xét với n+4:

an+4=2an+3+an+22an+1an=2(n+3)Fn+3+(n+2)Fn+22(n+1)Fn+1nFn=2(n+3)Fn+3+(n+2)Fn+22(n+1)Fn+1n(Fn+2Fn+1)=2(n+3)Fn+3+2Fn+2(n+2)Fn+1=2(n+3)Fn+3+2Fn+2(n+2)(Fn+3Fn+2)=(n+4)(Fn+3+Fn+2)=(n+4)Fn+4

Theo nguyên lí quy nạp ta có an=nFn với mọi n nguyên dương, suy ra nan với mọi n nguyên dương.

Điều phải chứng minh.

b) Nhận thấy dãy nói ở đề bài chính là dãy Fibonacci.

Từ đó theo định luật tuần hoàn của dãy số dư, ta có dãy số dư (rn) là dãy tuần hoàn. Trong đó rn là số dư khi chia Fn cho k với mỗi n. Hơn nữa r0=0F0=0, điều này đồng nghĩa tồn tại vô hạn số hạng của dãy Fibonacci là bội của k. Điều phải chứng minh.

Bài toán (China 1991)

Cho dãy số (un) nguyên thỏa mãn un+2=un+12un với mọi n tự nhiên. Giả sử u0=39,u1=45.

Chứng minh có vô hạn số hạng của dãy (un) chia hết cho 1986.

Lời giải

Gọi rn là số dư của un khi chia cho 1986 ứng với mỗi n. Ta chứng minh dãy (rn) tuần hoàn.

Xét dãy gồm các bộ số dư :

(r1,r2),(r2,r3),,(rm,rm+1),

Dãy trên có vô số số hạng mà số bộ khác nhau là hữu hạn vì ri{0,1,2,,1985}. Như vậy theo nguyên lí Dirichlet, sẽ tồn tại hai bộ trùng nhau. Tức là tồn tại k,m nguyên dương :

(rm+1,rm+2)=(rm+k+1,rm+k+2)

Từ đó :

rm=rm+12rm+2=rm+k+12rm+k+2=rm+k rm1=rm2rm+1=rm+k2rm+k+1=rm+k1 ... r1=r22r3=rk+22rk+3=rk+1

Tức là ta đã được :

(r1,r2)=(rk+1,rk+2)

Từ đó dựa vào công thức xác định dãy, ta thu được :

rn=rn+k,n=0,1,2,

Hơn nữa ta có u2=45239=1986 nên sẽ tồn tại vô hạn số hạng của dãy (un) chia hết cho 1986.

Bài toán (VMO 2022-2023)

Cho các số nguyên a,b,c,α,β và dãy số (un) xác định bởi

u1=α,u2=β,un+2=aun+1+bun+cvới mọi n1.

Chứng minh rằng tồn tại số nguyên dương n0 sao cho có duy nhất một trong hai khẳng định sau là đúng:

i) Có vô số số nguyên dương m để

un0un0+1un0+mchia hết cho 72023hoặc 172023,

ii) Có vô số số nguyên dương k để

un0un0+1un0+k1chia hết cho 2023.

Chứng minh

Giả sử trong dãy (un) tồn tại vô số số chia hết cho 7 hoặc tồn tại vô số số chia hết cho 17. Khi đó, u1u2un chia hết cho 72023 hoặc 172023 với mọi số nguyên dương n đủ lớn, và với mọi số dương n đủ lớn đó, u1u2un1 không chia hết cho 2023=7172. Do đó, lấy n0=1 thì khẳng định i) đúng và khẳng định ii) sai.

Bây giờ ta xét trường hợp dãy (un) không có hoặc có hữu hạn số chia hết cho 7 hoặc 17, tức là, un nguyên tố cùng nhau với 2023, với mọi n đủ lớn.

Gọi rn là số dư khi chia un cho 2023. Khi đó, tồn tại số nguyên dương n1 để (rn,2023)=1 với mọi nn1. Các cặp số (rn,rn+1) chỉ nhận hữu hạn khả năng, do đó, theo Nguyên lý Dirichlet, tồn tại các số nguyên dương n0,s (n0>n1) sao cho

(rn0,rn0+1)=(rn0+s,rn0+s+1).

Với n0 đã chọn, rõ ràng i) không đúng.

Với mọi số nguyên dương m, ta có rn0+m=rn0+r(m), với r(m) là số dư khi chia m cho s.

Lấy k=φ(2023)ts1 với t là số nguyên dương tùy ý, (φ là hàm Euler). Khi đó,

un0un0+1un0+krn0rn0+1rn0+φ(2023)ts1=(rn0)φ(2023)t(rn0+1)φ(2023)t(rn0+s1)φ(2023)t1(mod2023).

Bài toán

Cho dãy số nguyên (an) xác định bởi

a1=a,a2=b,an=6an1an2n3.

Hãy tìm tất cả các số nguyên dương p sao cho tồn tại cặp số (a,b) nguyên thỏa mãn p+4anan+1 là số chính phương với mọi n.

Lời giải.

Theo tính chất quen thuộc của dãy số nguyên, ta có

an+12anan+2=an2an1an+1==a22a3a1=b26ab+a2.

Từ đó, ta suy ra an+12anan+2=b26ab+a2, hay

an+12an(6an+1an)=b26ab+a2, (an+1an)2=4anan+1+b26ab+a2.

Giả sử rằng số p nguyên dương thỏa mãn yêu cầu bài toán, tức là

(an+1an)2+p(b26ab+a2)

là số chính phương với mọi n. Không khó để thấy rằng dãy các số (an+1an) là dãy số nguyên dương tăng, tiến đến vô cùng. Do vậy, để thỏa mãn yêu cầu bài toán thì ta phải có p=b26ab+a2.

Ở chiều ngược lại, với bất kì số p nguyên dương có dạng b26ab+a2, ta chọn a1=a,a2=b, và thu được

p+4anan+1=(an+1an)2nN.

Bài toán (VMO 2018-2019)

Cho dãy số nguyên dương (xn) thỏa mãn 0x0<x1100

xn+2=7xn+1xn+280,n0.

a) Chứng minh rằng nếu x0=2,x1=3 thì với mỗi số nguyên dương n, tổng các ước nguyên dương của xnxn+1+xn+1xn+2+xn+2xn+3+2018 thì chia hết cho 24.

b) Tìm tất cả các cặp số (x0,x1) để số xnxn+1+2019 là số chính phương với vô số số n.

Lời giải.

a) Bổ đề. Số nZ+ thỏa mãn 24n+1 thì tổng các ước dương σ(n) của nó chia hết cho 24.

Thật vậy, nếu d là ước của n thì nd cũng là ước của n. Do n2 (mod 3) nên nó không thể là số chính phương, chứng tỏ các ước của nó có thể chia cặp với dạng d+nd=d2+nd.

Chú ý rằng n2 (mod 3)d21 (mod 3) nên tổng trên chia hết cho 3.

Mặt khác, n7 (mod 8)d1,3,5,7 (mod 8), suy ra d21 (mod 8) nên tổng trên cũng chia hết cho 8. Vì (3,8)=1 nên tổng trên chia hết cho 24, bố đề được chứng minh.

Trở lại bài toán,

Đặt yn=xnxn+1+xn+1xn+2+xn+2xn+3, ta cần chứng minh rằng σ(yn+2018) chia hết cho 24. Ta cũng có 20182 (mod 24) nên theo bố đề, ta cần có yn3 (mod 24).

Xét chu kỳ của số dư khi chia cho 3 của dãy thông qua nhận xét xn+2xn+1xn+1 (mod 3) ta có 2,0,2,0,2,0, dãy số dư này tuần hoàn theo chu kỳ 2 và

yn02+20+02=0 (mod 3).

Lại xét chu kỳ của số dư khi chia cho 8 của dãy thông qua nhận xét xn+2xn+1xn (mod 8) ta có 2,3,3,2,3,3,2,3,3, nghĩa là dãy này tuần hoàn với chu kỳ 3 và

yn23+33+32=5 (mod 8).

Suy ra yn+3 vừa chia hết cho 3, vừa chia hết cho 8 nên yn3 (mod 24). Ta có đpcm.

b) Theo bổ đề đã biết, ta thấy rằng tồn tại CZ sao cho xn+12xnxn+2280xn+1=C. Từ đó suy ra

xn+12xn(7xn+1xn+280)280xn+1=C xn+12+xn27xn+1xn280(xn+1+xn)=C (xn+1+xn140)2=9(xn+1xn+2019)92019+C+1402 un2=vn2+C+1429

trong đó, un=xn+1+xn140, vn=3xn+1xn+2019 với mọi n0.

Vì dãy (xn) tăng mà các giá trị đều là số nguyên nên dãy này không bị chặn, do đó, (un) tăng và không bị chặn. Đồng thời, nếu xnxn+1+2019 là số chính phương thì vnZ+.

Do đó, un+vnC+1429 với vô hạn giá trị n. Rõ ràng điều này chỉ xảy ra khi C+1429=0. Vì thế nên ta có đẳng thức

(xn+1+xn140)2=9(xn+1xn+2019)

với mọi số tự nhiên n.

Ta có (x0+x1140)220199>44232=1322 nên |140x0x1|1330x0<x1<101 nên 140(x0+x1)133, tức là x0+x17. Ta cũng có

C=x12+x027x1x0280(x1+x0)=1429.

Để ý rằng x12+x0249 nên 1429=C<49280(x1+x0), kéo theo x0+x15.

Với x1+x0=7 thì x12+x027x1x0=531 và với x1+x0=6 thì x12+x027x1x0=251, dễ thấy đều không thỏa. Do đó x0+x1=5, kéo theo x0x1=6 nên dễ thấy x0=2, x1=3.

Vậy cặp giá trị cần tìm là (x0;x1)=(2;3).

Bài toán

Cho dãy số (Fn) xác định bởi F1=F2=1

Fn+2=Fn+1+Fn,n. và dãy số (Ln) xác định bởi L1=1,L2=3Ln+2=Ln+1+Ln,n. Chứng minh rằng :

a) (Fn,Fn+1)=1(Ln,Ln+1)=1 với mọi n, trong đó (a,b) là ước chung lớn nhất của ab.

b)Fn|Fnk.

c) (Fm,Fn)=F(m,n)

d) Fm|Fn khi và chỉ khi m|n

e) Lm|Fn khi và chỉ khi n=2km

f) Lm|Ln khi và chỉ khi n=(2k+1)m

g) Gọi R là số dư của Fn khi chia cho Fm (n>m). Chứng minh rằng tồn tại s sao cho R=Fs hoặc FmR=Fs.

h) Gọi R là số dư của Ln khi chia cho Lm (n>m). Chứng minh rằng R=0 hoặc tồn tại s sao cho R=Ls hoặc LmR=Ls.

Lời giải

a) Dễ thấy rằng hai số Fibonacci liên tiếp không có ước chung lớn hơn 1. Nếu Fn+2Fn+1 có một ước chung d, thì Fn=Fn+2Fn+1 cũng sẽ chia hết cho d. Do đó, ta có thể tiếp tục xuống đến F2=1 chia hết cho d. Vì d là số nguyên dương, nên d chỉ có thể là 1. Lập luận tương tự cũng áp dụng cho các số Lucas.

b) Fnk=αnkβnkαβ=αkβkαβ(α(n1)k+α(n2)kβk+α(n3)kβ2k++αkβ(n2)k+β(n1)k)

Trong dấu ngoặc bên phải, số hạng đầu tiên và số hạng cuối cùng có thể được ghép cặp để tạo thành một số Lucas:

α(n1)k+β(n1)k=L(n1)k

Các số hạng thứ hai và áp chót có thể được ghép cặp để tạo thành tích của (1)k và một số Lucas:

α(n2)kβk+αkβ(n2)k=αkβk(α(n3)k+β(n3)k)=(αβ)kL(n3)k=(1)kL(n3)k

Và cứ tiếp tục như vậy. Lưu ý rằng số lượng số hạng trong dấu ngoặc bên phải là n. Nếu n là số chẵn, thì các số hạng sẽ kết hợp thành từng cặp đối xứng để tạo thành các số Lucas, rõ ràng là một số nguyên.

Nếu n là số lẻ, thì các số hạng vẫn ghép cặp đối xứng ngoại trừ số hạng ở giữa, có dạng (αβ)(n1)k/2, rõ ràng là một số nguyên. Một lần nữa, biểu thức trong dấu ngoặc bên phải là số nguyên. Do đó ta có điều phải chứng minh.

d) Đây chỉ là hệ quả của câu c.

Bài toán (VMO 2017-2018)

Cho dãy số (xn) xác định bởi x0=2, x1=1

xn+2=xn+1+xn,n0.

a) Với n1, chứng minh rằng nếu xn là số nguyên tố thì n là số nguyên tố hoặc n không có ước nguyên tố lẻ.

b) Tìm tất cả các cặp số nguyên không âm (m,n) sao cho xn chia hết cho xm.

Lời giải.

a) Ta chứng minh được xn=αn+βn với mọi nN, trong đó α<0<β là hai nghiệm của phương trình đặc trưng λ2λ1=0.

Giả sử xn là số nguyên tố với n là số nguyên dương có ước nguyên tố lẻ. Khi đó, n có dạng pq với p là số nguyên tố lẻ và q là số tự nhiên lớn hơn 1. Ta có

xpq=αpq+βpq=(αq+βq)(αq(p1)αq(p2)βq+αq(p3)β2qαqβq(p2)+βq(p1))=(αq+βq)[(αq(p1)+βq(p1))++(1)(q+1)(p+1)2(α2q+β2q)+(1)(q+1)(p1)2]=xq(xq(p1)++(1)(q+1)(p+1)2x2q+(1)(q+1)(p1)2)

nên xqxpq. Mặt khác, dễ thấy dãy (xn) tăng ngặt kể từ n=1 nên xq>x1=1. Do đó, xpq là hợp số, mâu thuẫn. Vậy, với n1, để xn là số nguyên tố thì n là số nguyên tố hoặc n không có ước nguyên tố lẻ.

b) Xét các trường hợp sau:

  • Trường hợp 1: m=0. Xét trong modulo 2, ta có x0=0, x1=1, x2=1, x3=0, x4=1, x5=1, x6=0, Do đó, xn chẵn với mọi n chia hết cho 3 và lẻ trong các trường hợp còn lại. Từ đây suy ra, để xn chia hết cho x0, ta phải có n chia hết cho 3. Cặp số (m,n) thỏa mãn trong trường hợp này là (0,3k) với kN.

  • Trường hợp 2: m=1. Dễ thấy (m,n)=(1,k) với kN.

  • Trường hợp 3: m>1. Với mọi k0, ta có

    (αk+βk)(α+β)(αk++βk+)=(αβ)(αk+βk)=(1)(αk+βk).

    Do đó

    xk+=xkx(1)xk.(1)

    Nói cách khác, với mọi k20, ta có

    xk=xkx(1)xk2.

    Do đó xk chia hết cho x khi và chỉ khi xk2 chia hết cho x, xk2 chia hết cho x khi và chỉ khi xk4 chia hết cho x (nếu k4), Một cách tổng quát, ta có xk chia hết cho x khi và chỉ khi xk2t chia hết cho x (nếu k2t, tN). (2)

    Bây giờ, do xn chia hết cho xm nên xnxm3, suy ra nm>1. Đặt n=qm+r với qN, rN, 0rm1. Xét các trường hợp sau:

    • Trường hợp 3.1: q chẵn. Theo nhận xét (2), ta có xn chia hết cho xm khi và chỉ khi xr chia hết cho xm. Suy ra

      xrxm.

      Nếu r1 thì từ bất đẳng thức trên, ta suy ra rm (do {xn} tăng ngặt với mọi n1), mâu thuẫn. Do đó r=0, tuy nhiên điều này cũng mâu thuẫn vì

      xmx2=3>x0=xr.

    • Trường hợp 3.2: q lẻ. Theo nhận xét (2), ta có xn chia hết cho xm khi và chỉ khi xm+r chia hết cho xm. Mặt khác, theo (2), ta lại có

      xm+r=xmxr(1)rxmr

      nên xn chia hết cho xm khi và chỉ khi xmr chia hết cho xm. Nếu 0<r<m, ta có 1mr nên xmr<xm, mâu thuẫn. Do đó, r=0 và giá trị này thỏa mãn. Suy ra, trong trường hợp này, cặp số (m,n) thỏa mãn yêu cầu là (m,(2k+1)m) với kN.

      Tóm lại, các cặp số cần tìm là (0,3k),(1,k)(m,(2k+1)m) với m,kN,m>1.

    Bài toán (IMO Shortlist 1988)

    Cho dãy số nguyên (an) xác định bởi :

    a0=0,a1=1,an+2=2an+1+an.

    Chứng minh rằng 2kan khi và chỉ khi 2kn.

    Lời giải

    Bổ đề : Cho dãy số (xn) xác định bởi x1=a,x2=b và :

    xn+2=bxn+1+axn.

    Khi đó với m nguyên dương bất kỳ, ta có :

    xm+n=xnxm+1+xn1xm()

    Chứng minh bổ đề

    Ta chứng minh bằng quy nạp theo m, với m=1 thì hiển nhiên. Giả sử (*) đúng với mm1. Xét với m+1:

    xm+n+1=bxm+n+axm+n1=b(xnxm+1+xn1xm)+a(xnxm+xn1xm1)=xn(bxm+1+axm)+xn1(bxm+axm1)=xnxm+2+xn1xm+1

    Quy nạp hoàn tất, như vậy ta có đẳng thức (*).


    Kết quả này là một kết quả quan trọng được dùng cho nhiều bài toán.

    Trở lại bài toán

    Ta chọn m=n trong (*) thì ta được :

    x2n=xn(xn1+xn+1)=2xn(xn+xn1)()

    Bằng quy nạp ta chứng minh được a2n+1 lẻ và a2n chẵn. Như vậy xn+xn1 lẻ.

    Nếu 2kan. Đặt n=2mt, với t lẻ. Sử dụng (*) ta được :

    2kan=a2mt2k1a2m1t2k2a2m2t

    Nếu k>m thì cứ tiếp tục quá trình này, ta được 2kmat và điều này vô lí vì at lẻ (do t lẻ).

    Vậy phải có km, suy ra 2k2mt=n.

    Nếu 2kn. Đặt n=2kt và cũng sử dụng (**) ta có :

    20at21a2t22a22t2ka2kt=an

    Bài toán hoàn tất.

    Link

Nhận xét

Bài đăng phổ biến từ blog này

Các bài toán về thặng dư toàn phương

Căn nguyên thủy và ứng dụng