A while ago, after careful observation I've found a closed formula for linear recurrence relations:
Suppose
$$a_i = \begin{cases}
0 & \text{if $i < 0$ } \\
1 & \text{if $i = 0$} \\
a_{i-2} + a_{i-3} & \text{if $i > 0$}
\end{cases}$$
So, starting from $a_0$, we have $1,0,1,1,1,2,2,3,4,5,7,9,\ldots$
Then
$$a_i = \sum_{2x+3y=i} \binom{x+y}{x \quad y}$$
where $x$, $y$ are non-negative integers.
For example, to find $a_{11}$ we have to find the solutions of $2x+3y=11$ which are $(x,y) = (4,1),(1,3)$ so $a_{11} = \binom{4+1}{4} + \binom{1+3}{1} = 5 + 4 = 9$.
This also generalizes nicely to multidimensional linear recurrence relations:
Suppose
$$a_{i,j} = \begin{cases}
0 & \text{if $i < 0$ or $j<0$ } \\
1 & \text{if $(i,j) = (0,0)$} \\
a_{i-2,j} + a_{i-1,j-1} + a_{i,j-2} & \text{otherwise}
\end{cases}$$
So, if we consider the first cell to be $(0,0)$, we have
$$
\begin{matrix}
1 & 0 & 1 & 0 & 1 & 0 & 1 & \ldots\\
0 & 1 & 0 & 2 & 0 & 3 & \ldots\\
1 & 0 & 3 & 0 & 6 & \ldots\\
0 & 2 & 0 & 7 & \ldots\\
1 & 0 & 6 & \ldots\\
0 & 3 & \ldots\\
1 & \ldots \\
\ldots
\end{matrix}
$$
so this is basically the trinomial triangle.
We have a similar solution:
$$a_{i,j} = \sum_{\begin{cases}2x+1y+0z=i \\ 0x+1y+2z=j\end{cases}} \binom{x+y+z}{x \quad y \quad z}$$
where $x$, $y$, $z$ are non-negative integers.
Of course it's easy to imagine a generalization with more dimensions, adding coefficients to the recurrence relationship etc., but I think you get the point.
My problem is, I've been unable to find the name or the statement of this theorem on the internet, and I'd like to know more about it. Do you know its name, a place where it is stated or used or somewhere I can get more informations?
Best Answer
I would think of this as an immediate corollary to the multinomial theorem.
Here's a proof using generating functions to help organize information.
Let $F = \sum_{i=0}^{\infty} a_nX^n$ be the generating function of your sequence, with $a_n$ as defined as in your question.
Note that $(1 - X^2 - X^3)F = 1$, or equivalently we can write $F$ as a rational function, $F = 1 / (1 - X^2 - X^3)$.
The trick is to set $Y = X^2 + X^3$, so that we can also think of $F$ as a geometric series in $Y$, i.e. $F = \sum_{n=0}^{\infty} Y^n$
Now observe that binomial expansion yields the equality $$Y^n = (X^2 + X^3)^n = \sum\limits_{a+b = n} {a + b \choose a,b} X^{2a + 3b}$$
We are interested in a closed form expression for $a_n$, which is the coefficient of $X^n$ in $F$. From the above observation, we can achieve this by calculating the coefficient of $X^n$ in $Y^m$ for each $m$ and then adding all of these contributions together.
If $n$ is such that $2a + 3b = n$, then $Y^{a+b}$ contributes ${a+b \choose a,b}$ to the coefficient of $X^n$.
Summing up all of these we indeed get that $$a_n = \sum_{2a + 3b = n} {a+b \choose a,b}$$
This gives us a general method for converting a linear recurrence to a closed form expression for the $n$th term of the sequence.
Indeed, if we have a linearly recurrent sequence defined by
$$a_n = \begin{cases} 0 & \text{if $n < 0$ } \\ 1 & \text{if $n = 0$} \\ \sum_{i = 1}^m c_i a_{n-i} & \text{if $n > 0$} \end{cases}$$
then the above proof can be generalized with minimal effort to get that
$$a_n = \sum\limits_{v \cdot b = n} \big(\prod_{j=1}^m {c_j}^{b_j}\big) {\sum_{i=1}^m b_i \choose b_1, b_2, \ldots, b_m}$$
where $v = (1,2,3,4,\ldots, m)$ so that $v \cdot b = n$ is shorthand for $\sum_{i = 1}^m ib_i = n$.
You can go one step further, if you want, and generalize this to any multidimensional linearly recurrent sequence. The proof by univariate generating functions for the 1-dimensional case easily extends to multivariate generating functions.