Relating the roots of polynomials to the solution sets of certain functional equations Consider a functional equation of the following form:
$$\sum_{k=0}^n a_k\,\underbrace{f(f(\cdots f}_{k}(x)\cdots )=0\quad \big(f:\,\mathbb{R}\to\mathbb{R},\;a_i\in \mathbb{R},\;\text{and}\;f^0=\text{id}\big)$$
A well-known strategy for producing continuous solutions to this is to take the real roots $\lambda_1,\,\cdots,\, \lambda_m\;-$ if they exist $-$ of the characteristic polynomial $\mathcal{P}(z)=\sum_{k=0}^n a_kz^k$, and set $f_i(x)=\lambda_i x$ for each $1\leq i\leq m$ (note: this does not necessarily generate a full solution set).
It is natural to then explore the case where $\mathcal{P}$ has no roots in $\mathbb{R}$. After fiddling with a couple problems, it seems conceivable that this would immediately imply an absence of continuous solutions altogether: my question is whether this is indeed the case.
 A: Here is an incomplete answer, that hopefully should be useful to conclude in either direction. 
For $f:\mathbb{R}\rightarrow\mathbb{R}$ and $P(z):=\sum_{j=0}^n a_j z^j\in\mathbb{R}[z]$ let's denote $f^{(j)}$ the $j$-fold composition and $P[f]:=\sum_{j=0}^n a_j f^{(j)}.$
Here are a few facts about a continuous solution $f:\mathbb{R}\rightarrow\mathbb{R}$ to the functional equation $P[f]=0,$ that should be helpful.
0. If $0$ is not a root of $P$, then $f$ is a homeo, and the inverse of
$f$ satisfies the functional equation $R[f^{-1}]=0$, with the
reciprocal polynomial of $P$, $R(z):=z^nP(1/z)$.
Indeed, from the equation we have a continuous  left-inverse $g:\mathbb{R}\rightarrow\mathbb{R}$ of the form $g:=Q[f]$, so $f$ is injective; but for continuous functions on $\mathbb{R}$, $g\circ f=\mathrm{id_\mathbb{R}}$ also implies that $f$ is unbounded from above and from below, thus surjective. 
1. If $1$ is not a root of $P$, then $f$ has no nonzero fixed point. In particular, $f(x)-x$ has constant sign on $\mathbb{R}_+$ and on $\mathbb{R}_-$
Indeed, $f(x_0)=x_0$ implies again from the equation $P(1)x_0=0$ whence $x_0=0$.
Then, a negative answer to the question would follow from the following statement:

Lemma (Conjectured). Let $(x_m)_{m\ge0}$ be a sequence solution of a linear recurrence $\sum_{j=0}^n a_j x_{m+j}=0,$ with $P(z):=\sum_{j=0}^n a_j
> z^j\in\mathbb{R}[z]$ (and w.l.o.g. $a_na_0\neq0$). Then:
i) If  $x_m$ has constant sign , then $P$ has a positive real root.
ii) If  $x_m$ has alternate sign , then $P$ has a negative real root.

If true, a consequence would be: 
2. If for some  $x_0\neq 0$ the orbit   $x_m:=f^{(m)}(x_0)$ has (i) constant sign, then $P$ has a non-negative solution. If (ii) it has alternate sign, then $P$ has a non-positive real root.
Indeed, again from the equation, the sequence $(x_m)_m$ is a solution of the linear recurrence  $\sum_{j=0}^n a_j x_{m+j}=0,$ and both claims follows from the conjectured lemma.
Finally, let's prove how this would imply that $P$ has a real root, assuming that there exists a continuous solution to $P[f]=0$. If $0$ is not a root of $P$, by (0) $f$ is either increasing or decreasing. In the first case, all orbits would be monotone, thus with (eventually) constant sign, and $P$ has a positive real root by (2i). In the latter case, $f$ is a decreasing homeomorphism that fixes $0$. But then all orbits have alternate sign, and we conclude by (2ii) that $P$ has a negative real root.
Trying to prove the lemma. The sequence $(x_m)$ has a representation $x_m:=\sum_{\lambda\in\Lambda}p_\lambda(m)\lambda^m$, where $\Lambda$ is the set of roots of $P$ and $p_\lambda$ are (complex) polynomials with $\mathrm{deg}(P_\lambda)< \mathrm{mult}(\lambda)$. To put in evidence the principal term, this can be written in the form
$x_m:=m^s\rho^m \Big( \sum_{k=1}^r b_k \cos(m\omega_k+\phi_k)+o(1)\Big)$ as $m\to\infty$. If $P$ has no positive solutions,   we have $0 < \omega_k<2\pi$, which in several cases implies infinitely many changes of sign for $x_m$ . The claim (ii) follows from (i). Indeed, in this case the sequence $y_m:=(-1)^m x_m$ verifies the assumption (i) for the polynomial $P(-z)$, and $P$ has a negative root.
A: It is known that every polynomial having no positive root has a multiple with nonnegative coefficients only. So we may replace $\mathcal P$ by such multiple $\mathcal Q$ (surely, $f$ satisfies the corresponding equation as well).
Now, since $\mathcal P$ has no real roots, the equality $f(x)=x$ is impossible; thus $f(x)-x$ has constant sign, say $f(x)>x$ for all $x\in\mathbb R$ (otherwise we may replace $f$ by $g(x)=-f(-x)$). Take any positive $x$; then $f^k(x)>0$ as well, so when we substitute this $x$ into our equation constructed for $\mathcal Q$ we get the sum of positive terms only. A contradiction.
For completeness, let me sketch the proof of the fact used at the beginning. It suffices to prove it for polynomials of the forms $z+a$ (for positive $a$, it is trivial) and $z^2+az+b$ (having two non-real roots $z_0$ and $\overline z_0$). [SIMPLIFIED] For the second one, observe that for some positive integer $k$ the number $z_0^k$ has  negative real part; then a polynomial $(z^k-z_0^k)(z^k-\overline z_0^k)$ is what we want. 
A: Here is a partial solution, which allows to conclude in many cases. First it is easy to see that $f$ is injective (unless $a_0=0$, but this has been excluded by the assumption), so that $f$ is monotonic. Using the relation, one can also see that the image of $R$ is $R$. It is possible to replace $f$ by its inverse, which means that the $\lambda_j$'s are replaced by $1/\overline \lambda_j$'s. 
Next, let $u_k(x)= f^{(k)}(x)$. It satisfies a recurrence equation, so that, if all $\lambda_j$'s are simple, for instance, $u_k(x) =b_1(x)\lambda_1^k+\cdots +b_n(x)\lambda_n^k$. Let us assume more, that is, $|\lambda_n|>1$ is larger than the other ones (we could as well assume that one is smaller than all other ones, replacing $f$ by its inverse). This forces $\lambda_n$ to be real or $b_n(x)$ to be identically $0$, which means that we can replace $n$ by $n-1$ and have a recurrence argument. If this root is not simple, the reasoning is more or less the same. The reasoning does not work when there are two conjugate roots instead of one, with larger modulus. 
On the other hand this strategy does not work at all when all roots are of modulus $1$, which only occurs when $n$ is even. Consider the simplest case, that is, $n=2$ and $a_0=a_2=1$, $a_1=2\cos \alpha$. We know that the sequence $u_k$ is bounded and does not have a limit. We get a contradiction if we prove that it is monotonic. We know that $f\circ f$ is increasing, so is $f$ if $\cos\alpha>0$. So, if $f(x)>x$, the sequence is increasing. If $f(x)<x$, the sequence is decreasing. When $\cos\alpha<0$, the sequence of odd (resp. even) terms is monotonic, which allows also to get a contradiction. This will probably work in the general case of roots of modulus $1$.
A: Let $P(z)=a_nz^{n}+\ldots+a_0$ denote the characteristic polynomial associated to this functional equation.  We prove that if 
  $P$ does not have real roots, then the functional equation does not have a continuous solution.  We may assume that $a_0\neq 0$, else $0$ would be a 
  root of $P$.  
Suppose there is a continuous function $f$ satisfying the given functional equation.  As observed in the other answers, $f$ must be 
  injective, and therefore monotone.  It follows that $F(x)=f(f(x))$ is a monotone increasing function.  Pick any point $x_0$ and look at its orbit 
  under $F$; that is, the sequence $x_k =F(x_{k-1})$.  Since $F$ is monotone increasing, we see that the sequence $x_k$ is either monotone 
  increasing, or monotone decreasing.  In either case, $x_k$ maintains sign eventually.  By starting at a point where the sign has stabilized, 
  we see that there exists a starting point $x_0$ such that the orbit $x_k$ is always of one sign.   Pick such a starting point $x_0$.  
Put $y_0=x_0$ and $y_k=f(y_{k-1})$, so that $y_{2k}=x_k$.  Since $y_k$ satisfies a linear recurrence (with characteristic function $P$) we see 
  that 
  $$ 
  {\mathcal F}(z) = \sum_{k=0}^{\infty} y_k z^k = \frac{Q(z)}{R(z)}, 
  $$ 
where $R(z)=z^{n}P(z^{-1})$ and for some polynomial $Q(z)$.   Thus 
$$ 
{\mathcal G}(z) = {\mathcal F}(z)+{\mathcal F}(-z) = 2 \sum_{k=0}^{\infty} x_k z^{2k} = \frac{Q(z)}{R(z)}+\frac{Q(-z)}{R(-z)}.
$$ 
Now note that ${\mathcal G}(z)$ is a power series all whose coefficients are either all non-positive or all non-negative.  Recall Pringsheim's theorem: 
If the power series $h(z)=\sum_{n=0}^{\infty} a_n z^n$ has non-negative coefficients and radius of convergence $\rho$ then $\rho$ is a singularity of the 
function $h$.   Applying Pringsheim's theorem to ${\mathcal G}(z)$ (or $-{\mathcal G}(z)$) we conclude that $R(z)$ or $R(-z)$ must have a zero at $\rho$, 
the radius of convergence of ${\mathcal G}$.  Then $P$ has a zero at $1/\rho$ or $-1/\rho$, completing our proof.
