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$

Chuyên mục nhỏ về tính chất của dãy tuyến tính cấp 2.

Lời giải:

Đẳng thức sai phân và ứng dụng

(Đẳng thức): Cho f(x) là một đa thức bậc n, có hệ số ứng với $x^n$ là a. Khi đó, ta có:

$\sum_{i=0}^{n}C^i_n.(-1)^nf((x-i)k)=n!.ak^n$

Giải:

Rõ ràng ta có thể giả sử được k=1 ( Vì khi có thể đặt g(x)=f(kx) nên hệ số cao nhất của g bây giờ là 1)

Ta chỉ còn chứng minh:

$\sum_{i=0}^{n}C^i_n.(-1)^nf(x-i)=n!.a$

Để ý rằng:
$\begin{align*}
&f(x)\\
&\Delta f(x)=f(x)-f(x-1)\\
&\Delta^2 f(x)=\Delta(\Delta f(x))=\left(f(x)-f(x-1)\right)-\left(f(x-1)-f(x-2)\right)=f(x)-2f(x-1)+f(x-2)\\
&\dotsc
\end{align*}$
Vì thế ta sẽ chứng minh rằng vế trái của đẳng thức sẽ bằng với $\Delta^n(f(x))$. (1)

Chứng minh bằng quy nạp:
n=1 đúng, giả sử (1) đúng với $n=k$ thì:

$\Delta^k(f(x))=\sum_{i=0}^{k}C^i_k.(-1)^if(x-i)$

Với n=k+1 thì:
$\Delta^{k+1}(f(x))=\Delta(\Delta^k(f(x)))=\Delta^k(f(x))-\Delta^k(f(x-1))\\=\sum_{i=0}^{k}C^i_k.(-1)^if(x-i)-\sum_{i=0}^{k}C^i_k.(-1)^if(x-1-i) \\=\sum_{i=0}^{k}C^i_k.(-1)^if(x-i)-\sum_{i=1}^{k}C^{i-1}_k.(-1)^{i-1}f(x-i)-(-1)^kf(x-k-1)\\=f(x)+\sum_{i=1}^{k}((-1)^i.(C^i_k+C^{i-1}_k)f(x-i))+(-1)^{k+1}f(x-k-1)\\=\sum_{i=0}^{k+1}C^i_{k+1}.(-1)^if(x-i) (dpcm)$

Tiếp theo ta chứng minh $\Delta^kf(x)$ là một đa thức bậc (n-k) ( với n là bậc của f(x) ) và hệ số cao nhất là $n(n-1)\cdots(n-k+1)a$

Với n=1 Đúng.

Giả sử đúng với n=k, ta chứng minh đúng với n=k+1

$\Delta^{k+1}f(x)=(n(n-1)\cdots(n-k+1)ax^{n-k}+...)-(n(n-1)\cdots(n-k+1)a(x-1)^{n-k})=n(n-1)\cdots(n-k+1)a(x^{n-k}-(x-1)^{n-k}+..)=n(n-1)\cdots(n-k+1)(n-k)a(x^{n-k-1}+..)$

Ta có điều phải chứng minh.

Ta thấy đẳng thức này rất quen thuộc nhưng lại ít được quan tâm.

Sau đây ta sẽ xét ứng dụng của nó

 Tìm tất các đa thức hệ số nguyên f sao cho $n|m \Rightarrow f(n)|f(m)$

Giải: 

Giả sử g(x) là một đa thức thỏa mãn điều kiện đề bài.

Đặt deg g(x)=D. Hệ số ứng với số mũ cao nhất của g(x) là a.

Ta thấy n|rn, $\forall r \in Z$ nên g(n)|g(rn)$\forall r \in Z$ (do đề bài)

$\Rightarrow g(n)|\sum_{i=0}^{D}C^i_D(-1)^ig((D-i)n)=D!an^D$ ( theo đẳng thức vừa đề cập).

$\Rightarrow g(n) |(D!.an^D-D!g(n))=h(n)$ (1)

Ta thấy degh(x) <D=deg g(x) nên với mọi n tồn tại $n_o$ sao cho:$|h(n)| <|g(n)|( \forall n>n_0)$

Kết hợp với (1) suy ra $h(n)=0 \forall n>n_o$ vậy$D!.a.n^D=D!.g(n) \Rightarrow g(n)=an^D$

Vậy tất cả các đa thức thỏa mãn đề bài đều có dang $f(x)=ax^D$ với a nguyên, D là số tự nhiên.

ngoài ra ta có thể thấy những công thức này cũng là hệ quả của đẳng thức trên.