Triangular Square Numbers

Python 2, 45 - 4 - 4 = 37

a=1;b=0
exec"a,b=b,34*b-a+2;"*input()
print a

Iterates using the reccurence

f(0) = 1
f(1) = 0
f(k) = 34*f(k-1)-f(k-2)+2

In theory, this supports numbers of any size, but runs in exponential time, so it shouldn't qualify for the bonuses. Should work for numbers of any size. For example, for 100, gives

1185827220993342542557325920096705939276583904852110550753333094088280194260929920844987597980616456388639477930416411849864965254621398934978872054025

A recursive solution uses 41 chars, but shouldn't qualify because it takes exponential time.

f=lambda k:k>2and 34*f(k-1)-f(k-2)+2or~-k

CJam, 12 8 bytes

XUri{_34*@-Y+}*;

Makes use of the recurrence relation from the Wikipedia article.

The code is 16 bytes long and qualifies for both bonuses.

Try it online in the CJam interpreter.

How it works

My code turned out to be identical to xnor's in always every aspect, except that I use CJam's stack instead of variables.

XU               e# Push 1 and 0 on the stack.
                 e# Since 34 * 0 - 1 + 2 = 1, this compensates for 1-based indexing.
  ri{        }*  e# Do int(input()) times:
     _34*        e#   Copy the topmost integer and multiply it by 34.
         @-      e#   Subtract the bottommost integer from the result.
           Y+    e#   Add 2.
               ; e# Discard the last result.

Pyth, 16 - 4 - 4 = 8 bytes

Uses the recursive formula from the OEIS article.

K1uhh-*34G~KGtQZ

It uses the post-assign command which is pretty new and seems really cool. Uses reduce to iterate n-1 times because of 1-based indexing.

K1            Set K=1
u       tQ    Reduce input()-1 times
         Z    With zero as base case
 hh            +2
  -           Subtract
   *34G       34 times iterating variable
   ~K         Assign to K and use old value
    G         Assign the iterating variable.

Seems to be polynomial because it loops n times and does math & assignment each iteration, but I'm not a computer scientist. Finishes n=10000 almost instantly.

Try it here online.