Finding a recurrent relation or formula

Question

The formulation of the original problem: "How many words can be made up of N sticks, if two sticks can make the letter i, and three sticks can make j?"

Final task: create a formula (or recurrent ratio) that finds the value of the number of words for a given number of sticks.

There may be some way to use combinatorics here. The ratio of the number of sticks to the number of words:

1 stick — 0 words

2 sticks — 1 word

3 sticks — 1 word

4 sticks — 1 word

5 sticks — 2 words

6 sticks — 2 words

7 sticks — 3 words

8 sticks — 4 words

9 sticks — 5 words

10 sticks — 6 words

Answer 1

A valid word of length $n$ contains $i$ times $I$ and $j$ times $J$ such that $2i+3j=n$. We denote with \begin{align*} S_n=\{(i,j)|2i+3j=n,\quad i,j\geq 0\}\qquad\qquad n\geq 0 \end{align*} the set of pairs $(i,j)$ from which valid words are built. The number of valid words $A(n)$ which can be built from $i$ times $I$ and $j$ times $J$ is \begin{align*} \binom{i+j}{i} \end{align*} since out of $i+j$ positions in a word of length $2i+3j=n$ we can select $i$ positions for $I$.

We conclude a formula providing the number $A(n)$ of valid words of length $n$ is \begin{align*} \color{blue}{A(n)=\sum_{(i,j)\in S_n}\binom{i+j}{i}}\tag{1} \end{align*}

Based upon (1) we derive another representation. In oder to so, we consider cases $n=6m+q$, with $0\leq q\leq 5$. We show exemplarily the derivation for $n=6m+2$.

Case $n=6m+2$:

We have \begin{align*} n&\in\{2,8,14,20,\ldots\}\\ m&\in\{0,1,2,3,\ldots\}\\ \end{align*} and get \begin{align*} S_2&=\{(1,0)\}\\ S_8&=\{(1,2),(4,0)\}\\ S_{14}&=\{(1,4),(4,2),(7,0)\}\\ S_{20}&=\{(1,6),(4,4),(7,2),(10,0)\}\\ &\cdots \end{align*} It follows by inspection \begin{align*} A(n)=\sum_{j=0}^m\binom{(3j+1)+(2m-2j)}{3j+1}=\sum_{j=0}^m\binom{2m+j+1}{3j+1} \end{align*} the other cases can be solved similarly.

We obtain this way \begin{align*} \color{blue}{A(n)}&\color{blue}{=\sum_{j=0}^m\binom{2m+j+p}{3j+q}}\tag{2}\\ \\ \color{blue}{(p,q)}&\color{blue}{= \begin{cases} (0,0)\qquad n=6m\\ (1,2)\qquad n=6m+1\\ (1,1)\qquad n=6m+2\\ (1,0)\qquad n=6m+3\\ (2,2)\qquad n=6m+4\\ (2,1)\qquad n=6m+5\\ \end{cases}} \end{align*}

Note: A closed formula from (2) is not within reach. This is a consequence of Theorem 2.2.2 in Integral Representation and the Computation of Combinatorial Sums by G. P. Egorychev which provides information about closed form computations of expressions of the form \begin{align*} \sum_{j=0}^m\binom{a_1n+a_2j+a_3}{a_4n+a_5j+a_6}x^j \end{align*}