A system of equations for integers

Question

Working with cellular automata I came across a system of equations for unknown integers $R_{k}$ and $C_{k}$ that looks like this.

$\binom{m}{k}=R_{k}+C_{k}+\sum\limits_{j=1}^{k-1}R_{j}C_{k-j}.$

Where 0< k$\leq$ 2m

(for k>m we take $\binom{m}{k}=R_{k}=C_{k}=0$)

Given $R_{1}$, the system has a unique solution.

Has anyone seen something similar? Do you know if it still possible to solve it, if instead of $\binom{m}{k}$ in the left you put something else?

I just want to know if it's related to something else, and if it's possible to solve more general systems.

Answer 1

So piggybacking off the two two good answers so far, a system of equations $$a_k=R_k+C_k+\sum\limits_{j=1}^{k-1}R_{j}C_{k-j} \text{ for } 1 \le k \le M$$ is a system of $M$ equations in $2M$ variables which starts out

$$\begin{align} R_1 + C_1 &= a_1\\\ R_2+C_2&= a_2-R_1C_1 \\\ R_3+C_3 &= a_3- R_2C_1 - R_1C_2 \\\ R_4+C_4 &= a_4- R_3C_1 - R_2C_2-R_1C_3\\\ \end{align}$$

This can be solved top down leading to an a branching cascade of solutions where at stage $j$ we have $$R_j+C_j=b_j$$ where $b_j$ depends of the previous choices. If the $a_i$ are non-negative integers and we want the solutions to be of the same form then at that stage we have $\max(0,b_j+1)$ choices.

The system is equivalent to $$\left(1+\sum_1^MC_jx^j\right)\left(1+\sum_1^MR_jx^j\right)=1+\sum_1^Ma_jx^j+O(x^{M+1})$$

---

If we add enough conditions to make it equivalent to $$\left(1+\sum_1^MC_jx^j\right)\left(1+\sum_1^MR_jx^j\right)=1+\sum_1^Ma_jx^j$$ then there is some number of solutions (at most $2^M$) depending on how the right-hand side factors (and the conditions).

One set of conditions which does this is that $M=2m$ and $R_j=C_j=0$ for $j \gt m.$

If we say that the $a_j$ are in $\mathbb{Z}$ and the $R_j,C_j$ should be rational then there will be some solutions and they will all be integers (one is $R_j=0$ and $C_j=a_j$).

As noted, in the given problem the $m+1$ solutions come from $(1+x)^t(1+x)^{m-t}=(1+x)^m$ so they are $C_j=\binom{t}{j},R_j=\binom{m-t}{j}$ for some non-negative integer $t \le m.$

It is a disguised form of a classic problem to solve the case that the $a_k$ are all $1$ for $k \le m$ and the $C_i,R_i$ should be nonegative.

Answer 2

Here something is being said about the generating functions r(t) and c(t) for the $R_{k}$ and $C_{k}$; we'd better agree to begin with that $R_{0}$ and $C_{0}$ for that purpose are both equal to 1. You want in fact to multiply: the product r(t)c(t) is determined by your equation, coefficient by coefficient. So far, so good.

On the face of it, you are saying in fact that the product r(t)c(t) is the same as mth power of 1 + t. If you simply force r(t) and c(t) to be polynomials, then under this condition the uniqueness of factorisation of polynomials means here there are only the powers of 1 + t possible. I think this isn't what you are actually saying, or intending, so I'm a bit puzzled at this point. With r(t) and c(t) as just any power series you can't expect uniqueness at all: there are numerous invertible power series. The "boundary condition" forcing r(t) and c(t) to be polynomials is very strong, therefore.

Answer 3

I agree with Charles Matthews, there's something that doesn't seem right in the formulation of the problem. Consider what you get for $m=2$:

$$\begin{align} {2 \choose 1} &= R_1 + C_1 \\\ {2 \choose 2} &= R_2 + R_1C_1 + C_2\\\ {2 \choose 3} &= R_3 + R_2C_1 + R_1C_2 + C_3\\\ {2 \choose 4} &= R_4 + R_3C_1 + R_2C_2 + R_1C_3 + C_4 \end{align}$$

Given the assumptions made for $k>m$, this becomes

$$\begin{align} 2 &= R_1+C_1\\\ 1 &= R_2 + R_1C_1 + C_2\\\ 0 &= R_2C_1 + R_1C_2\\\ 0 &= R_2C_2 \end{align}$$

This has just three possible solutions $(R_1,C_1,R_2,C_2)$: $(0,2,0,1)$ $(1,1,0,0)$, and $(2,0,1,0)$, so it's not clear what's meant by saying "Given $R_1$, the system has a unique solution." Here's my guess:

For each $m$, the system has $m+1$ solutions, each solution is in non-negative integers, and there is exactly one solution for each integer $0 \le R_1 \le m$.

This is certainly true for $m=1$ and $m=2$ and seems to be true for $m=3$ as well (I checked but didn't doublecheck that case).

Added later: Aaron Meyerowitz has taken this quite a bit further, so read his answer, not this one.