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?

  • 0
    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.2012-08-09
  • 0
    @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.2012-08-09
  • 0
    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?2012-08-09
  • 0
    @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!2012-08-09
  • 0
    I don't know what you mean by "division doesn't apply for modular arithmetic". If $n+3$ is relatively prime to $m$, then it has a multiplicative inverse modulo $m$, so division is, in principle, not an issue.2012-08-09
  • 0
    @GerryMyerson: But what if $m$ is not relatively prime to $n + 3$? I tried both methods and compare the result, using division actually yielded incorrect results. By the way, I just check the prime factorization of $m = 10^{14} + 7 = 43 \cdot 1103 \cdot 2083 \cdot 1012201$. I think I add some special cases. Thanks a lot.2012-08-09
  • 0
    What do you mean, "both methods"?2012-08-10
  • 0
    @GerryMyerson: I meant brute-force vs this formula: $M_{n+1} = \dfrac{2n + 3}{n + 3}M_n + \dfrac{3n}{n + 3}M_{n-1}$2012-08-10
  • 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
    Good. That looks much better than what I put into the comments.2012-08-10
  • 0
    Nice one, thanks a lot.2012-08-10