The $<mn$ seems to suggest Pigeon hole as you say. Let’s explore. We want $mn$ sets. One possibility is to define $S_{i,j} = x_i + y_j$. Problem is they might exceed $mn$ so there would be $2mn -2$ holes. Hmm, that does’t seem to work. How can we squeeze that into at most $mn-1$ holes? Let’s take the answer mod $mn-1$.
That gives us at most $mn-1$ values so there must be $i,j,k,l$ such that $x_i + y_j = x_k + y_l \mod mn-1$. Rearranging, we get $x_i - x_k = y_l - y_j \mod mn-1$. Hmm, that’s not exactly what we need. This seems to tell us the difference between two elements is the same modulo $mn-1$.
Can we redefine the sets so that the above expression is a sum? The only fact we used above is that there are $mn$ summations. They don’t neccessarily need to be $x_i+y_j$! Aha, if they are contigious intervals, then maybe the subtraction works out for us!
Try 2: let $S_{i,j} = x_1 + … + x_i + y_1 + … + y_j$. There are still $mn$ sets and we take it mod $mn-1$, so there exists $i,j,k,l$ such that $x_1+…+x_i+ y_1+…+y_j = x_1+…+x_k + y_1+…+y_l \mod mn-1$. Almost there! If $i=k$ then we’re in trouble because a bunch of y variables sum to zero, which is impossible. So either $i<k$ or $i>k$. Assume WLOG that $i< k$. Then we get:
$$x_{i+1} + … + x_k = y_1 + … + y_j - y_1 - … - y_l \mod mn-1$$
If $j>l$, then we are done! Two sums that are equal, mod $mn-1$ and they are less than $mn-1$ so they are actually equal. But what about if $l > j$. Darn it, we are stuck.
Is there hope to save this? What else do we have? We changed the sets, and they seem to work except for this pesky set. What other freedom do we have? One “arbitrary” thing we did was take mod $mn-1$. Ok, let’s try setting it to $V<mn$ (to keep the holes number small). What can we do in modulo arithmetic? Well, we can add $V$ to any side. Let’s do that:
$$x_{i+1} + … + x_j = -y_{j+1} - … -y_l + V \mod V$$
Can we retrieve any sum from the RHS for any choice of V? What if $V$ is exactly the common sum? We get some $x$s and some $y$s sum to each other modulo the common sum! But since they are less than the common sum, then they are actually equal! We’re done.
Best Answer
Snake oil: \begin{align} \sum_{n=0}^\infty a_n z^n &= \sum_{n=0}^\infty \left(\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}\left(-\frac{1}{4}\right)^k \right) z^n \\ &= \sum_{k=0}^\infty \left(-\frac{1}{4}\right)^k\sum_{n=2k}^\infty \binom{n-k}{k} z^n \\ &= \sum_{k=0}^\infty \left(-\frac{1}{4}\right)^k z^{2k}\sum_{n=0}^\infty \binom{n+k}{k} z^n \\ &= \sum_{k=0}^\infty \left(-\frac{z^2}{4}\right)^k\frac{1}{(1-z)^{k+1}} \\ &= \frac{1}{1-z}\sum_{k=0}^\infty \left(-\frac{z^2}{4(1-z)}\right)^k \\ &= \frac{1}{1-z}\cdot\frac{1}{1+\frac{z^2}{4(1-z)}} \\ &= \frac{1}{(1-z/2)^2} \\ &= \sum_{n=0}^\infty \binom{n+1}{1} (z/2)^n \\ &= \sum_{n=0}^\infty \frac{n+1}{2^n} z^n \end{align} So $a_n= (n+1)/2^n$ for $n \ge 0$.
Note that this approach derives the formula without the need to guess the pattern.