Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
Seems like you got the right solution, I'll check it in a few minutes, and edit this comment. thanks for your efforts! –  RB14 Sep 7 '12 at 16:47
    
Ah, you type faster :) –  Hagen von Eitzen Sep 7 '12 at 16:50
    
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! –  RB14 Sep 7 '12 at 17:36

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

share|improve this answer
    
Good idea you got there, but I don't think (actually I'm pretty sure) the solution doesn't involve matrices..we don't use these kind of solutions in my course.. it should be much simpler. –  RB14 Sep 7 '12 at 16:18
    
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)$. –  Robert Israel Sep 7 '12 at 16:41

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$).

share|improve this answer
    
Thanks for your answer :) –  RB14 Sep 7 '12 at 17:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.