Consider these sequences in Sloane:

A001519, a(n) = 3*a(n-1) - a(n-2), '5x^2-4 is a square'
A001835, a(n) = 4*a(n-1) - a(n-2), '3x^2-2 is a square'
A004253, a(n) = 5*a(n-1) - a(n-2), 'x^2 - 5xy + y^2 + 3 = 0'
A001653, a(n) = 6*a(n-1) - a(n-2), 'Numbers n such that 2*n^2 - 1 is a square' etc.

Generally, a(n) = k*a(n-1) - a(n-2), with a(0) = 1, a(1) =1

As the quotes show, there is an exuberance of different algebraic forms given for the various sequences but there is actually a relatively straightforward formula that applies equally to all of them, with only the variable k at large.

What is it?

Jer,

Your initial insight is spot on.

You just need a little more work with the second part. I suggest you think in terms of the squares a,b, the variable k, and constants.