How many 10-digit sequence are there?

Let $T(n)$ be the number of such $n$ -digit sequence.

Let $A(n)$ be the number of such $n$ -digit sequence that end in either 1 or 4.

Let $B(n)$ be the number of such $n$ -digit sequence that end in either 2 or 3.

Now $T(n)=A(n)+B(n)$ .

Note that $A(n+1)=B(n)$ and $B(n+1)=B(n)+A(n)=B(n)+B(n-1)$ . Since $A(1)=2, B(1)=2$ , we can construct the following table, using the mentioned recursive relation, and obtain the answer.

For the bonus question: $\displaystyle \lim_{n \to \infty} \frac{T(n+1)}{T(n)} = \lim_{n \to \infty} \frac{A(n+1)+B(n+1)}{A(n)+B(n)} = \lim_{n \to \infty} \frac{B(n)+B(n+1)}{B(n-1)+B(n)} = \lim_{n \to \infty} \frac{B(n+2)}{B(n+1)} =...= \phi \approx 1.61803$

You can also figure this using a tree diagram. For the numbers starting 1 and 4, there is only one possibility for the result. You will find out for every digit, it goes in a Fibonacci sequence, so for the case of the first digit being 1 and 4, the sequence goes 1 1 2 3 5 8 13 21 34 55, 55 is the number of possible outcomes for the number starting with 1, and 55 is the number of possible outcomes for the number starting with 4. For 2 and 3, since the number of options for the second number is 2, we skip the first number of the Fibonacci sequence, thus leaving us with the 11th number of the Fibonacci sequence, 89 for the number of possibilities for 2, and another 89 possibilities with 3.

Therefore, the number of results is (55+89)*2=288

We can work out the number of sequences ending with a specific digit by adding together the number of sequences up to the previous number which ends with a number adjacent to the desired number.

For example, by using the tree diagram below (considering only the sequences starting with a 1), we can see that the number of 6-digit sequences ending in 2 $(5)$ is equal to the number of 5-digit sequences ending in 1 $(2)$ added to the number of sequences ending in 3 $(3)$ : This is applicable down to just 2-digit sequences: the number of 2-digit sequences ending in 3 $(2)$ is equal to the number of 1-digit sequences ending in either 2 $(1)$ , or 4 $(1)$ . In this case, these two sequences are $2,3$ and $4,3$ respectively.

With this information, starting with the 4 possible 1-digit sequences, we can work out the number of sequences of successive lengths ending in each digit: And now we can work out the total number of 10-digit sequences using $55+89+89+55=\boxed{288}$

For the bonus question: with the table above, we can see the Fibonacci sequence emerging as the length of the sequence increases. Because the ratio between successive numbers in the Fibonaccio sequence tends towards the golden ratio $(\phi)$ , we can see that, as the above sequence increases in length:

$T(n+1)_1+T(n+1)_2+T(n+1)_3+T(n+1)_4=\phi T(n)_1+\phi T(n)_2+\phi T(n)_3+\phi T(n)_4$

$T(n+1)_1+T(n+1)_2+T(n+1)_3+T(n+1)_4=\phi (T(n)_1+T(n)_2+T(n)_3+T(n)_4)$

$T(n+1)=\phi T(n)$

$\frac{T(n+1)}{T(n)}=\phi \approx 1.618$

The $1$ -digit possibilities are $1$ , $2$ , $3$ , and $4$ ; for a total of $4$ different sequences.

For $2$ -digit possibilities, the first digit can be $1$ , $2$ , $3$ , or $4$ . If the first digit is $1$ , then the second digit must be $2$ . If the first digit is $2$ , the the second digit must be $1$ or $3$ . If the first digit is $3$ , then the second digit must be $2$ or $4$ . And if the first digit is $4$ , then the second digit must be $3$ . The possible sequences are $12$ , $21$ , $23$ , $32$ , $34$ , and $43$ - $1$ starting with $1$ , $2$ starting with $2$ , $2$ starting with $3$ , and $1$ starting with $4$ - for a total of $1 + 2 + 2 + 1 = 6$ different sequences for $2$ digits.

For 3-digit possibilities, the first digit can be $1$ , $2$ , $3$ , or $4$ . If the first digit is $1$ , then the second digit must be $2$ , and from above we know that there are $2$ $2$ -digit possibilities that start with $2$ , so there are $2$ $3$ -digit possibilities that start with $1$ . If the first digit is $2$ , then the second digit must be $1$ or $3$ , and from above we know that there is $1$ $2$ -digit possibility that starts with $1$ and $2$ $2$ -digit possibilities that start with $3$ , for a total of $1 + 2 = 3$ $3$ -digit possibilities that start with $2$ . If the first digit is $3$ , then the second digit must be $2$ or $4$ , and from above we know that there are $2$ $2$ -digit possibilities that start with $2$ and $1$ $2$ -digit possibility that starts with $4$ , for a total of $2 + 1 = 3$ $3$ -digit possibilities that start with $2$ . If the first digit is $4$ , then the second digit must be $3$ , and from above we know that there are $2$ $2$ -digit possibilities that start with $3$ , so there are $2$ $3$ -digit possibilities that start with $4$ . There are then a total of $2 + 3 + 3 + 2 = 10$ different sequences for $3$ digits.

Now we can see a recursive pattern. Let $a_n$ be the number of $n$ -digit possibilities that start with $1$ or $4$ , $b_n$ be the number of $n$ -digit possibilities that start with $2$ or $3$ , and $t_n$ be the total number of $n$ -digit possibilities. Then using the above arguments, $a_n = b_{n - 1}$ , $b_n = a_{n - 1} + b_{n - 1}$ , and $t_n = 2(a_n + b_n)$ . Then substituting $a_n = b_{n - 1}$ and $b_n = a_{n - 1} + b_{n - 1}$ , we have $t_n = 2(b_{n - 1} + a_{n - 1} + b_{n - 1})$ , and substituting $b_{n - 1} = a_{n - 2} + b_{n - 2}$ , we have $t_n = 2(a_{n - 2} + b_{n - 2} + a_{n - 1} + b_{n - 1})$ , and since $t_{n - 1} = 2(a_{n - 1} + b_{n - 1})$ and $t_{n - 2} = 2(a_{n - 2} + b_{n - 2})$ , we have $t_n = t_{n - 2} + t_{n - 1}$ .

From above we know that $t_1 = 4$ and $t_2 = 6$ , and so using $t_n = t_{n - 2} + t_{n - 1}$ we can find the first $10$ terms of the sequence to be $4$ , $6$ , $10$ , $16$ , $26$ , $42$ , $68$ , $110$ , $178$ , and $288$ , which means $t_{10} = \boxed{288}$ .

Bonus: Since $t_n = t_{n - 2} + t_{n - 1}$ , it has the same recursive pattern as the Fibonacci sequence, and so $\lim_{n \to \infty} \frac{t_{n + 1}}{t_n} = \phi \approx 1.618$ .

C#

using System;

namespace ConsoleApp1
{
    class Program
    {
        static int Count = 0;
        static long Max = (long)Math.Pow(10,9);

        static void Expand(ref long _value)
        {   if (_value > Max)
                Console.WriteLine($"[{++Count}]\t{_value}");    // branch finished
            else
            {   long _tmp;
                short _lastDigit = (short)(_value % 10);
                long _root = 10 * _value + _lastDigit;
                if (_lastDigit > 1) { _tmp = _root - 1; Expand(ref _tmp); }
                if (_lastDigit < 4) { _tmp = _root + 1; Expand(ref _tmp); }
            }
        }


        static void Main(string[] args)
        {   for(long k = 1; k<=4; k++) Expand(ref k);
            Console.WriteLine($"Count: {Count}");
        }
    }
}

Noting that any number must go even, odd, even, or vise versa. We can treat 1 and 4 as end points, E, and 2 and 3 as middle points, M. (Where 2 E's cannot be next to each other). (Note we are now counting precisely half of total, as we can choose the first digit to be odd or even.)

Let F(n) be the number of combinations of E and M. For n>2,

F(n)= (first digit E, 2nd digit M) F(n-2) + (first digit M) F(n-1)

F(1)=2 (E, M)

F(2)=3 (EM, ME, MM)

We can deduce that F(n) = (n+2)th Fibonacci number, f(n+2). So F(10)=144. So T(10)=288.

Extra: lim(n -> infinity) T(n+1)/T(n) = lim(n -> infinity) f(n+3) / f(n+2) = phi