Suppose that I have a recurrence relation

$$\sum_{k=0}^n\binom{mn}{mk}A(mk)=0 \Rightarrow A(mn)=-\sum_{k=0}^{n-1}\binom{mn}{mk}A(mk)$$

with conditions $A(0)=1$, and $A(n)=0$ if $n\not\equiv 0\pmod{m}$. Then using the recurrence relation, it is easy to get that for $n=1, A(m)=-1$. Then for $n=2$,


By the Catalan number relation


where the factor $C(m)$ is the $m$-th Catalan Number, it is seen that $A(2m)\equiv -1\pmod{m+1}$

Using these facts, I'd like to try and show that

$$A(mn)\equiv -1{\pmod{m+1}}$$

I thought induction would help, so i assume for all $k\ge n, A(mk)\equiv -1\pmod{m+1}$, and though would mean that


However, from here, I am stuck. Can anyone either point me in the right direction, or show me if there is a fatal flaw in my reasoning?


I'd like to try and show that $$A(mn)\equiv -1{\pmod{m+1}}$$

This does not hold for $(m,n)=(5,4)$.

We have $$\sum_{k=0}^1\binom{5\times 1}{5k}A(5k)=0\implies A(5)=-1$$ $$\sum_{k=0}^2\binom{5\times 2}{5k}A(5k)=0\implies A(10)=251$$ $$\sum_{k=0}^3\binom{5\times 3}{5k}A(5k)=0\implies A(15)=-750751$$ $$\sum_{k=0}^4\binom{5\times 4}{5k}A(5k)=0\implies A(20)=11593285251$$ and $$A(20)\equiv 3\pmod 6$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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