How to solve an equation with a nested function

Question

I have the equation

f[f[x]] == 28 + 9 x

How can I solve this for f[x]? I note that this post relates to the topic, but Wolfram|Alpha doesn't work for my equation. So is there a method that can do it?

Answer 1

As the link you provided in your question shows, there is no unique solution. For example (and illustration), assuming a form (linear function) yields 2 solutions:

lhs = CoefficientRules[Nest[a # + b &, x, 2], x]
rhs = CoefficientRules[28 + 9 x, x]
{f1, f2} = 
 a # + b & /. 
  Solve[{({1} /. lhs) == ({1} /. rhs), ({0} /. lhs) == ({0} /. rhs)}, {a, b}]

yields:

{-3 #1 - 14 &, 3 #1 + 7 &}

Testing:

Simplify[Nest[f1, x, 2]]
Simplify[Nest[f2, x, 2]]

Both yield

28 + 9 x

Answer 2

It is interesting to see if there are some slightly more general solutions. For example, by assuming that the function has a fixed point for some unknown value c we can do a series expansion to various orders:

f[f[x]] == 28 + 9 x
Series[%, {x, c, 6}]
% //. f[c] -> c
LogicalExpand[%]
Reduce[%]
FullSimplify[%]
Solve[%]

which gives

$\left\{\left\{c\to -\frac{7}{2},f'\left(-\frac{7}{2}\right)\to -3,f''\left(-\frac{7}{2}\right)\to 0,f^{(3)}\left(-\frac{7}{2}\right)\to 0,f^{(4)}\left(-\frac{7}{2}\right)\to 0,f^{(5)}\left(-\frac{7}{2}\right)\to 0,f^{(6)}\left(-\frac{7}{2}\right)\to 0\right\},\left\{c\to -\frac{7}{2},f'\left(-\frac{7}{2}\right)\to 3,f''\left(-\frac{7}{2}\right)\to 0,f^{(3)}\left(-\frac{7}{2}\right)\to 0,f^{(4)}\left(-\frac{7}{2}\right)\to 0,f^{(5)}\left(-\frac{7}{2}\right)\to 0,f^{(6)}\left(-\frac{7}{2}\right)\to 0\right\}\right\}$

This obviously supports the idea that the only analytic functions with a fixed point satisfying the equation are linear.

Answer 3

Here's my attempt to construct a non-analytic solution. The idea is to use one of the analytic solutions in the accepted answer when x belongs to a set of points reachable through successive application of either analytic solution or their inverses, and the other solution otherwise. This set must not be equal the set of reals, otherwise the solution just reduces to one of the analytic solutions. I thought of a way to show this set is countable, and therefore can't be equal the real set, but realized it's easier to show by counterexample after finding the set.

I start with a couple of observations to facilitate finding this set. The first is the convenient commutativity of f1 and f2:

Simplify[f1[f2[x]] == f2[f1[x]]]

which means any sequence of f1 and f2 is equivalent to one with the same total number n1 and n2 of f1 and f2 calls respectively, e.g. n1 f1 calls followed by n2 f2 calls. This commutativity also implies the inverses are commutative, and sequences of InverseFunction[f1] and InverseFunction[f2] can be similarly ordered.

The second is the nth application of f1 or f2 is the sum of a constant term, which is a geometric series of length n, and a linear term, which is the nth term in another geometric series. These terms can be computed by hand, but Mathematica gives a convenient way to do so:

s1[x_]=FindSequenceFunction[NestList[f1,x,3]];
s2[x_]=FindSequenceFunction[NestList[f2,x,3]];

It can be shown the nth application of InverseFunction[f1] or InverseFunction[f2] to x is equal s1[x][-n] or s2[x][-n] respectively.

With these results, the set of points that can be reached from x0 satisfies:

criteria = Simplify[Reduce[{s2[s1[x][n1]][n2] == x0}, {n1, n2}], 
                    Assumptions -> {{n1, n2} \[Element] Integers, {x, x0} \[Element] Reals}]

$$ \left(x=-\frac{7}{2}\land \text{x0}=-\frac{7}{2}\right)\lor \left(c_1\in \mathbb{Z}\land 2 x+7\neq 0\land 2 \text{x0}+7\neq 0\land \\ \log (3) (\text{n1}+\text{n2})-2 i \pi c_1=\log \left(-\frac{9 (-1)^{\text{n1}} (2 \text{x0}+7)}{2 x+7}\right)\right) $$

Unless x0 is the fixed point -7/2, we can reach x if there are integers n1 and n2 satisfying this equation.

Here, the only imaginary terms are $2i\pi c_1$ and from the log on the right-hand side. Since x and x0 are real, the imaginary part of the log can only be 0 or $i\pi$. The former requires $c_1=0$, while the latter cannot be satisfied for any $c_1\in \mathbb{Z}$. We can therefore set $c_1=0$.

Moreover, given x and x0, there are only two possibilities for the log, one with n1 even, and one with n1 odd. Regardless of whether n1 is even or odd, n2 is arbitrary, so n1+n2 need only be integral and can be either even or odd:

condition[x_,x0_]=And @@ Reverse @ (Or @@ (n\[Element]Integers/.Simplify[
          Solve[criteria/.n1+n2->n,n][[1]],Assumptions->{x,x0}\[Element]Reals]/.C[1]->0/.#& 
          /@ {n1->1,n1->2}))

$$ x\neq -\frac{7}{2}\land \text{x0}\neq -\frac{7}{2}\land \left(\frac{\log \left(-\frac{9 (2 \text{x0}+7)}{2 x+7}\right)}{\log (3)}\in \mathbb{Z}\lor \frac{\log \left(\frac{9 (2 \text{x0}+7)}{2 x+7}\right)}{\log (3)}\in \mathbb{Z}\right) $$

This condition is sufficient to show the set of points that can be reached is not the real set, e.g. condition[1,0] returns False, showing x=1 cannot be reached from x0=0.

With this condition, we construct a non-analytic solution, as f1[x] for x satisfying the condition, and f2[x] otherwise:

f[x_, x0_] = Piecewise[{{f1[x], condition[x, x0]}}, f2[x]];

Testing:

ff=FullSimplify[f[f[x,x0],x0],Assumptions->{x,x0}\[Element]Reals]

unfortunately gives a long condition for 28+9x I have to simplify by brute force:

(ff[[1,1,2]]/.Log[x_]:>Log[Factor[x]]//PowerExpand//ExpandAll//FullSimplify)/.
(Log[x_]-Log[y_]:>Log[x/y])/.I \[Pi]+Log[x_]->Log[-x]/.
{x_\[Element]Integers->integerQ[x],x_\[NotElement]Integers:>!integerQ[x]}//FullSimplify

True

Answer 4

Inspired by @obsolesced, it is simple to find solutions based on any set that is mapped to itself by f1 and f2. For example, let

S = {q1 + q2 Sqrt[2]}  for {q1, q2} rational

then

f[x] = f1[x]   x in S
f[x] = f2[x]   x not in S

satisfies the required functional relation. It is continuous nowhere (except x = -7/2) and S is countably infinite and its complement uncountably infinite.

Alternatively, make S the Algebraic numbers, then its complement is the Transcendentals - both uncountably infinite.

It would be interesting to know if there are any solutions to the functional equation with f[x] not in {f1[x],f2[x]}.