We develop a general framework for finding all perfect powers in sequences derived
via shifting non-degenerate quadratic Lucas-Lehmer binary recurrence sequences by
a fixed integer. By combining this setup with bounds for linear forms in logarithms
and results based upon the modularity of elliptic curves defined over totally real
fields, we are able to answer a question of Bugeaud, Luca, Mignotte and the third
author by explicitly finding all perfect powers of the shape F-k +/- 2 where F-k is
the k-th term in the Fibonacci sequence.