In symbolic dynamics, the context-free shift is the set of biinfinite concatenations of strings of the form $01^k2^k$ for $k\in\mathbb{N}\cup\lbrace 0\rbrace$. I've reduced a certain problem to finding a reasonable upper bound on the number of ways to concatenate such strings to create a string of length n. This can be looked at as the number of ways to partition n into positive odd summands, taking combinations into account, but this doesn't seem to be a reasonable approach to the problem. How would I go about making this estimation?



Estimation of number of ways to concatenate strings of the form $01^k2^k$ to create a string of length n
Here is another approach to your question that could be used more generally for context-free shifts. Let C be the language of strings $01^k2^k$. This language is a suffix code (no two words are suffixes of each other). Thus the set $C^\*$ of concatenations of elements of C is a free monoid generated freely by $C$ and so the generating function g(t) for $C^\*$ is $\frac{1}{1-f(t)}$ where f(t) is the generating function for C. Now C is given by the unambiguous context-free grammar 


$S\to 0T$, 


$T\to \varepsilon \mid 1T2$


The Chomsky-Schutzenberger theorem then says $f(t)=tr(t)$ where $r(t)=1+t^2r(t)$. Thus $f(t)= \frac{t}{1-t^2}$. Thus $g(t)=\frac{1-t^2}{1-t-t^2}$ which is the Fibonacci generating series, or at least is the same recurrence. 


