Dãy Số Và Các Tính Chất Số Học - Lê Phúc Lữ - 123doc

Chứng minh rằng tất cả số hạng của dãy đều là số nguyên... Bằng quy nạp, ta dễ dàng có được đpcm..[r]

1

Bài giảng trường Đông 2013

DÃY SỐ VÀ CÁC TÍNH CHẤT SỐ HỌC

PHẦN LÝ THUYẾT

Trong phần này, ta xét dãy số  u n với u u1, 2,u n2 au n1bu n n, 1 và 2

1 3 2

c u u u

Tính chất 1

2 1 ( ) (n 3 1 2)

      với mọi số tự nhiên n

Tính chất 2

Nếu b  1 thì ta có

2 1 2

n n

n

u

u







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

Tính chất 3

Nếu u u a b1, 2, , nguyên thì 2 2

1

( 4 ) 4( )n

n

a  b u   b c là số chính phương với mọi n

Tính chất 4

Xét dãy  v n thỏa mãn: v1 u v12, 2 u v22, n2 (a22)v n1v n2c thì v n u n2 với mọi n

(trong trường hợp b  1)

Chứng minh chi tiết cho các tính chất này có thể xem thêm trong bài viết:

“Khám phá một số tính chất của dãy truy hồi tuyến tính cấp 2”

trong tài liệu Chuyên đề Toán học số 9

Bài tập rèn luyện

Bài 1 Cho dãy số ( )x n thỏa mãn x11,x2  1 và x n2  x n12 ,x n n 1, 2, 3,

Xét dãy  v n xác định bởi 1 2

1

2n 7 , 2, 3, 4,



Chứng minh rằng mọi số hạng của dãy ( )v n là số chính phương

2

Bài 2 Cho dãy số  x n xác định bởi x0 0,x11,x n2 rx n1x n, n 1 Chứng minh rằng x1x3x5 x2m1 x m2 với mọi số nguyên dương m

Bài 3 Cho số nguyên dương m Xác định dãy số ( )x n như sau:

2

0 0, 1 , n 1 n n 1, 1, 2, 3,

x  x m x  m x x  n Chứng minh rằng với mọi cặp số tự nhiên ( , )a b với a b là nghiệm của phương trình

2 2

1

a b

m

ab





 khi và chỉ khi ( , ) (a b  x x n, n1) với n là số tự nhiên nào đó

Bài 4 Cho dãy số ( )x n xác định bởi x0 0,x11,x n2 2x n1x n1,n1, 2, 3,

Chứng minh rằng 4x x n n21 là số chính phương với mọi n

Bài 5 Cho dãy số ( )u n với 1 2

1, 2,

u  u  u n





Tìm tất cả các giá trị của n sao cho u  n 1 là số chính phương

Bài 6 Cho dãy số ( )u n xác định bởi 0 1

1, 9,

10 , 1, 2, 3,

u  u  u n





Chứng minh rằng 5 1

4

u  u

và

2

2

n

u 

là các số nguyên với mọi n

Bài 7 Cho dãy số nguyên  a n xác định bởi công thức truy hồi sau

2 1

2

4

n n

a

a







Chứng minh rằng tất cả số hạng của dãy đều là số nguyên

Bài 8 Tìm tất cả các dãy vô hạn các số nguyên dương  a n bị chặn và thỏa mãn

1 2

1 2

, 3

,

n

a a

 

 



3

Lời giải

Đặt y n a a n, n1,n1, 2, 3, Ta thấy rằng y n1 chia hết cả u n1 và u n2 nên cũng chia hết y a n n2a n1 a n

Suy ra y n1 chia hết cả a n1,a n nên y n1|y n Do đó,  y n là dãy không tăng của các số nguyên dương và kết thúc là dãy hằng với hằng số y nào đó

Xét dãy khi y n y: ya n a n1a n2 Ta xét các trường hợp:

- Nếu y 1, a n a n1a n2 thì lima   n nên dãy không bị chặn và mâu thuẫn

1 2

 

Tương tự, a n1maxa a n, n1maxa n2,a n1 nên maxa a n, n1maxa n1,a n2 và dãy này vô hạn, mâu thuẫn với tính chất nguyên dương của dãy

- Nếu y  thì 2 2a n a n1a n2 nên 1 1  1 2

2

a a      a  a 

  nên suy ra hiệu a na n1

tiến về 0 nên a i là dãy hằng với i đủ lớn

Hơn nữa, từ 2a n a n1a n2, ta có 2a a n, n1 nên a  i 2 với mọi i i 0 đủ lớn

Nếu a n a n1 2 với n 1 thì a n1,a n  a n1, 21 hoặc 2 mà

1

1

, 2

n

a







Từ đó suy ra a  n 2 với mọi n và dãy số này thỏa mãn đề bài

Bài 9 Cho  a n là các số nguyên dương lẻ xác định như sau

1 , 2

a r a s và a n là ước dương lẻ lớn nhất của a n1a n2 Chứng minh rằng với n đủ lớn thì a n là hằng số và xác định hằng số đó theo , r s

4

Lời giải

Kí hiệu s n( ) là ước nguyên dương lẻ lớn nhất của n Với m là số nguyên dương lẻ, ta

có s(2t m)m với t nguyên dương

Suy ra với ,m n lẻ thì m n 2 và ( )

2

m n

s m n  

Đặt M n maxa a n, n1 với n 1, 2, 3,

2 ( 1)

2

a a



1

a a

Do đó M n2 M n và đẳng thức xảy ra khi và chỉ khi a n a n1 Do M  n 1 nên với n đủ

lớn thì M n là dãy hằng, tức là n0 sao cho

0 0 1

a a  c, quy nạp thì suy ra được rằng

0

n

a c n n

Mặt khác, đặt d r s, thì a a n, n1d với mọi n nên cd

Vậy tồn tại n đủ lớn sao cho a n là dãy hằng và khi đó a n  r s,

Bài 10 Cho dãy số nguyên dương ( )a n thỏa a na n11 Đặt b na1a2 a n Chứng minh rằng luôn có một số chính phương trong dãy sau b b n, n1,b n2, ,b n11

Lời giải

Giả sử rằng không có số chính phương nào trong dãy b b n, n1,b n2, ,b n11, tức là

tồn tại m nguyên dương sao cho 2  2

1

m  b b    m  hay

b   b 

Ta sẽ chứng minh bằng quy nạp rằng b n1  b n 1 với mọi số nguyên dương n

Suy ra b n1b n2 b n  1 a n12 b n  1 4a1a2  a n1  a n12

Bằng quy nạp, ta dễ dàng có được đpcm

5

DÃY SỐ VÀ TÍNH TUẦN HOÀN

x a x b x c

x  x x  x  n





Chứng minh rằng với mọi cách chọn các số , ,a b c thì dãy số đã cho hoặc tồn tại vô số số

hạng chia hết cho 2013 hoặc không tồn tại số hạng nào chia hết cho 2013

Bài 2 Cho p là số nguyên tố và ,a b là hai số nguyên thỏa mãn a2ab b 2 không chia

hết cho p Xét dãy số 1 2

v a v b

v  v v  n





Chứng minh rằng dãy v nmodp tuần hoàn và chu kì không phụ thuộc vào p

Bài 3 Cho một số nguyên tố lẻ p thỏa mãn 2h 1(mod )p với mọi hp1,h * và

một số chẵn ( ; )

2

p

a p Xét dãy số ( )a n xác định bởi:a0 a a, n1p b n n, 0,1, 2, với b n

là ước số lẻ lớn nhất của a n

Chứng minh rằng ( )a n là dãy số tuần hoàn và tìm chu kì dương nhỏ nhất của nó

Lời giải

Ta thấy rằng với mọi i, a i là số chẵn, a i  p b i1 p mà

1

i

        

p

   , tức là giá trị của các số hạng của dãy ( )a n đã cho là hữu hạn

Đặt 2k i

a  b với ,k b i i,k i 0 và b i là số lẻ Nếu b i b j thì a a i| j hoặc a j|a i, theo nhận xét trên thì a i a j vì nếu ngược lại thì cả hai số này không thể nằm trong khoảng

,

2

p

p

  được Cũng theo nhận xét trên thì phải tồn tại các giá trị ; , ,

2

p

i j i j  p

  thỏa mãn a i a j; mặt khác a i  p b i1,a j  p b j1 nên b i b j, do đó a i1a j1, tiếp tục quá trình này, ta được a0 a j i , tức là dãy đã cho tuần hoàn từ số hạng đầu tiên Nếu đặt

T  j i thì T chính là chu kì dương nhỏ nhất cần tìm của dãy đã cho

6

Ta biết rằng lũy thừa của 2 trong n! là

1 2i

i

n



 nên nếu đặt K là tích của tất cả các số tự

nhiên trong khoảng ,

2

p p

  , tức là ( 1)!

1

! 2

p K p







, thì lũy thừa của 2 trong K là

1 1

i







      

   

 , đó cũng chính là lũy thừa của 2 trong tích của tất cả các số

chẵn trong khoảng ,

2

p p

  Suy ra 1 2 3

1

2

T

p

k k k  k   Đẳng thức xảy ra khi và

chỉ khi tập hợp a a a1, 2, 3, ,a T chính là tập hợp tất cả các số chẵn trong khoảng ,

2

p p

1 2 3 2k k k k T 1 2 3 (mod )

a a a a      b b b b p

Theo giả thiết thì a i  b i1(mod )p nên a a a1 2 3 a T  ( 1)T b b b0 1 2 b T1(mod )p , do cách chọn

T nên b0 b T, tức là 1 2 3 ( 1)T 1 2 (mod )

a a a a   b b b p , suy ra:

1 2 3 1 2 3

do ( , ) 1b p i  (b b b1 2 3 , ) 1b p T  Ta được 2( 1 2 3 )

2 k k k k T 1(mod )

p

   

Hơn nữa, cũng theo giả thiết thì 2h 1(mod ),p h1, 2, 3, ,p2 nên từ hệ thức trên, suy

1

2

p

k k k  k  p k k k  k  

So sánh hai bất đẳng thức trên về tổng k1k2k3 k T, ta được

1 2 3

1

2

T

p

k k k  k  

Do đóa a a1, 2, 3, ,a T chính là tất cả các số chẵn trong khoảng ,

2

p p

 , suy ra

T   p    

Vậy dãy số đã cho tuần hoàn với chu kì dương nhỏ nhất là 1

4

p

T    

Bài 4 Cho dãy số  x n thỏa mãn

*

x  x x  n









7

Chứng minh rằng nếu p là số nguyên tố và x2006 chia hết cho p thì

a Tồn tại j 2006 mà x chia hết cho j p

b Tồn tại TN* sao cho với mọi n 2006 thì x T n x n(mod )p

c Tồn tại j 2006 mà x j j chia hết cho x20062006

Lời giải

a Chú ý rằng nếu ( , ) 1n p  thì tồn tại m sao cho mn1(mod )p

b Sử dụng kết quả của câu a

c Giả sử 1 2

2006 1a 2a a k

k

x p p p , với mọi i1, 2, 3, ,k thì theo câu b, tồn tại T i sao cho

2006 0(mod )

i

lT

x   p Đặt T[ ,T T T1 2, 3, , ]T k thì x2006lT 0(modp p1 2 )p k

Chọn l đủ lớn sao cho 2006lTmax 2006 , 2006 , , 2006 a1 a2 a k thì dễ dàng có được 2006 2006

2006 2006

lT lT

x  x

  Đây chính là đpcm

SỬ DỤNG CÔNG THỨC TỔNG QUÁT

Bài 1

Cho dãy số 1 2

7, 50,

u  u u 





Chứng minh rằng u1996 chia hết cho 1997

Bài 2

Cho dãy số ( )u n thỏa mãn 0 2

1

2,

u

 







Chứng minh rằng số  2 

1

8

5 u  n có thể biểu diễn thành tổng bình phương của ba số tự nhiên liên tiếp

8

Bài 3

Cho dãy số  u n thỏa mãn 1 2

0, 1,

1, 1

u u u  n





Chứng minh rằng với p là số nguyên tố lớn hơn 5 thì u u p( p11) chia hết cho p

Bài 4

Cho dãy số nguyên ( )a n thỏa mãn 0 1

a a  a  n





Chứng minh rằng a20122010 chia hết cho 2011

Bài 5

Cho dãy số ( )a n thỏa mãn 1 2

1, 2011,





Chứng minh rằng 2012 1

2012

a 

là số chính phương

Lời giải Ta xét bài toán tổng quát sau

Cho p là số nguyên dương lẻ lớn hơn 1

Xét dãy số nguyên dương  x n được xác định bởi 1 2 *

x  px  x n





Chứng minh rằng 1 1

1

p

x p

 

 là số chính phương

Bài toán này có một số lời giải như sau

Cách 1 (dùng công thức tổng quát của dãy và biến đổi trực tiếp)

Phương trình đặc trưng của dãy số đã cho là 2 2

t  pt t  pt  có

2

1 0

p



    nên phương trình có hai nghiệm là 2 2

t  p p  t  p p  Công thức tổng quát của dãy đã cho là x n At1nBt n2n, 1, 2,3,

9

Thay n 1, 2 tương ứng với hai số hạng cho trước của dãy, ta được hệ phương trình sau:

1 2

2 2

1 2

1

At Bt

At Bt p







Giải hệ này, ta thu được 2, 1

A B hay

1 1

1 2 , 1, 2,3,

2

n

 



1 2

1 1 1 2 2

Chú ý rằng t1t2 2 , p t t1 2 1 nên t1  t2  t1t22 t t1 2  2(p1)

Hơn nữa, ta cũng có S n t1nt2n, n 1 vì S S  1, 2 và S n2 2pS n1S n

Đặt t1 a, t2 b thì a b  2(p1),ab1 và t1p/ 2t2p/ 2 a p b p

Ta có

3

1

2

p

p





1 2



 

1p 2p 2( 1) 1p 2p 2( 1)

t t N p  t t N p

p

N

  là số chính phương Ta có đpcm

Cách 2 (Xét dãy số phụ và dùng quy nạp)

10

Ta thấy rằng

2 2

3

1,

1

1

x

p





Từ công thức truy hồi là x n2 2px n1x n, ta có 2px n1 x n x n2 Suy ra

x  p px x x  p x  px  x  p  x x   n

Ta sẽ xây dựng công thức của dãy 2 1

, 1, 2,3,

1

n n

x

p



 và chứng minh các số hạng của dãy này đều nguyên

Xét dãy  y n thỏa mãn 1 2

, 1

y  ay  by n







với a b, được chọn sau

Do y3 4p2p1 nên 2

a p  b p  p ; ta có thể chọn a2 ,p b 1

Dãy số tương ứng là 1 2

y  py  y n







Ta sẽ chứng minh bằng quy nạp rằng 2 2 1

1

n n

x

p



Với n 1, 2, khẳng định (*) đúng

Giả sử ta có 2 2 2 2 2

1

,





y  y y   py  y y y  py y   y  y  y n

Hơn nữa y y3 1y22 2p2 nên y n2y ny n21 2p2,n

Từ công thức xác định dãy thì

11

y y   py   y y   y y   p y   y y   p y   p y  hay

2



Khẳng định (*) cũng đúng với n 2 Theo nguyên lí quy nạp, (*) được chứng minh

Do đó, ta đã chứng minh được với mọi n chẵn thì 1

1

n

x p



 là số chính phương; nói riêng,

ta cũng có 1 1

1

p

x

p

 

 cũng là số chính phương Ta có đpcm

DỰ ĐOÁN VÀ QUY NẠP

Bài 1

Cho dãy số nguyên dương a a a1, , , 2 3 thỏa mãn a 1 1 và

 1 2 

1

2 if a 2 , , , , 2 0

3, otherwise

n

n

a

a





 





Chứng minh rằng với mọi số nguyên dương k thì tồn tại sốn nguyên dương n sao cho

2

1 3

a k a  

Lời giải

Ta tính được

n

Ta thấy rằng a a1, , ,2 a10 là một hoán vị của 1, 2, 3, ,10 và a 11 11 nên bằng quy nạp, ta chứng minh được rằng a10k1 10k1,a10k2 10k4

12

Suy ra với mọi số nguyên dương k đều xuất hiện đúng một lần trong dãy đã cho

Hơn nữa, các số chính phương đồng dư với 0,1, 4, 5,6,9 theo modulo 10 nên ta có đpcm

Bài 2

Cho dãy số (2 3) (2 3)

2 3

n

u     với n 0

a Chứng minh rằng tất cả số hạng của dãy đều nguyên

b Tìm tất cả các số hạng chia hết cho 3 của dãy đã cho

Bài 3

Cho dãy số  a n xác định bởi

 

0, 1,







Chứng minh rằng a n là số chính phương với mọi n

Bài 3

Cho dãy số( )a n thỏa mãn 1 2

1,

a a

a  a a  n





Chứng minh rằng với mọi số nguyên dương n thì a na n12 là số chính phương

Bài 4

a  a  a  a  a n





Chứng minh rằng với mọi n 1 thì a n chia hết cho n

Gợi ý Chứng minh bằng quy nạp rằng a n nF n với F n là số Fibonacci thứ n

MỘT SỐ BÀI TOÁN KHÁC

Bài 1

13

Cho dãy số

0 1

1

1,

3

n

n











Chứng minh rằng 2 1

0

n

k

a  a  a a 



  đvới mọi số tự nhiên n thì a n là số nguyên

Lời giải

Xem thêm lời giải chi tiết (bằng tiếng Hungary) tại đây:

http://www.komal.hu/verseny/2000-03/A.h.shtml

Bài 2

Cho dãy số nguyên ( )a n thỏa mãn

2 1 1

, 2, 3, 4,

n n n

a

a











 Chứng minh rằng với mọi n 1 thì a n là số lẻ

Bài 3

Cho một dãy vô hạn các số nguyên dương ( )a n được xác định như sau

a  a b n , b n là chữ số tận cùng của a n

Tìm điều kiện cần và đủ của a1 để trong dãy số đã cho chứa vô hạn lũy thừa của của 2

Lời giải

Phần thuận:

Do a1 không chia hết cho 5 nên a n không chia hết cho 5 với mọi n Có nhận xét sau:

Chữ số tận cùng của a n đến một lúc nào đó sẽ tuần hoàn với chu kì 2,4,8,6 Do đó

a  a  sm s, 

  Vì 2|a m thì 2

4

4|

4|

m m

a a











nên tồn tại vô hạn m để a m 4l ( l

14

không chia hết cho 5) Suy ra a m4s 4n5s Mà l không chia hết cho 5 nên tồn tại vô hạn ksao cho: 2k lmod 5 hay tồn tại vô hạn ,k s :2k  l 5s

Phần đảo:

Tồn tại vô số số hạng của dãy là lũy thừa của 2 Giả sử 5|a1 thì 5| ,a n n (mâu thuẫn vì

2k không chia hết cho 5)

Vậy điều kiện cần và đủ cần tìm là a1 không chia hết cho 5

Bài 4

Cho n 2 là số tự nhiên Chứng minh rằng tồn tại hữu hạn các bộ n số nguyên dương

a a1, , ,2 a n thỏa mãn đồng thời các điều kiện sau:

(i) a1 a2 a3  a n

(ii) a a a1, , , ,2 3 a n1

(iii) 1  1

1

,

n

i i i



 với quy ước a n1 a1

Lời giải

Đặt d i a a i, i1,i1,2, 3, ,n trong đó a n1 Theo giả thiết, ta thấy rằng, a1

a  d a a d a a  d a i Đưa vào dãy đã cho, ta được

1 2 n 1 1 2 1 2 2 1 2 n 1 n

Từ đây suy ra d na n, nhưng do d na a n, 1 nên d na n hay đẳng thức phải xảy ra

Do đó, ta có a ia i1d i, i 1,n Tiếp theo, ta sẽ chứng minh rằng tồn tại vô số dãy số thỏa mãn đề bài Ta thấy rằng với dãy số thỏa mãn đề bài, tồn tại hữu hạn các số

15

nguyên dương r i sao cho 1, 1,

1

i

i

r

 Do a a1, , ,2 a  n 1 nên

a a2, , ,3 a  n 1 và a a n| 1 Ta sẽ chứng minh bài toán bằng quy nạp

- Với n 2, do a a2| 1 nên ta có thể viết a2 m a, 1km với ,k m  Hơn nữa, do 

a a 1, 2 1 nên m 1 mà a1a a1, 2  a a2, 12 nên với n 2, tồn tại đúng một dãy thỏa mãn đề bài

- Giả sử bài toán đúng với n1, ta sẽ chứng minh rằng tồn tại hữu hạn dãy số thỏa

mãn trong trường hợp n phần tử

Ta có hai trường hợp:

+ Nếu a2 không chia hết cho a n, đặt a2 p a n

q

 với p q,   và   p q, 1,q1

1

, |

r

r



 nên suy ra 1 1 1

r p

q r  là số nguyên dương Với mỗi a2, tồn tại hữu

hạn các giá trị r1 và cũng do có hữu hạn các dãy n1 thỏa mãn nên từ đó suy ra trong trường hợp này, số bộ n phần tử là hữu hạn

+ Nếu a2 chia hết cho a n thì theo nguyên lí quy nạp, tồn tại hữu hạn dãy a a2, , ,3 a n và

do cách xác định 1  1

1

,

n

i i i



 , ta thấy rằng tồn tại hữu hạn dãy số thỏa mãn đề bài

Do đó, theo nguyên lí quy nạp, bài toán được chứng minh

Bài 5

Tìm tất cả các dãy vô hạn các số nguyên dương a a a1, , , 2 3 thỏa mãn đồng thời các tính chất sau:

i) Dãy số đã cho tăng thực sự

ii) Không có các số nguyên dương i j k nào, không nhất thiết phân biệt, thỏa mãn , ,

a a a