2013 AMC 12A Problem 7

The sequence S_1, S_2, S_3, \cdots, S_{10} has the property that every term beginning with the third is the sum of the previous two. That is, S_n = S_{n-2} + S_{n-1} \text{ for } n \ge 3. Suppose that S_9 = 110 and S_7 = 42. What is S_4?

\textbf{(A)}\ 4\qquad\textbf{(B)}\ 6\qquad\textbf{(C)}\ 10\qquad\textbf{(D)}\ 12\qquad\textbf{(E)}\ 16\qquad

Full credit goes to MAA for authoring these problems. These problems were taken on the AOPS website.