  In this paper we consider the Diophantine equation $ V_n - b^m = c $ for
given integers $ b,c $ with $ b \geq 2 $, whereas $ V_n $ varies among
Lucas-Lehmer sequences of the second kind. We prove under some technical
conditions that if the considered equation has at least three solutions $ (n,m)
$, then there is an upper bound on the size of the solutions as well as on the
size of the coefficients in the characteristic polynomial of $ V_n $.
