  Let $F$ be an integral linear recurrence, $G$ be an integer-valued polynomial
splitting over the rationals, and $h$ be a positive integer. Also, let
$\mathcal{A}_{F,G,h}$ be the set of all natural numbers $n$ such that
$\gcd(F(n), G(n)) = h$. We prove that $\mathcal{A}_{F,G,h}$ has a natural
density. Moreover, assuming $F$ is non-degenerate and $G$ has no fixed
divisors, we show that $\mathbf{d}(\mathcal{A}_{F,G,1}) = 0$ if and only if
$\mathcal{A}_{F,G,1}$ is finite.
