[★★★☆☆]

โจทย์ทำนองนี้เคยเป็นข้อสอบเข้ามหาวิทยาลัย ในช่วงประมาณไม่เกิน 10 ปีที่ผ่านมา ผมจำไม่ได้ครับว่าเป็นของ พ.ศ.ไหน ถ้าสนใจลองหาดู

ส่วนวิธีการมองปัญหาให้อยู่ในรูปความสัมพันธ์เวียนเกิด (recurrence relation) เป็นสิ่งที่นักคณิตศาสตร์ใช้แก้ปัญหาที่ถ้านั่งทำซ้ำ ๆ ต่อไปแล้วจะยากขึ้นเรื่อย ๆ ครับ

เช่น สมมติว่ามีลำดับ
2, 5, 8, 11, ...

ถ้าเราหาสูตรของพจน์ทั่วไปก็จะได้เป็น $a_n = 3n-1$ เมื่อ n เป็นจำนวนเต็มบวกใด ๆ
แต่ถ้ามองในแง่ความสัมพันธ์เวียนเกิด เราจะพบว่า พจน์ที่อยู่ถัดไปจะเท่ากับพจน์ที่อยู่ก่อนหน้าตัวมัน บวกด้วย 3 เสมอ
$a_2 = a_1 + 3$
$a_3 = a_2 + 3$ ...

ดังนั้นจึงอาจจะเขียนในแง่ความสัมพันธ์เวียนเกิดได้เป็น $a_n = a_{n-1} + 3$ เมื่อ $n \ge 2$ และ $a_1 = 2$

หรือลำดับ
2, 4, 8, 16, ...
ถ้าเราหาสูตรของพจน์ทั่วไปก็จะได้เป็น $a_n = 2^n$ เมื่อ n เป็นจำนวนเต็มบวกใด ๆ
แต่ถ้ามองในแง่ความสัมพันธ์เวียนเกิด เราจะพบว่า พจน์ที่อยู่ถัดไปจะเท่ากับพจน์ที่อยู่ก่อนหน้าตัวมัน คูณด้วย 2 เสมอ
$a_2 = 2a_1$
$a_3 = 2a_2 $ ...

ดังนั้นจึงอาจจะเขียนในแง่ความสัมพันธ์เวียนเกิดได้เป็น $a_n = 2a_{n-1}$ เมื่อ $n \ge 2$ และ $a_1 = 2$

หรือลำดับ Fibonacci ที่โด่งดังคือ
1, 1, 2, 3, 5, 8, 13, 21, ...
จะเขียนในแง่ความสัมพันธ์เวียนเกิดได้เป็น $a_n = a_{n-1} + a_{n-2}$ เมื่อ $n \ge 3$ และ $a_1 = a_2 = 1$

หรือถ้าถามว่าจะมีจำนวนในระบบฐานสองที่มีความยาว 8 ทั้งหมดกี่จำนวนซึ่งไม่มีศูนย์สองตัวใด ๆ อยู่ติดกัน

เช่น 01110111 ใช้ได้ แต่ในขณะที่ 10011111 แบบนี้ใช้ไม่ได้ ถ้านับโดยตรงก็จะทำได้เฉพาะเมื่อมีความยาวน้อย ๆ
เช่น
n = 1 จะมี 2 จำนวนคือ 0 กับ 1
n = 2 จะมี 3 จำนวนคือ 01, 10, 11
n = 3 จะมี 5 จำนวนคือ 010, 011, 110, 101, 111,

แต่ถ้ายาวมาก ๆ และสามารถหาออกมาเป็นความสัมพันธ์เวียนเกิด ก็จะทำให้คำนวณได้ง่ายขึ้น (ในที่นี้จะได้ $a_n = a_{n-1} + a_{n-2}$ เมื่อ $n \ge 3$ และ $a_1 = 2, a_2 = 3$ ซึ่งเป็นความสัมพันธ์ทำนองเดียวกันกับลำดับ Fibonacci นั่นเองครับ)