# How to cancel the division of a recurrence matrix?

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?

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

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

-
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