YES
O(n)
TRS:
 {
             sqr(0()) -> 0(),
             sqr(s()) -> s(),
             terms(N) -> cons(recip(sqr(N))),
             dbl(0()) -> 0(),
             dbl(s()) -> s(),
          add(0(), X) -> X,
          add(s(), Y) -> s(),
        first(0(), X) -> nil(),
  first(s(), cons(Y)) -> cons(Y)
 }
 Natural interpretation:
  Strict:
   {
               sqr(0()) -> 0(),
               sqr(s()) -> s(),
               terms(N) -> cons(recip(sqr(N))),
               dbl(0()) -> 0(),
               dbl(s()) -> s(),
            add(0(), X) -> X,
            add(s(), Y) -> s(),
          first(0(), X) -> nil(),
    first(s(), cons(Y)) -> cons(Y)
   }
  Weak:
   {}
  Interpretation class: stronglylinear
  [first](X1, X0) = + 1*X0 + 1*X1 + 2
  [nil] = + 0
  [add](X1, X0) = + 1*X0 + 1*X1 + 2
  [dbl](X0) = + 1*X0 + 1
  [s] = + 0
  [0] = + 0
  [terms](X0) = + 1*X0 + 2
  [sqr](X0) = + 1*X0 + 1
  [recip](X0) = + 1*X0 + 0
  [cons](X0) = + 1*X0 + 0
  
  Qed