On the Diophantine equation $U_n-b^m=c$

Let $(U_n{)}_{n\in \mathbb{N}}$ be a fixed linear recurrence sequence defined over the integers (with some technical restrictions). We prove that there exist effectively computable constants $B$ and $N_0$ such that for any $b,c\in \mathbb{Z}$ with $b>B$ the equation $U_n-b^m=c$ has at most two distinct solutions $(n,m)\in {\mathbb{N}}^2$ with $n\ge N_0$ and $m\ge 1$. Moreover, we apply our result to the special case of Tribonacci numbers given by $T_1=T_2=1$, $T_3=2$ and $T_n=T_{n-1}+T_{n-2}+T_{n-3}$ for $n\ge 4$. By means of the LLL-algorithm and continued fraction reduction we are able to prove $N_0=1.1\cdot {10}^{37}$ and $B=e^{438}$. The corresponding reduction algorithm is implemented in Sage.