Inductive sequence of words in a biprefix code Let $X = X_1 \cup X_2$ a code on an alphabet $A$, with $X_1$ a biprefix code and $X_2$ a uniform code, with $m(X_1) &lt; m(X_2)$, i.e. the maximal length of the first is strictly lower than the second. Now, if $v \in X_2$ we define a sequence such that $v_0 = v$ and $v_{i+1} = 1$ if $v_i \notin X_1A^*$ and $v_{i+1} = y_ix_i$ if instead $v_i \in X_1A^*$, with $v_i = x_iy_i$ with $x_i \in X_1, y_i \in A^*$.
Now, let $u,v \in X_2$ and suppose there exist two integers $i \leq j$ such that $u_{i} = v_j$. Since $X_1$ is biprefix, this implies that $u_{i-1} = v_{j-1}$. Why does this imply that $u_0 = v_{j-1}$? The paper I am reading motivates this last deduction by induction, but I can’t see how $j-1$ could stay fixed in the process. Any hints?
Your paper has a typo. It should be $u_0 = v_{j-i}$ rather than $u_0 = v_{j-1}$.
Indeed, consider the following example: the alphabet is $A = \{0,1\}$, and the two codes are $X_1 = A^1$ and $X_2 = A^2$. Take $u = 01$ and $v = 10$. Then $u_0 = 01$, $v_0 = 10$, and $v_1 = 01$. If $i = 0$ and $j = 1$ then $u_i = v_j$, yet $u_0 \neq v_{j-1}$; but $u_0 = v_{j-i}$.
You already know that $u_i = v_j$ implies $u_{i-1} = v_{j-1}$. Applying this step $i$ times, you immediately conclude that $u_0 = v_{j-i}$.