[Thgx0312555]

ข้อความเดิมเขียนโดยคุณ PP_nine

กำหนดลำดับ $u_n$ ซึ่งมีความสัมพันธ์เวียนเกิด $u_{n+1}=pu_{n}+u_{n-1}$ เมื่อ $n \ge 1$

โดยที่ $p \in \mathbb{Z}-\{ 0 \}$ และ $u_0=0,\ u_1=1$

จงพิสูจน์ว่า ถ้า $u_n^2 | u_{kn}$ สำหรับบางจำนวนเต็มบวก $k$ แล้ว $u_n | k$

ข้อนี้สวยมากครับ

solution

Case $n=0$ is trivial
ถ้า $n \ge 1$

สมมติว่า $u_{n-1}=a,u_n=b$
โดย induction สามารถพิสูจน์ว่า $u_{n+q}=au_q+bu_{q+1}$
ดังนั้นเมื่อ $m \ge 2$
$u_{mn-1}=au_{(m-1)n-1}+bu_{(m-1)n}$
$u_{mn}=au_{(m-1)n}+bu_{(m-1)n+1}=au_{(m-1)n}+b(u_{(m-1)n-1}+pu_{(m-1)n})=bu_{(m-1)n-1}+(a+pb)u_{(m-1)n}$

ให้ $x_m=u_{mn-1}, y_m=u_{mn}$
ดังนั้น
$x_m=ax_{m-1}+by_{m-1}$
$y_m=bx_{m-1}+(a+pb)y_{m-1}$

แก้สมการเวียนเกิดสมการแรกออกมาจะได้ $x_m=b(y_{m-1}+y_{m-2}+\cdots+y_1)+a^m$

$y_m=b(b(y_{m-2}+y_{m-3}+\cdots+y_1)+a^m)+(a+pb)y_{m-1}$

สามารถพิสูจน์โดย induction ว่า $b \ | \ y^m$ ดังนั้นให้ $z_m=\dfrac{y^m}{b}$

$z_m=b(y_{m-1}+y_{m-2}+\cdots+y_1)+a^m+az_{m-1}+bpz_{m-1}$
$z_m \equiv a^m+az_{m-1} \pmod b$

$z_m \equiv ma^m \pmod b$

ดังนั้นถ้า $u_n^2 \ | \ u_{kn}$ นั่นคือ $b^2 \ | \ y_k$, $b \ | \ z_k$ จะได้ $b \ | \ ka^k$
เห็นได้ไม่ยากว่า $\gcd(a,b)=1$
จะได้ $b \ | \ k$ นั่นคือ $u_n \ | \ k$ ตามต้องการครับ