# How many 7-digit numbers are there in which every digit is a 6 or a 7 and no two 7s are adjacent?

*print*Print*list*Cite

Hello!

Let's denote

`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` .

Also, denote

`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_1=2,` `b_1=1.`

`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**.