A word is bifix-free provided it has no proper initial string and terminal string that are identical. Let $a_n^{(q)}$ be the number of bifix-free strings over a fixed $q$-letter alphabet. The generating function $f(x) = f^{(q)}(x) = \sum_{n = 0}^{\infty} a_nx^n$ satisfies the functional equation $$f(x) = qx + qxf(x) - f(x^2).$$

Solving for $f(x)$ gives $$f(x) = \frac{qx - f(x^2)}{1-qx} = \cdots = \sum_{j=0}^{\infty} \frac{(-1)^jqx^{2^j}}{\prod_{k=0}^{j} (1 - qx^{2^k})}.$$

(Q1) Is there a "nice" solution to this functional equation, perhaps one that does not involve an infinite product or sum?

Here is a plot of $f^{(2)}(x)$ generated in Sage:

The limit as $n \to \infty$ of the probability that a uniformly random word of length $n$ is bifix-free is $1 - f^{(q)}(q^{-2})$. From the initial three terms in the alternating series above, as $q \to \infty$, $$f^{(q)}(q^{-2}) = \frac{1}{q-1} - \frac{1+o(1)}{q^3}.$$

(Q2) What else can be said specifically about $f^{(q)}(q^{-2})$ for integers $q \geq 2$? Is there a simpler formula than the infinite series above? Are these values rational? ...algebraic?

Here is a plot of $f^{(x)}(x^{-2})$ generated in Sage:

(The combinatorics-on-words paper associated with this function is here.)

A word (i.e., ordered string of letters) is bifix-free provided it has no proper initial string and terminal string that are identical. For example, the word $ingratiating$ has bifix $ing$, but the word $ingratiate$ is bifix-free.

Let $a_n^{(q)}$ be the number of bifix-free words over a fixed $q$-letter alphabet. The generating function $f(x) = f^{(q)}(x) = \sum_{n = 0}^{\infty} a_nx^n$ satisfies the functional equation $$f(x) = qx + qxf(x) - f(x^2).$$

Solving for $f(x)$ gives $$f(x) = \frac{qx - f(x^2)}{1-qx} = \cdots = \sum_{j=0}^{\infty} \frac{(-1)^jqx^{2^j}}{\prod_{k=0}^{j} (1 - qx^{2^k})}.$$

(Q1) Is there a "nice" solution to this functional equation, perhaps one that does not involve an infinite product or sum?

Here is a plot of $f^{(2)}(x)$ generated in Sage:

The limit as $n \to \infty$ of the probability that a uniformly random word of length $n$ is bifix-free is $1 - f^{(q)}(q^{-2})$. From the initial three terms in the alternating series above, as $q \to \infty$, $$f^{(q)}(q^{-2}) = \frac{1}{q-1} - \frac{1+o(1)}{q^3}.$$

(Q2) What else can be said specifically about $f^{(q)}(q^{-2})$ for integers $q \geq 2$? Is there a simpler formula than the infinite series above? Are these values rational? ...algebraic?

Here is a plot of $f^{(x)}(x^{-2})$ generated in Sage:

(The combinatorics-on-words paper associated with this function is here.)