You probably really want to use RSolve[] instead. The code

RSolve[a[j] + a[1 + j] == a[-2 + j] + a[-1 + j], a[j], j]

returns

{{a[j] -> (-1)^j*C[1] + (-1)^j*j*C[2] + C[3]}}

You probably really want to use a[j] and RSolve[] instead. The code

RSolve[a[j] + a[1 + j] == a[-2 + j] + a[-1 + j], a[j], j]

returns

{{a[j] -> (-1)^j*C[1] + (-1)^j*j*C[2] + C[3]}}

But you may still want to do it your way. The code

Solve[ a[j] + a[j + 1] == a[j - 1] + a[j - 2], a[j]]

returns

{{a[j] -> a[-2 + j] + a[-1 + j] - a[1 + j]}}

which may be what you want. A third alternative mentioned in comments is to use Indexed[a,j] instead of a[[j]]. The function Indexed[] was introduced in 2014 with version 10.0 of Mathematica.