Key idea: (Passage: an counts n-digit numbers made of 0/1 with no two consecutive 0s; bn of them end in 1 and cn end in 0.) Build the numbers by adding one digit at a time.
- You can append a 1 to any valid (n−1)-digit number, so bn=an−1.
- You can append a 0 only after a 1, so cn=bn−1=an−2.
- So an=bn+cn=an−1+an−2, a Fibonacci-type recurrence. (A) is true.
- Checking the others:
- (B): c17=a15=a14+a13=c16+c15, so the "=" is false.
- (C): b17=a16=b16+c16, so the "=" is false.
- (D): c17+b16=a15+a15=2a15=a17. False.
Answer: (A)