# Finding sum form for a particular recursive function

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$.

-
You defined $a$ and $x$, but what's $f$? – J. M. Oct 1 '11 at 1:46
The condition just says there are $2k$ ones in the first $3k$ terms, and the other $n-3k$ terms can each be $0$ or $1$ independently with no restrictions, which would mean the answer is simply $\tbinom{3k}{2k}2^{n-3k}$ sequences, no? – anon Oct 1 '11 at 1:52
oops I meant x when I wrote f. edited. – DumbQuestion Oct 1 '11 at 1:56
anon, that is the solution for some fixed k, but I want to find it over all $k\le n$, so I have to make sure I am not double counting. – DumbQuestion Oct 1 '11 at 1:58
@Dum: Oh, you should probably change "where" to "for all $0<k\le n$" in the question then. – anon Oct 1 '11 at 2:02

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}\;.$$

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.

-
That makes sense, thank you! – DumbQuestion Oct 1 '11 at 14:11

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.

-
If I understand the question correctly, this is wrong. It gives $x_3=234$, whereas $x_3$ should be $261$. Can you explain how you came up with this? – joriki Oct 1 '11 at 10:44
@joriki: I assumed that the recurrence was correct; apparently it isn't. – David Bevan Oct 1 '11 at 11:01
That's right, it isn't. – joriki Oct 1 '11 at 11:03