# Can Mathematica return the closed forms of 'arbitrary' function compositions?

I have only just downloaded Mathematica, so I am entirely new to this software.

Here is what I am trying to do:

If $$f(x) = \frac{x}{2}$$ is an example function, and $$f^{(n)}(x)$$ is the composition of $$f$$ with itself $$n$$ times, then I know I can write $$f^{(n)}(x) = \frac{x}{2^n}$$.

Now, is there some way I can provide $$f(x)$$ to Mathematica and get $$f^{(n)}(x)$$ as my result with $$x$$ and $$n$$ as symbolic variables?

The most complex functions I would be composing in this manner all have the form $$\frac{(a \cdot x + c)}{d}$$, so I am also hoping that the software is powerful enough to, at least, introduce and manipulate sigma notations where necessary.

My guess is that there might be certain complicated functions for which it becomes infeasible to condense their compositions, so it might be too much to ask for the solution to be truly arbitrary. But for the sort of functions I'm dealing with, I feel this concern does not apply.

I think as much because I have already worked out a few by hand. If there was software that could do them faster and with less errors then, I would rather it did most of the work.

• f[x_] = x/2; Nest[f, x, 5]. g[x_] = (a x + c)/d; Nest[g, x, 5] Commented Mar 28 at 21:05
• f[n_, x_] = RSolveValue[{a[n] == a[n - 1]/2, a[1] == x/2}, a[n], n] Commented Mar 28 at 21:13

\$Version

(* "14.0.0 for Mac OS X ARM (64-bit) (December 13, 2023)" *)

Clear["Global*"]

f[n_, x_] = RSolveValue[{a[n] == a[n - 1]/2, a[1] == x/2}, a[n], n]

(* 2^-n x *)

g[x_] := (a*x + c)/d

seq = Rest@NestList[g, x, 5] // Simplify

(* {(c + a x)/d, (a c + c d + a^2 x)/d^2, (a^2 c + a c d + c d^2 + a^3 x)/d^3, (
a^3 c + a^2 c d + a c d^2 + c d^3 + a^4 x)/d^4, (
a^4 c + a^3 c d + a^2 c d^2 + a c d^3 + c d^4 + a^5 x)/d^5} *)

f[a_, c_, d_, n_, x_] = FindSequenceFunction[seq, n] // Simplify

(* (c (-1 + (a/d)^n))/(a - d) + (a/d)^n x *)


This reduces to the first example

f[1, 0, 2, n, x] == f[n, x]

(* True *)


EDIT: Alternatively,

f[a, c, d, n, x] ==
(RSolveValue[{h[n] == (a*h[n - 1] + c)/d, h[1] == (a*x + c)/d}, h[n],
n] // Simplify)

(* True *)


There is a function, Composition, that will solve your issue. The only problem is that it needs explicit arguments. That means we need to feed it $$n$$ times the function: f., where $$n$$ is unknown at the time of definition. Therefore, we need a delayed definition. We can create a table of $$n$$ functions using Table. To feed them as arguments we need Apply:

f0[x_] = x/2;
fn[f_, n_] := (Composition @@ Table[f, n])[x]


To test it:

fn[f0, 3]

x/8
`