4
$\begingroup$

How do I find a recursion formula to solve the following question:

In how many sequences of length $n$, with elements from $\{{0,1,2,3,4}\}$, the difference between every 2 adjacent elements is $1$ or $-1$?

I've been trying to solve the problem for the last 5 hours maybe, I'm sure that I'm missing something..

This is a problem in combinatorics, and the solution must be by finding a recursion formula for the problem.

best solution I've come so far is that if we say that $a_n$ is the solution to the question, so let's count how many sequences of size $n-1$ there are that meet the requirement, and we complete the first element to make it a sequence of $n$ elements. so for $n-1$ there $a_{n-1}$ sequences, and for each sequence we have $2$ options to choose the first element (one option is to take a plus $1$ number from the number that start the $n-1$ sequence, and the other option to to take a minus $1$ number from the number that start the $n-1$ sequence), only problem as you figured out is that if the $n-1$ sequnce starts with $0$ or $4$ there is only $1$ option left for the first element in the sequnce.. so $a_n=2a_{n-1}$ won't work.

I think that the solution may involve using $2$ or maybe $3$ recursion formulas.

Hope I was clear enough.

3 Answers 3

4

Let $A_n$ be the number of sequences ending at $0$ or $4$, and $B_n$ the number of sequences ending at $1$ or $3$, and $C_n$ the number of sequences ending at $2$. Then

$ A_{n+1} = B_n\\ B_{n+1} = A_n + 2C_n\\ C_{n+1} = B_n. $

We conclude immediately that $A_{n+1} = C_{n+1} = B_n$ for all $n\ge 1$, and so

$B_{n+2} = 3 A_{n+1} = 3 B_n$

also for $n\ge 1$. Given $A_1 = B_1 = 2$ and $C_1 = 1$, you can take it from here.

  • 0
    Alright, that's exactly the solution I've been looking for, and works great.. I always tried to solve it with 2 formulas, and I knew I'm missing something. Thanks!2012-09-07
3

Consider the column vector $V(n) = (v_0(n), v_1(n), v_2(n),v_3(n), v_4(n))^T$, where $V_i(n)$ is the number of such sequences starting with $i$. This satisfies the equation $V(n+1) = A V(n)$ where $A$ is a certain $5 \times 5$ matrix. So $V(n) = A^{n-1} V(1)$. Eigenvalues and eigenvectors will be useful...

  • 0
    You can get some simplification by symmetry: $v_0 = v_4$, $v_1 = v_3$. Moreover, if you look at two steps you can decouple $v_1$ from $v_0$ and $v_2$: $ v_1(n+2) = 3 v_1(n)$, $v_0(n+2) = v_0(n) + v_2(n)$, $v_2(n+2) = 2 v_0(n) + 2 v_2(n)$.2012-09-07
2

Let $a_n$ be the number of such sequences ending in 0 or 4, $b_n$ the number of such sequences ending in 1 or 3, $c_n$ the number of those ending in 2. The recursion is $a_{n+1}=b_n$, $b_{n+1}=a_n+2c_n$, $c_{n+1}=b_n$ for $n\ge 1$. It follows that $a_n=c_n$ for $n\ge2$, hence $a_{n+1}=b_n$, $b_{n+1}=3a_n$ for $n\ge 2$. Finally $a_{n+2}=b_{n+1}=3a_n$ for $n\ge 2$.

We compute the fiurst few values: $a_1=2$, $b_1=2$, $c_1=1$, then $a_2=c_2=2$, $b_2=4$, next $a_3=c_3=4$, $b_3=6$. Using $a_{n+2}=b_{n+1}=3a_n$ for $n\ge 2$, we conclude $a_{2k+2}=3^ka_2=2\cdot 3^k$ and $a_{2k+3} = 3^k a_3 = 4\cdot 3^k$ for $k\in \mathbb N_0$. Hence $b_{2k+2}=a_{2k+3} =4\cdot 3^k$ and $b_{2k+3} = a_{2k+4} = 6\cdot 3^k$ because $b_n=a_{n+1}$.

What we are actually looking for is $d_n:=a_n+b_n+c_n$. We find $d_1=5$, $d_2=8$, and for $n\ge 3$, $d_n=\begin{cases}14\cdot3^{\frac{n-3}2}&n\mathrm{\ odd}\\8\cdot3^{\frac{n-2}2}&n\mathrm{\ even}\end{cases}.$ By coincidence, the generic formula is also correct for $d_2$ and almost correct for $d_1$ ($14\cdot3^{\frac{1-3}2}=\frac{14}3\approx 5$).