10-digit numbers with constraints 
How many 10-digit numbers can be made by using the digits {5,6,7} (all of them) and with the additional constraints that no two consecutive digits must be the same and also that the first and last digits of the number must be the same?

I am trying to find a solution by using combinatorics. I start from the 1st leftmost digit, which can have any value from {5,6,7} (3 possibilities). 
Then we move to the 2nd digit, which can have 2 values (since it can't be the same with the 1st) and so on, and for the last digit we only have 1 option. But this is not correct, because for the 9th digit we have the restriction that it must be different from the 8th and also different from the 10th, which, in turn, is equal to the 1st. 
I don't know how to express this.
I therefore tried to find a recursive relation. 
I found that the general relation is $a(n) = 2*a(n-1)$ if n odd and $2*a(n-1) + 6$ if n is even. 
For n=4, we have 6 such numbers (4-digit numbers, but with the given restrictions). Then if we add one more digit to the right, we remove the rightmost (4th) digit, which had to be the same with the first, and now for the 3rd digit we have 2 options instead of 1 (we can also add the options that were rejected because they were neighboring with the 4th digit). So in total we now have $2 x 6 = 12$ options.
Therefore, $a(4)=6$ and $a(5)=12$.
I don't understand, however, where this $+6$ (in the recursive relation) comes from!
By the way, the correct answer is 510.
Many thanks in anticipation.

I have another solution. We call a number satisfying the condition of the problem "accepted". Let $a(n)$ denote the number of accepted numbers with $n$ digits. Imagine an accepted number with $n-2$ digits and put two empty places at the left side of the number with $n-2$ digits. You can easily make two different accepted numbers with $n$ digits. To make this claim clear, assume $1,3,...,1$ is an accepted number with $n-2$ digits, we can build two $n$-digit numbers as below: $$1,2,1,3,...,1$$ $$1,3,1,3,...,1$$
Now, assume we have an accepted number with $n-1$ digits. We can make an accepted number with $n$ digits from this number. For example, assume $1,3,...,1$ is such number. we can write:$$1,2,3,...,1$$
Just notice that we added $1$ to the left side and the first $1$ in$1,3,...,1$ changed into $2$.
Now, assume $n$ is even. An accepted number can be made from $1,2,1,2,1,2,...,1,2$ with $n-2$ digit, as below:$$2,3,1,2,...,1,2$$
It is easy to understand that $1,2,1,2,1,2,...,1,2$ doesn't belong to the set of accepted numbers with $n-2$ digits.
If $n$ is odd, the same goes for it, consider $1,2,1,2,...,1,2$ with $n-1$ digits. It's possible to make an accepted number with $n$ digits from this as below:$$2,3,2, 1,2,1,2,...,1,2$$
In each situation there are 6 accepted numbers (why?) with $n$ digits which can't be made from accepted numbers with $n-1$ or $n-2$ digits. So, we will get $a(n)=a(n-1)+2a(n-2)+6$.
To be done, one should check two statements below:


*

*A $n$-digit accepted number made from $n-2$-digit accepted numbers doesn't coincide with any $n$-digit accepted numbers made from  $n-1$-digit accepted numbers and vice versa.

*Each $n$-digit accepted number can be obtained through either $n-2$-digit accepted numbers, $n-1$-digit accepted numbers or those six numbers. 


Note: What I wrote implies the formula you mentioned.
