อ้างอิง:
ข้อความเดิมเขียนโดยคุณ warut_suk
61. พิจารณาลำดับที่นิยามโดย $x_{n+1}=2x_n+3y_n, y_{n+1}=x_n+2y_n$ โดยที่ $x_1=2,y_1=1$ จงแสดงว่าสำหรับทุก $n\geq 1$ มีจำนวนเต็มบวก $K_n$ ซึ่ง $x_{2n+1}=2(K_n^2+(K_n+1)^2)$
|
โจทย์ข้อนี้ดีอย่าง คือสามารถใช้กำลังเข้าหักหาญเอาคำตอบได้ ไม่เหมือนกับข้อ 59-60 แต่โจทย์ที่ brute force ได้ก็มีข้อเสียคือ เรามักไม่สนใจว่าจะทำได้หรือไม่ แต่ไปสนใจว่าจะหาวิธีทำสวยๆได้ยังไง Carl Pomerance (number theorist ที่มีชื่อเสียงมากที่สุดคนนึงในยุคปัจจุบัน) เคยเขียนเล่าให้ฟังว่า เขาเคยได้รับโจทย์ในการแข่งขันข้อนึง เป็นโจทย์ให้แยกตัวประกอบจำนวนเต็ม ซึ่งถ้าใช้ trial division ธรรมดาก็คงทำได้แล้วล่ะ แต่ในเมื่อโจทย์ออกมาในลักษณะอย่างนี้ เขาคิดว่ามันต้องมีวิธีฉลาดๆในการทำแน่ จึงเสียเวลามองหาวิธีอยู่นาน จนกระทั่งเวลาใกล้หมด ก็ยังทำไม่ได้ เลยตัดสินใจกลับมาใช้ trial division แต่ก็สายเกินไปแล้ว...
สำหรับวิธีใช้กำลังที่ผมว่านั้น คือทำตรงๆดังนี้ครับ
จากที่โจทย์ให้ เราจะได้ว่า $$x_{n+2} = 2x_{n+1} +3y_{n+1} = 2x_{n+1} +3(x_n+2y_n) = 2x_{n+1} +3x_n +6y_n$$ เมื่อรวมกับ $x_{n+1}=2x_n+3y_n$ เราจึงได้ว่า $$x_{n+2} = 4x_{n+1} -x_n$$ โดยที่ $x_1=2$ และ $x_2=7$
แก้ difference equation อันนี้ เราได้ $$x_n= \frac12 (a^n + a^{-n}) $$ เมื่อ $a=2+\sqrt3$
จาก $$x_{2n+1}= 2(K_n^2+(K_n+1)^2) = (2K_n+1)^2+1$$ และ $$x_{2n+1}-1 = \frac12 (a^{2n+1} + a^{-(2n+1)} - 2) = \frac12 (a^{n+1/2} - a^{-(n+1/2)} )^2$$ ดังนั้น $$K_n= \frac{(1+\sqrt3)}{4} a^n + \frac{(1-\sqrt3)}{4} a^{-n} -\frac12 $$ เพราะ $\sqrt a= \dfrac{1+\sqrt3}{\sqrt2} $
คำนวณย้อนกลับหา linear recurrence relation เราจะพบว่า $$K_{n+2} =4K_{n+1} -K_n +1$$ โดยที่ $K_0=0$ และ $K_1=2$
โดย induction เรารู้ว่า $K_{n+1}>K_n$ ดังนั้น $\{K_n\}_{n\ge1}$ จึงเป็นลำดับของจำนวนเต็มบวก ตามที่โจทย์ต้องการครับ
สำหรับวิธีทำเจ๋งๆของข้อนี้ หรือวิธีทำของข้อที่เหลือ (ข้อ 64. ดูท่าทางน่าสนใจมาก) คงต้องปล่อยให้เป็นหน้าที่ของคนอื่นๆแล้วล่ะครับ
