Recursive integer solution of the equation: $a^2-2b^2=\pm 1$ 
Consider $a_0=a_1=1$ and $a_k=2a_{k-1}+a_{k-2}$ for $k\ge2$.
  Similarly $b_0=0,b_1=1$ and $b_k=2b_{k-1}+b_{k-2}$ for $k\ge 2$. 

I want to prove that for every natural $k$ the pair $(a_k,b_k)$ is an integer solution of the equation $a^2-2b^2=\pm 1$ where $a,b\in \mathbb Z$. Of course you can find other recursions for other indices (even/odd). This would be ok for me.
Now the idea is to prove it by induction. I tried, but I had some difficulties since by even $k$ we have the solution for $+1$ and for odd $k$ the one for $-1$ and I should prove also this by induction. However I cannot see how since the $a_k,b_k$ are too dependent on the others. Making computations you can see what I mean.

Another idea was to consider two distinct recursions: one for even values of $k$ and another one for odd $k$ and proving by induction the two recursions separately. However I cannot see these recursions. Anyone does?

Does anyone know how to do the induction here?
 A: Hint
You can prove the following claim by induction. Note that this claim is one claim containing 4 equations. We will prove these equations simultaneously. 
Claim
\begin{align}
a_{2m}^2 - 2b_{2m}^2 &= 1\\
a_{2m+1}^2 - 2b_{2m+1}^2 &= -1\\
a_{2m}a_{2m+1} - 2b_{2m}b_{2m+1} &= -1\\
a_{2m-1}a_{2m} - 2b_{2m-1}b_{2m} &= 1\\
\end{align}
Sketch of the proof the claim


*

*First step: You can easily show this for $m=1$.

*Then try to prove this claim for $m+1$ i.e.
\begin{align*}
a_{2m+2}^2 - 2b_{2m+2}^2 &= 1\\
a_{2m+3}^2 - 2b_{2m+3}^2 &= -1\\
a_{2m+2}a_{2m+3} - 2b_{2m+2}b_{2m+3} &= -1\\
a_{2m+1}a_{2m+2} - 2b_{2m+1}b_{2m+2} &= 1\\
\end{align*}
This should be straight forward.
Comment on the straightforwardness
Let me prove the first line:
\begin{align*}
a_{2m+2}^2 - 2b_{2m+2}^2 &= (2a_{2m+1} - a_{2m})^2 - (2b_{2m+1} - b_{2m})^2\\
&= 4a_{2m+1}^2 + a_{2m}^2 -4a_{2m+1}a_{2m} - 8b_{2m+1}^2 - 2b_{2m}^2 + 4b_{2m+1}a_{2m}\\
&= 4(a_{2m+1}^2 -2b_{2m+1}^2) + (a_{2m}^2 -2 b_{2m}^2) - 4(a_{2m}a_{2m+1} - b_{2m}a_{2m+1})\\
&= - 4 + 1 -4\\
&=1
\end{align*}
Note
Sometimes it is hard to do induction over one claim. In cases like this, proving a stronger claim makes the proof easier.
Edit
There were couple of typos about the negative signs. I have fixed them.
A: We can use the fact that
$$a_n=\frac{1}{2} \left(\left(1-\sqrt{2}\right)^n+\left(1+\sqrt{2}\right)^n\right)
\qquad
\text{and}
\qquad
b_n=-\frac{\left(1-\sqrt{2}\right)^n-\left(1+\sqrt{2}\right)^n}{2 \sqrt{2}}.$$
These expressions can be proved by induction (there are also well-known methods to derive the general term of a linear recursive relation. You can read about it for example in Wikipedia.)
Therefore, we have 
$$a_n^2=\frac{1}{4}\left\{\left(1-\sqrt{2}\right)^{2 n}+\left(1+\sqrt{2}\right)^{2 n}+2\left(\left(1-\sqrt{2}\right) \left(1+\sqrt{2}\right)\right)^n\right\}
$$
and
$$2b_n^2=\frac14\left\{\left(1-\sqrt{2}\right)^{2 n}+\left(1+\sqrt{2}\right)^{2 n}-2\left(\left(1-\sqrt{2}\right) \left(1+\sqrt{2}\right)\right)^n\right\}
$$
so
$$a_n^2-2b_n^2=\frac14\left\{4\left(\left(1-\sqrt{2}\right) \left(1+\sqrt{2}\right)\right)^n\right\}
=(-1)^n.$$
EDIT (a method to derive $a_n$): let us define 
$$F(x):=\sum_{n\geq0}a_n\frac{x^n}{n!}.$$
Then clearly $F^{(n)}(0)=a_n$. Now, 
$$F''(x)=\sum_{n\geq0}a_{n+2}\frac{x^n}{n!}
=\sum_{n\geq0}a_{n}\frac{x^n}{n!}+2\sum_{n\geq0}a_{n+1}\frac{x^n}{n!}
=\sum_{n\geq0}a_{n}\frac{x^n}{n!}+2\sum_{n\geq1}a_{n}\frac{x^{n-1}}{(n-1)!}
=F(x)+2F'(x).$$
So $F$ is a function that satisfies the linear second order ODE
$$F''(x)-2F'(x)-F(x)=0$$
and the initial conditions $F(0)=1,F'(0)=1$. Solving the differential equation we obtain
$$F(x)=\frac{1}{2} \left(e^{\left(1-\sqrt{2}\right) x}+e^{\left(1+\sqrt{2}\right) x}\right),$$
so the general form of $a_n$ is achieved after $n$-fold differentiation.
A: I should emphasize that this is just the continued fraction for $\sqrt 2.$
Usually it is not so pretty to combine the $1$ and $-1$ cases in Pell $x^2 - n y^2.$ However: If $$ x^2 - 2 y^2 = \delta  $$ with all integers, then
$$ (x+2y)^2 - 2 (x+y)^2 = - \delta.  $$
That is, take the column vector of integers
$$
\left(
\begin{array}{c}
x \\
y
\end{array}
\right)
$$
The matrix of transformation is
$$
A =
\left(
\begin{array}{rr}
1 & 2 \\
1 & 1
\end{array}
\right)
$$
The fact you are trying to prove is just Cayley-Hamilton for this matrix. The trace is $2$ while the determinant is $-1.$ The characteristic equation is then $\lambda^2 - 2 \lambda - 1,$ or  $\lambda^2 = 2 \lambda + 1.$
$$
\left(
\begin{array}{c}
x_{n+1} \\
y_{n+1}
\end{array}
\right) =
\left(
\begin{array}{rr}
1 & 2 \\
1 & 1
\end{array}
\right)
\left(
\begin{array}{c}
x_n \\
y_n
\end{array}
\right),
$$
$$
\left(
\begin{array}{c}
x_{n+2} \\
y_{n+2}
\end{array}
\right) =
\left(
\begin{array}{rr}
1 & 2 \\
1 & 1
\end{array}
\right)
\left(
\begin{array}{c}
x_{n+1} \\
y_{n+1}
\end{array}
\right),
$$
while $A^2 = 2A + I.$
