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
Finding sum form for a particular recursive function
-
0Unfortunately, your recurrence counts sequences like $011001111$ (in which the condition is satisfied for $k=1$ and $k=3$) multiple times. – 2011-10-01
2 Answers
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.
-
0That makes se$n$se, than$k$ you! – 2011-10-01
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.
-
0That's right, it isn't. – 2011-10-01