Thách thức !

[T&S]

Dãy Fibonaci có tích chất:
u(n)=u(n-1)+u(n-2)
Một số phần tử của dãy:

1 1 2 3 5 8 13 21 34 55 89 144 ...


mình đang nghi ngờ: u(n*m) chia hết cho u(n)*u(m)
nhưng không thể chứng minh được nó đúng hay sai. Ai có thể giúp mình?

[myhanh]

n=2->u(2)=2
m=3->u(3)=3
=>u(2)*u(3)=2*3=6.
n*m=2*3=6->u(6)=13.
Vì 13 không chia hết cho 6 nên u(6) không chia hết cho u(2)*u(3).
Kết luận dành cho T&S

[meohoang]

Theo pt sai phân của dãy mà luận thì :
u(n) = ax1(n) + bx2(n)
=>
u(n*m) = ax1(m*n) + bx2(m*n)
u(m)*u(n) = [ ax1(m) + bx2(m) ] * [ ax1(n) + bx2(n) ]
= u(n*m) + ax1(m)*bx2(n) + bx2(m)*ax1(n) > u(m*n) =>>> ???

[T&S]

* Gửi myhanh: u(1)=1, u(2)=1,u(3)=2,u(6)=8
nên u(6) vẫn chia hết cho u(2)*u(3)
* Gửi meohoang: tui hổng biết pt sai phân là gì hết, nên hòan tòan hổng hiểu, nói rõ hơn 1 chút được ko?
* Nhận định mới: tui đã thấy rằng(suy đóan này rộng hơn suy đóan trước):

Nếu n chia hết cho m thì u(n) chia hết cho u(m)

VD: nếu 8 chia hết cho 4 thì u(8) chia hết cho u(4)

Và đương nhiên là...cũng chưa chứng minh được.

[T&S]

Nếu suy đóan mình đúng, thì ta có thể nảy ra bài tóan kiểm tra tính nguyên tố của các phần tử trên dãy Fibonaci. Thay vì kiểm tra giá trị phần tử (số rất lớn), thì ta chỉ cần kiểm tra chỉ số của nó (số nhỏ hơn nhiều), bài tóan đơn giản hơn.

[myhanh]

myhanh xin nói thêm về phương trình sai phân:
u(n)=u(n-1)+u(n-2)
phương trình sai phân có dạng
u(n)=a pow(x1,n)+b pow(x2,n).
Trong đó x1,x2 là nghiệm của phương trình
x^2=x+1
=>x1=(1+sqrt(5))/2 và x2=(1-sqrt(5))/2.
Từ điều kiện u(0)=1 và u(1)=1 ta tính được hai hệ số a và b.
Tóm lại ta có u(n)=(1/sqrt(5))(pow((1+sqrt(5))/2,n+1)-pow((1-sqrt(5))/2,n+1)).

[meohoang]

Đúng vậy, đó chính là công thức tổng quát của dãy Fibonaci , và từ đó mà tính được ( một cách chính xác ) kết luận ban đấu là sai . Tức là u(m*n) không chia hết cho u(m)*u(n) !

[T&S]

Dzậy kết luận thứ 2 là sai hay là đúng?

[meohoang]

Đúng ! Meohoang không chứng minh được nhận xét đó , nhưng đã có người chứng minh được . Cách đây khoảng ... mấy chục năm , một thí sinh người Liên Xô trong kì thi Vô địch toán quốc tế đã giải bài toán : đánh dấu tất cả các phần tử là số nguyên tố của dãy Fibonaci ( đề bài chỉ cho trong phạm vi 10(8)- 1 số đầu tiên . Người này tên là Ba_lat_xơ ! Anh ta đoạt chức vô địch tuyệt đối và trở thành huyền thoại của cuộc thi này .
Thứ cho năm tạpmeohoang kiến thức còn hạn hẹp , không nhớ nổi cách chứng minh . Bạn có thể tìm đọc trong quyển "Tuyển tập 30 chí Toán học& tuổi trẻ" . !

[T&S]

Nhưng nếu kết luận thứ 2 là đúng, thì ta chũng suy ra là kết luận đầu tiên cũng đúng chứ?
Vì nếu u(m) chia hết cho u(n) khi m chia hết cho n thì u(m*n) chia hết cho u(n) (do m*n chia hết cho n)=>u(m*n) chia hết cho u(n)*u(m).

[meohoang]

Originally posted by T&S@May 13 2005, 11:47 AM
Nếu suy đóan mình đúng, thì ta có thể nảy ra bài tóan kiểm tra tính nguyên tố của các phần tử trên dãy Fibonaci. Thay vì kiểm tra giá trị phần tử (số rất lớn), thì ta chỉ cần kiểm tra chỉ số của nó (số nhỏ hơn nhiều), bài tóan đơn giản hơn.
Meohoang nói đúng là kết luận này . Còn các kết luận kia thì meohoang đã chứng minh là sai hết rồi !

[chinhlh]

[Vì nếu u(m) chia hết cho u(n) khi m chia hết cho n thì u(m*n) chia hết cho u(n) (do m*n chia hết cho n)=>u(m*n) chia hết cho u(n)*u(m).]

T&S lập luận không chính xác rồi. 20 chia hết cho 10, và cũng chia hết cho 5, nhưng không chia hết cho 50. Nếu có u(n) và u(m) nguyên tố cùng nhau thì được.