Return to Answer

The generating function is $$ \sum_{s_1,s_2, s_3} {s_1 + s_2-1 \choose s_2} {s_2+ s_3-1 \choose s_3} x^{s_1+s_2+s_3}.$$

$$ \sum_{s_3} {s_2+ s_3-1 \choose s_3} x^{s_3} = \left( \frac{1}{1-x}\right)^{s_2}$$.

Then the sum over the $s_2$ variable is

$$ \sum_{s_2} {s_1 + s_2-1 \choose s_2}\left( \frac{x}{1-x}\right)^{s_2} = \left( \frac{1}{1- \frac{x}{1-x}} \right)^{s_1} = \left( \frac{1-x}{1-2x} \right)^{s_1}$$

and the sum over just the $s_1$ variable is

$$ \sum_{s_1} \left( \frac{x-x^2}{1-2x}\right)^{s_1} = \frac{1}{1- \frac{x-x^2}{1-2x}}=\frac{1-2x}{1-3x+x^2}.$$

This explains two of the eigenvalues Carlo found. The remaining one comes from the fact that for this to work we need ${-1 \choose 0}=1$. We have to subtract off the terms where $s_1,s_2,$ or $s_3$ is zero. If any is zero then all later ones are zero so these are all contained I $s_3=0$ which gives $(1-x)/(1-2x)$. Subtracting this off we should get the right formula.

The generating function is $$ \sum_{s_1,s_2, s_3} {s_1 + s_2-1 \choose s_2} {s_2+ s_3-1 \choose s_3} x^{s_1+s_2+s_3}.$$

$$ \sum_{s_3} {s_2+ s_3-1 \choose s_3} x^{s_3} = \left( \frac{1}{1-x}\right)^{s_2}$$.

Then the sum over the $s_2$ variable is

$$ \sum_{s_2} {s_1 + s_2-1 \choose s_2}\left( \frac{x}{1-x}\right)^{s_2} = \left( \frac{1}{1- \frac{x}{1-x}} \right)^{s_1} = \left( \frac{1-x}{1-2x} \right)^{s_1}$$

and the sum over just the $s_1$ variable is

$$ \sum_{s_1} \left( \frac{x-x^2}{1-2x}\right)^{s_1} = \frac{1}{1- \frac{x-x^2}{1-2x}}=\frac{1-2x}{1-3x+x^2}.$$

However, we need to remove the terms when $s_1,s_2$ or $s_3$ is zero. Because of the binomial coefficients, if $s_1$ vanishes then $s_2$ vanishes and if $s_2$ vanishes then $s_3$ vanishes, so it suffices to remove the terms with $s_3=0$, which are

$$ \sum_{s_1,s_2} {s_1 + s_2-1 \choose s_2} x^{s_1+s_2}= \frac{1-x}{1-2x}$$ by the same logic.

So the full generating function is $$ \frac{1-2x}{1-3x+x^2} - \frac{1-x}{1-2x}.$$

Your sum is then the coefficient of $x^{n-1}$ in this series. To get this, as EFinat-S suggests we may use partial fractions.

$$ \frac{1-2x}{1-3x+x^2} - \frac{1-x}{1-2x} = \frac{- 2 + \sqrt{5} }{1- \frac{3 + \sqrt{5}}{2} x} + \frac{-2-\sqrt{5} }{1- \frac{3 - \sqrt{5}}{2} x} - \frac{1/2}{1-2x} - \frac{1}{2} $$

which will match the expression Carlo Beenaker gave.

Moreover, this will generalize to the analogue with $s_1,\dots,s_k$, giving a rational generating function. There is a straightforward enumerative interpretation, along the lines of the OEIS reference Carlo found as length $2(n-1)$ depth $k$ nested balanced parantheses expressions / plane trees / Dyck paths, which will thus be related to a column ofOEIS A080936.

The generating function is $$ \sum_{s_1,s_2, s_3} {s_1 + s_2-1 \choose s_2} {s_2+ s_3-1 \choose s_3} x^{s_1+s_2+s_3}.$$

$$ \sum_{s_3} {s_2+ s_3-1 \choose s_3} x^{s_3} = \left( \frac{1}{1-x}\right)^{s_2}$$.

Then the sum over the $s_2$ variable is

$$ \sum_{s_2} {s_1 + s_2-1 \choose s_2}\left( \frac{x}{1-x}\right)^{s_2} = \left( \frac{1}{1- \frac{x}{1-x}} \right)^{s_1} = \left( \frac{1-x}{1-2x} \right)^{s_1}$$

and the sum over just the $s_1$ variable is

$$ \sum_{s_1} \left( \frac{x-x^2}{1-2x}\right)^{s_1} = \frac{1}{1- \frac{x}{1-x}} \right)^{s_1} = \left( \frac{1-x}{1-2x} \right)^{s_1}$$

Examining just the sum over the $s_3$ variable, we get $1/(1-x)^{s_2}.$ then the sum over just the $s_2$ variable is $1/(1-x/(1-x))^{s_1}=((1-x)/(1-2x))^{s_1}$ and so the whole generating function is $(1-2x)/(1-3x+ x^2)$. Thus explains two of the eugenvalues Carlo found. The remaining one comes from the fact that for this to work we need ${-1 \choose 0}=1$. We have to subtract off the terms where $s_1,s_2,$ or $s_3$ is zero. If any is zero then all later ones are zero so these are all contained I $s_3=0$ which gives $(1-x)/(1-2x)$. Subtracting this off we should get the right formula.

The generating function is $$ \sum_{s_1,s_2, s_3} {s_1 + s_2-1 \choose s_2} {s_2+ s_3-1 \choose s_3} x^{s_1+s_2+s_3}.$$

$$ \sum_{s_3} {s_2+ s_3-1 \choose s_3} x^{s_3} = \left( \frac{1}{1-x}\right)^{s_2}$$.

Then the sum over the $s_2$ variable is

$$ \sum_{s_2} {s_1 + s_2-1 \choose s_2}\left( \frac{x}{1-x}\right)^{s_2} = \left( \frac{1}{1- \frac{x}{1-x}} \right)^{s_1} = \left( \frac{1-x}{1-2x} \right)^{s_1}$$

and the sum over just the $s_1$ variable is

$$ \sum_{s_1} \left( \frac{x-x^2}{1-2x}\right)^{s_1} = \frac{1}{1- \frac{x-x^2}{1-2x}}=\frac{1-2x}{1-3x+x^2}.$$

This explains two of the eigenvalues Carlo found. The remaining one comes from the fact that for this to work we need ${-1 \choose 0}=1$. We have to subtract off the terms where $s_1,s_2,$ or $s_3$ is zero. If any is zero then all later ones are zero so these are all contained I $s_3=0$ which gives $(1-x)/(1-2x)$. Subtracting this off we should get the right formula.

The generating function is $$ \sum_{s_1,s_2, s_3} {s_1 + s_2-1 \choose s_2} {s_2+ s_3-1 \choose s_3} x^{s_1+s_2+s_3}.$$

Examining just the sum over the $s_3$ variable, we get $1/(1-x)^{s_2}.$ then the sum over just the $s_2$ variable is $1/(1-x/(1-x))^{s_1}=((1-x)/(1-2x))^{s_1}$ and so the whole generating function is $(1-2x)/(1-3x+ x^2)$. Thus explains two of the eugenvalues Carlo found. The remaining one comes from the fact that for this to work we need ${-1 \choose 0}=1$. We have to subtract off the terms where $s_1,s_2,$ or $s_3$ is zero. If any is zero then all later ones are zero so these are all contained I $s_3=0$ which gives $(1-x)/(1-2x)$. Subtracting this off we should get the right formula.

The generating function is $$ \sum_{s_1,s_2, s_3} {s_1 + s_2-1 \choose s_2} {s_2+ s_3-1 \choose s_3} x^{s_1+s_2+s_3}.$$

$$ \sum_{s_3} {s_2+ s_3-1 \choose s_3} x^{s_3} = \left( \frac{1}{1-x}\right)^{s_2}$$.

Then the sum over the $s_2$ variable is

$$ \sum_{s_2} {s_1 + s_2-1 \choose s_2}\left( \frac{x}{1-x}\right)^{s_2} = \left( \frac{1}{1- \frac{x}{1-x}} \right)^{s_1} = \left( \frac{1-x}{1-2x} \right)^{s_1}$$

and the sum over just the $s_1$ variable is

$$ \sum_{s_1} \left( \frac{x-x^2}{1-2x}\right)^{s_1} = \frac{1}{1- \frac{x}{1-x}} \right)^{s_1} = \left( \frac{1-x}{1-2x} \right)^{s_1}$$

Examining just the sum over the $s_3$ variable, we get $1/(1-x)^{s_2}.$ then the sum over just the $s_2$ variable is $1/(1-x/(1-x))^{s_1}=((1-x)/(1-2x))^{s_1}$ and so the whole generating function is $(1-2x)/(1-3x+ x^2)$. Thus explains two of the eugenvalues Carlo found. The remaining one comes from the fact that for this to work we need ${-1 \choose 0}=1$. We have to subtract off the terms where $s_1,s_2,$ or $s_3$ is zero. If any is zero then all later ones are zero so these are all contained I $s_3=0$ which gives $(1-x)/(1-2x)$. Subtracting this off we should get the right formula.