จงหาความสัมพันธ์เวียนเกิดและเงื่อนไขเริ่มต้นของจำนวนบิตสตริงที่มีความยาว n โดยที่ไม่มีเลข 0 สามตัวอยู่ติดกัน (000)
โดยที่ n น้อยกว่าหรือเท่ากับ 1 และหาจำนวนบิตสตริงที่มีความ 10 โดยไม่มี 000 ติดกัน

Sol กำหนดให้ a_n  เป็นจำนวนบิตสตริงที่มีความยาว n โดยไม่มี 000 ติดกัน

จะได้   a₁ =  2      -> 0,1
          a₂ =  4     -> 00, 01 , 10, 11
          a₃ =  7     -> 001, 010, 011, 010 ,011, 100, 101, 110, 111 - {000}

พิจารณา a_n โดยใช้หลักการบวก เราแบ่งเป็น 2 กรณีตตามหลักที่ขึ้นต้น ดังนั้น จำนวนบิตสตริงที่มีความยาว n
โดยไม่มีเลขศุนย์สามตัวอยู่ติดกัน เท่ากับ  "เลข0อยู่ด้านหน้าสุด" และ "เลข1อยู่ด้านหน้าสุด" ซึ่งไม่มีเลข000

ข้อนี้จะเริ่มอย่างไรครับ ช่วยแนะหน่อยครับ