In trying to answer (my own) recent question I'm looking for the name for the following type of self-composition of a function.

  • Let's define an infinite set of fixed coefficients $\{a_0,a_1,...\}$
  • Let us assume the domain for the function in question $ \mathbb N $
  • Let $g(n)$ be some simple function on $n$, say for example $g(n)=n$

Then let us define the self-composing of $f(n)$ with iteration-index denoted as $f^{\circ h}(n)$ by the following scheme:

$$ \begin{array} {} f^{\circ 0}(n) &= g(n) \\ f^{\circ h}(0)&=0 \\ f^{\circ h+1}(n) &= a_0 f^{\circ h}(n) + a_1 f^{\circ h}(n-1) + ... + a_{n-1} f^{\circ h}(1)\\ \end{array}$$

Example: if $a_0=a_1=...=a_k=...=1 $ and $g(n)=n$ then we have for $f^{\circ 1}(n)$ the sum-of-natural-numbers up to $n$, for $f^{\circ 2}(n)$ the sum-of-sums and so on.

Q: Is there a canonical name for this type of self-composition?

It's surely not "iteration"; I looked for "convolution" but this seems to be different - I'm without an idea what other term I could look for.


1 Answer 1


This can be written in terms of convolutions: For two functions $u,v\colon\mathbb{Z}\rightarrow\mathbb{R}$ you can define the convolution product formally as $$ u*v(k)=\sum_{i\in\mathbb{Z}}u(i)v(k-i). $$ In general this series does not converge in any sense, but assuming that $u(j)=v(j)=0$ for $j<0$, it is actually a finite sum for every $k\in\mathbb{Z}$ and for $k<0$ we even have $u*v(k)=0$. This means that the convolution restricts to product on $R:=\{u\colon\mathbb{Z}_{\ge0}\rightarrow\mathbb{R}\}$, in the sense that it makes $(R,+,*)$ a commutative ring. (Which is ismorphic to $\mathbb{R}[[x]]$, the ring of formal power series.)

Now in your case you have some $a\in R$ defined by $a(j)=a_j$ and start with an arbitrary $g\in R$. Then $f^{\circ 1}(k)=a*g(k)$ for $k\ge 1$ and $f^{\circ0}(0)=0.$ But if $v\in R$ satisfies $v(0)=0$ also $a*v(0)=0$, hence from there on it is just convolution: $f^{\circ 2}=a*f^{\circ 1}$ and so on. If you aready start with a function $g\in R$ with $g(0)=0$, then $$ f^{\circ h}=(a*\dots*a)*g=:a^{*h}*g. $$

  • $\begingroup$ Ah, good so! But can we go so far to say directly: "this is a self-convolution" (instead of saying "we can express this in terms of convolution")? I thought it might exist some technical term which is associated to this special form... $\endgroup$ Commented Apr 15, 2018 at 9:57
  • 1
    $\begingroup$ Well, only $a$ gets convoluted with itself, not $g$. And yes there is a term for that, $a^{*n}=a*\dots*a$ (n-times) is called the $n$-fold convolution power. $\endgroup$
    – Jan Bohr
    Commented Apr 15, 2018 at 13:44
  • $\begingroup$ Jan, thanks for your answer. I've looked at the wp-entry - difficult for me to "decode" .. so I'm not yet really convinced that "convolution power" is the best technical term to describe that self-composition. But I've not yet found a "better" one and also no one else stepped in so I'll "accept" your answer to close-the-case and at least have your suggestion as a guide how to look further around. $\endgroup$ Commented Apr 18, 2018 at 8:55
  • $\begingroup$ You're welcome. Though I don't quite understand why you insist on the term "self-composition". Given any function $F\colon S\rightarrow S$ (on a set $S$), the self compositions would be $F\circ F, F\circ F \circ F$ and so on and I would denote this $F^{\circ n}$. This does not happen at the level of functions in $R$, but rather on the level of functions acting on $R$, specifically you could put $F\colon R\rightarrow R, F(u):=a*u$, then $F^{\circ n}(u) = a^{*n}*u$. $\endgroup$
    – Jan Bohr
    Commented Apr 18, 2018 at 9:11
  • $\begingroup$ The reason I continue so far to use the term "self-composition" is that I understand it in a more (or even most) general form as "any polynomial or series where the function is reintroduced as argument " (or so...) Of course to avoid infinite recursion we need the function at varying arguments (or different powers of the function) at the coefficients of the polynomial/series. This is basically my intuitive understanding of such a general term "self-composition" - perhaps there is some triviality which makes this understanding messy and I didn't notice it yet... I'd try to change it then... $\endgroup$ Commented Apr 18, 2018 at 9:23

You must log in to answer this question.

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