# Sum of terms in a composition cycle

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}$

-
What is the question? –  M Turgeon Jul 3 '13 at 18:35
@MTurgeon The question is clearly stated. Very formally: Let $f,g$ be any linear functions from $\mathbb R$ to itself. If $h$ is a function obtained by composing $f,g$, in any order, say $h=j_1\circ j_2\circ\dots \circ j_n$, where each $j_i$ is $f$ or $g$; and $s=s_h$ is the fixed point of $h$, then we can associate a cycle to $h,s_h$ by considering the finite sequence $a_0=s_h, a_1=j_n(s_h)$, $a_2=j_{n-1}\circ j_n(s_h),\dots$, $a_n=j_1\circ\dots\circ j_n(s_h)=s_h$. (Note $a_i=a_i(h)$ depends on $h$.) Define $\mathrm{Sum}_g(h)$ as the sum of the $a_i$ with $i<n$ such that $j_{n-i}=g$. (Cont.) –  Andres Caicedo Jul 3 '13 at 18:47
@MTurgeon Now, let $S$ be obtained by composing $f,g$ in any order, and let $T$ be the result of composing in the reverse order, so if $S=j_1\circ\dots \circ j_n$, then $T=j_n\circ\dots \circ j_1$. The question is: Prove that $\mathrm{Sum}_g(S)=\mathrm{Sum}_g(T)$. –  Andres Caicedo Jul 3 '13 at 18:49
@MTurgeon If the question is stated as: "Is it true that ... ?", would that make it acceptable? (I could edit it accordingly, if that is the issue.) I'd bet the OP came up with this question on their own, so there is not much more context to give. Even writing out the examples as they did is way more than we see in the typical questions on this site. –  Andres Caicedo Jul 3 '13 at 19:14
@MTurgeon I really consider this the wrong question to start your crusade for details on questions. The worked example (and indeed, even its typesetting) shows nontrivial effort to an extent that it is safe to assume that OP is interested in knowing the answer beyond "it's my homework". –  Lord_Farin Jul 3 '13 at 19:57

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.

-
Thank you very much for de answer. Tomorrow I will try to understand. I'm going to sleep now. –  Federico Jul 4 '13 at 5:47
@AndresCaicedo Thank you very much for un-hold my question. –  Federico Jul 4 '13 at 19:54