1
$\begingroup$

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?

  • 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.2012-08-10

1 Answers 1

2

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

  • 0
    Nice one, thanks a lot.2012-08-10