Tính chất của dãy số Fibonacci

1) $(F_n,F_{n+1})=1$

2) Nếu $n |m $ thì $F_n |F_m$
Ta chỉ cần chứng minh tính chất sau:
$F_{m+n}=F_{m-1}F_{n+1}+F_{m}.F_{n}$
Quy nạp theo $n$, với $n=1$ đúng
Giả sử đúng với $n=k$ khi đó với $n=k+1$ thì:
$F_{m+k+1}=F_{m+k}+F_{m+k-1}=(F_{m-1}F_{k+1}+F_{m}.F_{k})+(F_{m-1}_F{k}+F_{m}.F_{k-1})=F_{m-1}F_{k+2}+F_{m}F_{k+1}$
Vậy theo nguyên lí quy nạp ta có điều phải chứng minh.
Cho $m=kn$ thì ta suy ra thêm được một số tính chất sau
3)Nếu $F_n$ chia hết cho $F_m$ thì $n$ chia hết cho $m$ (m>2)
4) $(F_m,F_n)=F_{(m,n)}$
5) $n \ge 5$ và $F_n$ là số nguyên tố thì n cũng là số nguyên tố.
6) $(F_n)$ chứa vô hạn những số nguyên tố đôi một cùng nhau
7) $F_{5n}=5F_nq_n$ $q_n$ không chia hết cho 5.

Chứng minh:

Cách 1:
$F_{5n}=\frac{q_1^{5n}-q_2^{5n}}{\sqrt 5}=F_n(q_1^{4n}+q_1^{3n}q_2^n+(q_1q_2)^2n+q_1^nq_2^{3n}+q_2^{4n})=F_n(L_{4n}+(-1)^nL_{2n}+1)=F_n(L_{2n}^2+(-1)^nL_{2n}-1).$ Vì thế $v_5(F_{5n})=v_5(F_n)+v_5(L_{2n}^2+(-1)^nL_{2n}-1)$.
$L_n^2-5F_n^2=4(-1)^n$
$F_{2n}=F_nL_n$.
Do $n=1$ $L_2^2-L_2-1=5$.
$L_n,F_n$ chu kì 20 mod 5 ($L{n+10}=-L_n\mod 5, F_{n+10}=-F_n\mod 5$. $5|F_n$ khi và chỉ khi $5|n$
nếu $n>1$ $5|F_5|F_{5k}$. Vì thế $5|n$  $L_{2n}^2=4(-1)^n\mod 25$. Vì $10|n$ $L_{2n}=\pm 2\mod 25$.
$L_{2n}^2+(-1)^nL_{2n}-1=4+2-1=5\mod 25$. Vậy $v_5(F_{5n})=v_5(F_n)+1\to v_5(F_n)=v_5(n).$ (Đpcm)

Cách 2:



Dùng cách tính chất ở trên, nếu $a|b$ thì $F_a|F_b$ và , $(F_a,F_b)=F_{(a,b)}$.

Đặt $n=5^p \cdot q$ Với $(5,q)=1$. thì $v_5(n)=p$. thấy rằng $(F_{5^k \cdot m}, F_{5^k}) = F_{5^k}$ . Hiển nhiên $5^k|F_{5^k}$.và $5^{k+1}$ không là ước của ${F_{5^k \cdot m}}$ vì nó sẽ dẫn đến $5|m$ mâu thuẫn. Vậy $v_5(F_{5^k \cdot m})=k$ . Đpcm $\Box$




8) $F_n \vdots 5^k$ khi và chỉ khi $n \vdots k$
9) $F_n$ có tận cùng là 0 khi và chỉ khi $n \vdots 15$

10) $F_n$ có tận cùng là hai chữ số 0 khi và chỉ khi $n \vdots 150$

Bổ đề bất đẳng thức số học và đề USA MO 1995

Ta có một bổ đề bất đẳng thức số học dùng để đánh giá bội chung nhỏ nhất như sau:
Với mọi số nguyên dương n tồn tại một số $c_n >0$ sao cho:

$lcm(m,m+1,m+2,..m+n)>c_nm(m+1)(m+2)..(m+n)$ (ký hiệu lcm, gcd lần lượt là bội chung nhỏ nhỏ và ước chung lớn nhất)

Chứng minh:

Ta có:

$lcm(m,m+1,m+2,..m+n)=lcm(lcm(m,m+1,..m+n-1),m+n)\\=\frac{lcm(m,m+1,..m+n-1)(m+n)}{gcd(lcm(m,m+1,..m+n-1),m+n)} \\ \ge \frac{lcm(m,m+1,..m+n-1)(m+n)}{gcd(m(m+1)(m+2)..(m+n-1),m+n)}\\ \geq \frac{lcm(m,m+1,..m+n-1)(m+n)}{n!}$

Bằng quy nạp ta chứng minh được:
$lcm(m,m+1,m+2,..m+n)\ge\frac{m(m+1)(m+2)..(m+n)}{n!(n-1)!..1!}$

Như vậy bổ đề được chứng minh.
Ta xét bài toán sau:

(USA MO 1995) Cho dãy số nguyên $(a_n)_{n \ge 0}$ thỏa mãn điều kiện sau:

i) $m-n | a_m -a_n$

ii) tồn tại đa thức f(x) sao cho |a_n| \le $f(n)$ với mọi $n \ge 0$

Chứng minh rằng tồn tại đa thức g(n) sao cho $g(n)=a_n$ với mọi $n \ge 0$

Lời giải:



Giả sử $P$ có bậc $d$. Đặt $Q$ là đa thức bậc cao nhất $d$ với $Q(x)=q_x$ cho $0\leq x\leq d$. Vì $q_x$ là những số nguyên, $Q$ là đa thức hệ số hữu tỉ và tồn tại $k$ để $kQ$ có hệ số nguyên. Vì thế $m-n|kQ(m)-kQ(n)$ với mọi $m,n\in \mathbb N_0$.




Ta sẽ chứng minh rằng $Q$ là đa thức cần tìm


Cho $x>n$ Ta có

$ kq_x \equiv kq_m\pmod{x-m}\text{với mọi }m\in[0,d]$

Vì $kQ(x)$ thỏa mãn điều kiện nên $kq_m=kQ(m)$,

$kq_x\equiv kQ(x)\pmod{x-m}\text{ với mọi }m\in [0,d] $
( lưu ý kQ(x) -kQ(m) chia hết x-m)
và vì thế

$ kq_x\equiv kQ(x)\pmod{\text{lcm}(x,x-1,\ldots, x-d)}. \;(1) $

Vì $P(x), Q(x)$ có bậc là $d$, Vì thế với $x$ đủ lớn ( $x>L$) Ta có $\left|Q(x)\pm\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}\right|>P(x)$. Vì (1) $kq_x$ phải lớn hơn một bội của $\text{lcm}(x,x-1,\ldots, x-d)$ so với $kQ(x)$; vì thế $q_x$ phải lớn hơn một bội của $\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}$ với $Q(x)$, với $x>L$ Ta phải có $q_x=Q(x)$.




Bây giờ với mọi $y$ ta có $kQ(y)\equiv kQ(x)\equiv kq_x \equiv kq_y\pmod{x-y}$ với $x>L$. Vì $x-y$ có thể lớn tùy ý nên ta phải có $Q(y)=q_y$, đpcm

Hai bài số học của Mỹ và Trung Quốc.

1/ (Mỹ) Chứng minh rằng với mỗi số nguyên $n \ge 2$ đều tồn tại một tập S gồm n số nguyên thoả mãn $(a-b)^2$ là ước của ab với mọi a,b thuộc S phân biệt.
2/ ( Trung Quốc) Tìm số nguyên không âm K nhỏ nhất sao cho với mọi tập con K- phần tử của tập hợp {1,2,..50} tồn tại hai phần tử a,b phân biệt mà a+b là ước của ab

Giải

1/ Ta chứng minh bằng quy nạp rằng với mỗi số nguyên dương n đều tồn tại một tập hợp $S_n$ gồm n phần tử thoả mãn điều kiện đã cho.

Với n=2 chọn $S_2$={0,1}. Giả sử khẳng định đã đúng đến n. Ta chứng minh khẳng định đúng với n+1. Gọi L là BCNN của các số khác 0 có dạng $(a-b)^2$ và ab trong đó $a,b \in S_n$. Đặt:

$S_{n+1}$={$s+L: s \in S_n$} $\cup ${0}

Khi đó, vì $L \ge 0$ nên $S_{n+1}$ chứ n+1 phần tử phân biệt không âm. Ta chứng minh tập $S_{n+1}$ thoả mãn.

Lấy u,v, bất kì. Nếu trong u,v có một số bằng 0 thì hiển nhiên. Nếu u,v đều khác 0 thì tồn tại hai phần tử a,b thuộc S sao cho
$u=L+a, v=L+b.$

Từ các chọn ta có $uv \vdots (u-v)^2$. Vậy ta đã chứng minh với n+1. Theo nguyên lí quy nạp ta có đpcm
2/ Giá trị nhỏ nhất của k=39. Cho a,b thuộc S thoả mãn a+b chia hết ab. Đặt $c=(a,b), a=ca_1, b=cb_1$ thì $(a_1,b_1)=1$ Khi đó $c(a_1+b_1)$ chia hết $c^2a_1b_1$ Suy ra $a_1+b_1$ chia hết $ca_1b_1$. Vì $a_1, b_1$ không có ước chung nên $a_1+b_1$ không chia hết $a_1$ và $b_1$. nên c chia hết cho $a_1+b_1$.(1)

Vì S là tập con {1,..,50}, ta có $a+b \le 99$, vì thế $c(a_1+b_1) \le 99$, từ (1) suy ra $a_1+b_1 \le 9$ mặt khác, $a_1+b_1 \ge 3$ từ đây ta tìm được các cặp (a,b):



(6, 3); (12, 6); (18, 9); (24, 12); (30, 15); (36, 18); (42, 21); (48, 24);

(12, 4); (24, 8); (36, 12); (48, 16)

(20, 5), (40, 10), (15, 10), (30, 20), (45, 30)

(30, 6)

(42, 7), (35, 14), (28, 21)

(40, 24)

(45, 36)


Có 23 cặp, 24 số. Còn lại 26 số. Suy ra K>26. Ta cần tìm giá trị nhỏ nhất của K-26 sao cho ta sẽ chọn được hai số trong 24 số thuộc 1 cặp. Ta tìm được giá trị 13 là nhỏ nhất .Thật vậy, giả sử nhỏ hơn 12 thì ta chọn 26 số đó với các số sau đây 3,4,5,7,8,9,10,14,16,28,30,36.


Vậy K nhỏ nhất là 39.