How many $n-$digit number that contain only digits $ 1,2,3,4,5,6$ How many $n- $digit numbers can be formed from the digits $1,2,3,4,5$ and 6, which contains the  numbers $1$ and $2$ as neighbours.
Let $p_n$ be the number of n-digit numbers which consist only of the digits 1,2,3,4,5,6, which contains the  numbers $1$ and $2$ as neighbours.
$$p_{n+1}=p_{n}+(?)$$
Now How to find  $(?)$ 
 A: Denote by $a_n$ the number of words of length $n$ which do not contain $12$ or $21$, and do not end with one of $1$ or $2$.
Denote by $b_n$ the number of words of length $n$ which do not contain $12$ or $21$, and do  end with one of $1$ or $2$.
Denote by $c_n$ the number of words of length $n$ which do contain $12$ or $21$.
Then $a_1=4$, $b_1=2$, $c_1=0$, and we have the following recursion scheme:
$$\eqalign{a_{n+1}&=4a_n+4b_n\cr b_{n+1}&=2a_n+b_n\cr c_{n+1}&=6c_n+b_n\ .\cr}\tag{1}$$
It is possible to eliminate the $a$'s and the $b$'s from these equations, and the following difference equation for the $c_n$ results:
$$c_{n+3}-11 c_{n+2}+26 c_{n+1}+24 c_n=0\qquad(n\geq1)\ .\tag{2}$$
This equation can be solved using the "Master Theorem". The missing initial values $c_2$ and $c_3$ have to be computed by hand from $(1)$. The final result is: 
$$c_n={\rm round}\left(6^n-\left({1\over2}+{7\over 2\sqrt{41}}\right)\left({5+\sqrt{41}\over2}\right)^n\right)\qquad(n\geq1)\ .$$
A: Start by making $n$-symbol words from the five symbols $[12],3,4,5,6$; there are $\binom{n+4}{4}$ ways to do this (use "stars and bars".)  For each such word, you have two possible orderings of the $1$ and $2$.  So
$$p_n=2\binom{n+4}{4}.$$
And $p_{n+1}-p_n=2\binom{n+5}{4}-2\binom{n+4}{4}=2\binom{n+4}{3}$.
A: The number of digits-numbers that we can form with the digists such that the digits $1,2$ are neighbours:$10\cdot 4!$. We can have $10$ possibilities($u,z,y,x$ are digits):$1)$  $$12xyzu$$ 
$2)$
$$21xyzu$$
$3)$
$$x12yzu$$
$4)$
$$x21yzu$$
$5)$
$$xy12zu$$
$6)$
$$xy21zu$$
$7)$
$$xyz12u$$
$8)$
$$xyz21u$$
$9)$
$$xyzu12$$
$10)$
$$xyzu21$$
The permutations for every possibilities of digits $x,y,z,u$ are$4!$ There are $10$ cases therefore we have $10\cdot 4!$ numbers.
