Consider two symbols, $X$ and $Y$.

Symbol $X$ spawns $X$ and $Y$ -- think of the spawning as a binary tree rooted in $X$ with two leaves. The path weight for leaf $X$ is $a$ and that for leaf $Y$ is $b$.

Symbol $Y$ also spawns $X$ and $Y$ -- however, the path weight for leaf $X$, in this case, is $c$ and that for leaf $Y$ is $d$.

Let us start with symbol $X$ and consider another binary tree.

Each level of the tree is made of children spawned by the previous level.

That is, the root, or the first level, will be $X$.

The next level will be $X$ and $Y$, with the weight of the path connecting $X$ (of the second level) to $X$ (the root) being $a$ and that connecting $Y$ to the root $X$ being $b$.

Similarly, the next level will have $X$ (path weight upto the root being $a^{2}$), $Y$ (path weight upto the root being $ab$), $X$ (path weight upto the root being $bc$), and $Y$ (path weight upto the root being $bd$.)

As is evident, the weights of different paths get multiplied when counting the weight of a path till the root. Then, the final weights are added together to get the total weight of a symbol.

Additionally, as is also evident, the first ($X$, $Y$) pair of this level was spawned from $X$ (of the previous level) and the second pair was spawned from $Y$ (of the previous level.)

So, the total weight for symbol $X$ in this level will be $a^{2} + ab$ and the total weight for symbol $Y$ will be $bc + bd$.

Let us say the binary tree has $k$ levels.

What is the total weight of symbol $X$ and symbol $Y$ after the $k^{\text{th}}$ level?


1 Answer 1


By using induction from the leafs to the root : Lets $x_k$ be the weight of a tree of depth $k$ rooted on $X$, and $y_k$ same but rooted on $Y$.

We have the following recurrence : $$x_{k+1} = ax_k + by_k$$ $$y_{k+1} = cx_k + dy_k$$ $$x_0 = y_0 = 1$$ which is a system of linear homogeneous recurrences, and can be solved the classic way.

  • $\begingroup$ What is the classic way to solve the recurrence? $\endgroup$ Mar 30, 2022 at 14:13
  • $\begingroup$ @RandomMatrices You can write $u_k = (x_k, y_k)$, $u_{k+1} = Au_k$, with $A = \left(\begin{matrix} a &c\\b &d\end{matrix}\right)$, which gives $u_n = Au_0$, so you need to compute $A^n$. $A^n = P^{-1}D^nP$ if $A$ is diagonalizable. Cayley-Hamilton works in a more general way. For the 2x2 case: math.stackexchange.com/questions/3478394/… $\endgroup$
    – caduk
    Mar 30, 2022 at 15:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .