  In this paper, we show that if $(U_n)_{n\ge 1}$ is any nondegenerate linearly
recurrent sequence of integers whose general term is up to sign not a
polynomial in $n$, then the inequality $\phi(|U_n|)\ge |U_{\phi(n)}|$ holds on
a set of positive integers $n$ of density $1$, where $\phi$ is the Euler
function. In fact, we show that the set of $n\le x$ for which the above
inequality fails has counting function $O_U(x/\log x)$.
