Optimal Decay for Linear Recurrences