Finding sum form for a particular recursive function

Question

Consider a finite sequence of zeros and ones of length $3n$, with $n$ an integer. We write an element of this sequence as $a_i$. How many sequences are there such that there exists an integer $k$, $0<k\le n$, such that $\sum^{3k}_{j=1}a_j=2k$? Here is what I have as of now: let $x_n$ be this number. We notice that $x_1=\binom{3}{2}=3$, and $x_n=\binom{3n}{2n}-\binom{3}{2}x_{n-1}+2^{3}x_{n-1}=\binom{3n}{2n}+5x_{n-1}$. How would I find a sum form solution to this? Also, does this seem correct? I got this because $\binom{3n}{2n}$ counts the total number of sequences satisfying the condition for $k=n$, $\binom{3}{2}x_{n-1}$ is the number of sequences satisfying it for both $k=n$ and $k=n-1$, and the number of sequences satisfying $k=n-1$ should be $x_{n-1}$, and we can choose the last three elements at random, so we multiply by $2^3$.

Answer 1

The recurrence relation you derived isn't right. I'm not sure I understand your explanation of the derivation, but it seems you may have confused the number of sequences of length $3(n-1)$ fulfilling the condition for any $k$ with the number of sequences of length $3(n-1)$ fulfilling the condition for $k=n-1$.

Let's call a sequence of length $3k$ that has $2k$ ones "$k$-balanced", and a sequence that is $k$-balanced but not $j$-balanced for any $j\lt k$ "$k$-exclusive". To get the correct result, consider the number $a_n$ of $n$-exclusive sequences. We can count this as the number $\binom{3n}{2n}$ of $n$-balanced sequences minus the number of all $n$-balanced extensions of $k$-exclusive sequences for $0\lt k\lt n$. For each $k$, there are $a_k$ $k$-exclusive sequences to be extended, and the remaining $3(n-k)$ values must contain exactly $2(n-k)$ ones for the sequence to be $n$-balanced. Thus

$$a_n=\binom{3n}{2n}-\sum_{k=1}^{n-1}\binom{3(n-k)}{2(n-k)}a_k\;.$$

The left-hand side is the missing $n$-th term of the sum, so this becomes

$$\sum_{k=1}^n\binom{3(n-k)}{2(n-k)}a_k=\binom{3n}{2n}\;.$$

Now

$$\sum_{k=1}^n\binom{3(n-k)}{2(n-k)}\binom{3k}{2k}\frac2{3k-1}=\binom{3n}{2n}\;,$$

so

$$a_k=\binom{3k}{2k}\frac2{3k-1}\;.$$

For more on this, see What's the probability that a sequence of coin flips never has twice as many heads as tails? and Combinatorial proof of $\binom{3n}{n} \frac{2}{3n-1}$ as the answer to a coin-flipping problem.

The desired number $x_n$ is the number of all extensions of $k$-exclusive sequences to length $3n$, of which there are $2^{3(n-k)}$. Thus

$$x_n=\sum_{k=1}^na_k2^{3(n-k)}=\sum_{k=1}^n\binom{3k}{2k}\frac{2^{3(n-k)+1}}{3k-1}\;.$$

Wolfram|Alpha gives a "closed form" for this similar to the one in David's answer.

Answer 2

If $x_n$ was $\binom{3n}{2n}+5x_{n-1}$, which it isn’t, we would have

$$ x_n=\sum_{k=1}^{n} 5^{(n-k)} \binom{3k}{2k} $$ Mathematica gives the following “closed form”:

$$ x_n=-\frac{1}{5} \binom{3 n+3}{2 n+2} \, _3F_2\left(1,n+\frac{4}{3},n+\frac{5}{3};n+\frac{3}{2},n+2;\frac{27}{20}\right) -\alpha \;5^n $$ where $ \alpha=1+2 i \sqrt{\frac{5}{7}} \cos \left(\frac{1}{6} \cos ^{-1}\left(-\frac{17}{10}\right)\right) $ is a (complex) root of $7 z^3-21 z^2+36 z-27$, and $_3F_2$ is a generalized hypergeometric function.