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.

The recurrence is for Motzkin number, which is defined as follows: $$M_{n+1} = \begin{bmatrix} \dfrac{2n+3}{n+3} & \dfrac{3n}{n+3} \\ 1 & 0\end{bmatrix}^n \cdot \begin{bmatrix} 1 \\ 1\end{bmatrix}$$

where $M_{n+1}$ is the $n+1$th Motzkin number.

I wonder is there an equivalent form without having to divide by $n + 3$ because the value after calculation must be modulo with another number $m$, where the division doesn't apply for modular arithmetic. For example, something like: $$\text{some terms} \cdot M_{n+1} = \begin{bmatrix} 2n +3 & 3n \\ 1 & 0\end{bmatrix}^n \cdot \begin{bmatrix} 1 \\ 1\end{bmatrix}$$

The motivation came from this thread How to compute linear recurrence using matrix with fraction coefficients?

share|improve this question
    
The expression shown as a recurrence relation is incorrect. The recurrence relation coefficients are not constant, so while $M_{n+1}$ can be expressed as a product of 2x2 matrices times a constant initial vector, that product is not the power shown. –  hardmath Aug 9 '12 at 20:49
    
@hardmath: Yes, it is incorrect. Thanks for catching that, I derived that matrix based on Fibonacci one. However it is much easier with Fibonacci since the coefficients are constants. Now I don't even know if it can be expressed as matrix power form. –  Chan Aug 9 '12 at 20:59
    
We can write out the product and move the factor of $(n+3)!$ to the left hand side, but I'm doubtful this will help your residue $\mod{m}$ analysis. Would you like me to set this out as an answer? –  hardmath Aug 9 '12 at 22:08
    
@hardmath: Please do. I'm struggling with this problem for 3 days. I'm wondering where all these techniques come from. Programming contest problem writer is amazing! –  Chan Aug 9 '12 at 22:18
1  
I think the correct way to set this up with matrices is $$\pmatrix{M_{n+1}\cr M_n\cr}=\left(\prod_{k=2}^n\pmatrix{(2k+3)/(k+3)&3k/(k+1)\cr(2k+1)/(k+2)&(3k-3)/‌​k\cr}\right)\pmatrix{M_2\cr M_1\cr}$$ but I don't see any way to reduce this modulo $m$ without first multiplying it out. –  Gerry Myerson Aug 10 '12 at 0:43

1 Answer 1

up vote 2 down vote accepted

If we let $\mathcal{A}_n = \begin{bmatrix} \frac{2n+3}{n+3} & \frac{3n}{n+3} \\ 1 & 0 \end{bmatrix} $, then the recurrence relation for Motzkin numbers $M_n$ can be expressed as:

$$ \begin{bmatrix} M_{n+1} \\ M_n \end{bmatrix} = \mathcal{A}_n \begin{bmatrix} M_n \\ M_{n-1} \end{bmatrix} $$

Repeated application of this relation, along with $M_0 = M_1 = 1$, gives the product for $n \ge 2$:

$$ \begin{bmatrix} M_{n+1} \\ M_n \end{bmatrix} = \mathcal{A}_n \cdots \mathcal{A}_1 \begin{bmatrix} 1 \\ 1 \end{bmatrix} $$

If desired we can clear fractions in the above formula:

$$ \frac{(n+3)!}{3!} \begin{bmatrix} M_{n+1} \\ M_n \end{bmatrix} = \mathcal{B}_n \cdots \mathcal{B}_1 \begin{bmatrix} 1 \\ 1 \end{bmatrix} $$

where $\mathcal{B}_n = \begin{bmatrix} 2n+3 & 3n \\ n+3 & 0 \end{bmatrix}$.

share|improve this answer
    
Good. That looks much better than what I put into the comments. –  Gerry Myerson Aug 10 '12 at 4:43
    
Nice one, thanks a lot. –  Chan Aug 10 '12 at 5:44

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.