How many 7-digit numbers are there in which every digit is a 6 or a 7 and no two 7s are adjacent?
`a_n` = the quantity of n-digit numbers in which every digit is a 6 or a 7 and no two 7s are adjacent.
We are interested in `a_7` .
`b_n` = the quantity of n-digit numbers in which every digit is a 6 or a 7 and no two 7s are adjacent AND the last digit is 6.
It is obvious that `a_1=2` (6 and 7) and `b_1=1` (6).
Now we want to move from n to n+1.
First, `a_(n+1) = a_n + b_n.`
Actually, if (n+1)-th digit is 6, then any of `a_n` combinations may occupy first n digits. If (n+1)-th digit is 7, only `b_n` combinations may.
Second, `b_(n+1) = a_n.` Any of `a_n` combinations may occupy the first n digits and the last must be 6.
So, `a_(n+2)=a_(n+1)+b_(n+1)=a_(n+1)+a_n` — good old Fibonacci numbers.
Now we can compute `a_n` for any `n`:
`a_2 = a_1+b_1=3.`
`a_3 = a_2+a_1=5.`
`a_4 = a_3+a_2=8.`
`a_5 = a_4+a_3=13.`
`a_6 = a_5+a_4=21.`
`a_7 = a_6+a_5=34.`
The answer is 34.