Recursive integer solution of the equation: $a^2-2b^2=\pm 1$

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.$