Sum of terms in a composition cycle

Question

Let $f, g$ be linear functions.

Define $S(x)$ as $any$ composition sequence of $f$ and $g$ like

$S(x) = (f\circ g\circ g\circ f\circ f\circ g)(x)$

Let $s$ as the fixed point of $S$ then a cycle is determined

$s \to_g g(s) \to_f (f\circ g)(s) \to_f (f\circ f\circ g)(s) \to_g (g\circ f\circ f\circ g)(s) \to_g (g\circ g\circ f\circ f\circ g)(s) \to_f s (again)$

Call $Sum_g(S)$ the sum of the terms of the cycle such that $g$ function is applied to this term.

In this example $Sum_g(S) = s + (f\circ f\circ g)(s) + (g\circ f\circ f\circ g)(s)$

Define $T(x)$ as the reversed composition sequence

$T(x) = (g\circ f\circ f\circ g\circ g\circ f)(x)$

Call $t$ the fixed point of $T$

In this example $Sum_g(T) = (f)(t) + (g\circ f)(t) + (f\circ f\circ g\circ g\circ f)(t)$

Prove that $Sum_g(S) = Sum_g(T)$

---

$f(x) = 3x-2$ and $g(x)=2x+1$

$S(x) = (f\circ g\circ g\circ f\circ f\circ g)(x) = 216 x + 19$ and $s = -19/215$

$T(x) = (g\circ f\circ f\circ g\circ g\circ f)(x) = 216 x - 105$ and $t = 21/43$

$Sum_g(S) = s + (f\circ f\circ g)(s) + (g\circ f\circ f\circ g)(s) = -19/215 -127/215 -39/215 = -37/43$

$Sum_g(T) = (f)(t) + (g\circ f)(t) + (f\circ f\circ g\circ g\circ f)(t) = -23/43 -3/43-11/43 = -37/43$

---

A visual approach

$f(x) = 3x-2$ (or any linear function)

$g(x)=x/5+1$ (or any other linear function)

Then

$ \color{red}{215/98 \to_g} \color{blue}{141/98 \to_f 227/98 \to_f} \color{red}{485/98 \to_g 195/98 \to_g} \color{blue}{137/98 \to_f} 215/98 (again)$

Obs: $215/98$ is the fixed point of $(f\circ g\circ g\circ f\circ f\circ g)(x)$

The reversed cycle is

$ 177/98 \color{red}{_g\leftarrow 395/98} \color{blue}{_f\leftarrow 197/98 _f\leftarrow 131/98} \color{red}{_g\leftarrow 165/98 _g\leftarrow 335/98} \color{blue}{_f\leftarrow 177/98} (again)$

Obs: $177/98$ is the fixed point of $(g\circ f\circ f\circ g\circ g\circ f)(x)$

why this happens?

$ \color{red}{215/98 + 485/98 + 195/98 = 395/98 + 165/98 + 335/98}$

$\color{blue}{141/98 + 227/98 + 137/98 = 197/98 + 131/98 + 177/98} $

Answer 1

Consider a composition of functions $f_i, i=1$ to $n$ with $f_i(x)=a_i x + b_i$

Then $f_1 \circ \dots \circ f_n (x) = \left(\prod_{i=1}^n a_i \right) x + \sum_{k=1}^n \left(\prod_{i=1}^{k-1} a_i \right) b_k $

So the fixed point is:

$$\frac{ \sum_{k=1}^n \left(\prod_{i=1}^{k-1} a_i \right) b_k } {1- \left(\prod_{i=1}^n a_i \right)}$$

Each term in the sum $Sum_g$ is going to be a fixed point of some cyclic permutation of the composition. $\prod_{i=1}^n a_i$ is preserved by cyclic shift and reflection, so we can ignore the denominator.

Thus each of the two sums is expressed as a sum over pairs of points in the composition (or its reflection), the first of which much has $g$ applied to it and the second of which can have anything applied to it. The term corresponding to a pair is the product of the slopes of the linear functions in between, times the intercept of the last one.

Thus we can divide into pairs where the second has $g$ applied to it and pairs where the second has $f$ applied to it. The first case is completely symmetric, so it is the same reflected and unreflected. The second case is more complicated. In the $S$, terms come from sequences beginning in $g$ and ending in $f$. In the $T$, the term comes from the sequences beginning in $f$ and ending in $g$. In both cases, the contribution of a term depends only on the number of $f$s and $g$s between them. Thus, we need the following combinatorial lemma:

For each cycle of $f$s and $g$s, and for each pair of nonnegative numbers $x$ and $y$, the number of subsequences consisting of a $g$, followed by $x$ $f$s and $y$ $g$s, followed by an $f$, is the same as the number of subsequences consisting of an $f$, followed by $x$ $f$s and $y$ $g$s, followed by a $g$

The proof is by discrete continuity. Arrange all the subsequences of length $x+y+1$ in order, and count the number of $f$s in each. This can increase or decrease by at most $1$ at each step. The first type of subsequence occurs when a subsequence of length $x+y+1$ with $x$ $f$s is followed by one with $x+1$ $f$s. The second type of subsequence occurs when a subsequence of length $x+y+1$ with $x+1$ $f$s is followed by one with $x$ $f$s. These two events must alternate, so must occur equally often.