16
$\begingroup$

I asked an earlier question on when $32x+32$ is a square number (here) and I got a very clear answer.

Now I am looking to solve for which $x$ the equation $8x^2-4$ results in a square number. When I am trying to solve it I get: $y^2=4(2x^2-1)$ so if we put $y=2w$ then $2x^2-1 = w^2$ and therefore $x=\sqrt{\frac{w^2+1}{2}}$ which is correct.

Only now I need to check when $\frac{w^2-1}{2}$ is a square which goes on recursively. I am looking for Integer solutions for $x$ and $w$. How can I solve this?

$\endgroup$
4
  • 9
    $\begingroup$ You get $w^2 - 2x^2 = -1$. That is a negative Pell equation. $\endgroup$ Jun 15, 2015 at 21:39
  • 1
    $\begingroup$ If it may help, The values of $x$ that results in squared value begin with the series $x=1, 5, 29, 169, 985, 5741, 33461, 195025$. These x values look like they are generated from oeis.org/A001653 $\endgroup$
    – NoChance
    Jun 16, 2015 at 1:56
  • $\begingroup$ you mean (w^2+1)/2 is a square. If so w=5 and w=41 are two values. $\endgroup$
    – Adelafif
    Jun 18, 2015 at 14:49
  • 1
    $\begingroup$ You can find the values of $x$ using: $x = \frac{7 + 5 \sqrt{2}}{2 \sqrt{2}} \Big( 3 + 2 \sqrt{2} \Big)^{n-1} -\frac{7 - 5 \sqrt{2}}{2 \sqrt{2}} \Big( 3 - 2 \sqrt{2} \Big)^{n-1}$. $\endgroup$ Jul 19, 2015 at 13:48

4 Answers 4

7
$\begingroup$

Given the equation $$ 2 n^2 - 1 = ( m - n )^2. $$

From this we can write $$ 2 m n = m^2 - n^2 + 1. $$

Let $$ x = m^2 - n^2, y = 2 m n, z = m^2 + n^2 \Rightarrow x^2 + y^2 = z^2. $$

But $$ y = x + 1, $$

so we obtain $$ x^2 + ( x + 1 )^2 = z^2, $$

which can be written as $$ 2 z^2 - 1 = ( 2 x + 1 )^2, $$

or $$ 2 \big( \underbrace{m^2 + n^2}_{n'} \big)^2 - 1 = \big( \underbrace{ 2 \big[ m^2 - n^2 \big] + 1 }_{m'-n'} \big)^2. $$

So starting with $$ \big( m, n \big) $$

we can "generate" the next pair $(m',n')$ using $$ \big( m', n' \big) = \big( 3 m^2 - n^2 + 1, m^2 + n^2 \big). $$

Note that $m=2$ and $n=1$ yields $$ 2 \cdot 1^2 - 1 = ( 2 - 1 )^2 $$

We can now "generate" the next pairs...

$$ \big( m', n' \big) = \big( 3 \cdot 2^2 - 1^2 + 1, 2^2 + 1^2 \big) = \big( 12 , 5 \big). $$

$$ \big( m'', n'' \big) = \big( 3 \cdot 12^2 - 5^2 + 1, 12^2 + 5^2 \big) = \big( 408 , 169 \big). $$

$$ \big( m''', n''' \big) = \big( 3 \cdot 408^2 - 169^2 + 1, 408^2 + 169^2 \big) = \big( 470832, 195025 \big). $$

The number we are looking for are the numbers $n$, the first given by $$ n = 1\\ n = 5\\ n = 169\\ n = 195025 $$

This are not all numbers, as the is a second method to generate pairs $(m',n')$.

I am still working on the second method.


The general method is given by

$$ 2 x_n^2 - 1 = y_n^2, $$

where both $x_n$ and $y_n$ are integers, then $$ x_n = \frac{7 + 5 \sqrt{2}}{2 \sqrt{2}} \Big( 3 + 2 \sqrt{2} \Big)^{n-1} -\frac{7 - 5 \sqrt{2}}{2 \sqrt{2}} \Big( 3 - 2 \sqrt{2} \Big)^{n-1}. $$

The results are $$ \begin{array}{l|l} n & x_n\\ \hline 0 & 1\\ 1 & 5\\ 2 & 29\\ 3 & 169\\ 4 & 985\\ 5 & 5741\\ 6 & 33461\\ 7 & 195025\\ 8 & 1136689\\ 9 & 6625109\\ 10 & 38613965 \end{array} $$

(need to post how to derive it, but it is long)


The basic idea to derive it:

Given $$ 2 x_n^2 - 1 = y_n^2. $$

Note that $$ \left( \begin{array}{c} x_{n+1} \\ y_{n+1} \end{array} \right) = \left( \begin{array}{cc} 3 & 2 \\ 4 & 3 \end{array} \right) \left( \begin{array}{c} x_n \\ y_n \end{array} \right) $$

and $$ \left( \begin{array}{c} x_0 \\ y_0 \end{array} \right) = \left( \begin{array}{c} 1 \\ 1 \end{array} \right). $$

So $$ \left( \begin{array}{c} x_n \\ y_n \end{array} \right) = \left( \begin{array}{cc} 3 & 2 \\ 4 & 3 \end{array} \right)^n \left( \begin{array}{c} 1 \\ 1 \end{array} \right). $$

Let $\chi$ be the trace of the matrix and $\Delta$ the determinant, then the eigenvalues are given by $\lambda_\pm = \chi/2 \pm \sqrt{\chi^2/4 - \Delta}$.

Then $$ \left( \begin{array}{cc} 3 & 2 \\ 4 & 3 \end{array} \right)^n = \frac{\lambda_+^n - \lambda_-^n}{\lambda_+ - \lambda_-} \left( \begin{array}{cc} 3 & 2 \\ 4 & 3 \end{array} \right) - \lambda_+ \lambda_- \frac{\lambda_+^{n-1} - \lambda_-^{n-1}}{\lambda_+ - \lambda_-} \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) $$

From this follows that $$ x_n = 5 \frac{\lambda_+^n - \lambda_-^n}{\lambda_+ - \lambda_-} - \lambda_+ \lambda_- \frac{\lambda_+^{n-1} - \lambda_-^{n-1}}{\lambda_+ - \lambda_-} $$

and $$ y_n = 7 \frac{\lambda_+^n - \lambda_-^n}{\lambda_+ - \lambda_-} - \lambda_+ \lambda_- \frac{\lambda_+^{n-1} - \lambda_-^{n-1}}{\lambda_+ - \lambda_-}. $$

Working this out we get $$ x_n = \frac{7 + 5 \sqrt{2}}{2 \sqrt{2}} \Big( 3 + 2 \sqrt{2} \Big)^{n-1} -\frac{7 - 5 \sqrt{2}}{2 \sqrt{2}} \Big( 3 - 2 \sqrt{2} \Big)^{n-1}. $$

(I have written this post fast, so forgive me for some typos :)

$\endgroup$
3
$\begingroup$

As Daniel Fischer has said, you end up with $w^2 - 2x^2 = -1$, which is a negative Pell equation. I asked a question very similar earlier. The fundamental and minimal solution is $(w_1, x_1) = (1, 1)$. The rest of the solutions can be solved as convergents of the continued fraction of $\sqrt{2}$. The next solutions are described by the recurrence equations $w_{k+1} = 3w_k + 4x_k,\ x_{k+1} = 2w_k + 3x_k$. This resolves to $x_k = 6x_{k-1} - x_{k-2}$, with $x_0 = 0$. More information here.

$\endgroup$
3
$\begingroup$

Continued Fraction Approach

Suppose $2q^2-1=p^2$. Then $$ \left(\sqrt2-\frac pq\right)\left(\sqrt2+\frac pq\right)=\frac1{q^2}\tag{1} $$ Thus, $$ \left|\sqrt2-\frac pq\right|\lt\frac1{2q^2}\tag{2} $$ The only rational approximations that are this good are Continued Fraction approximations. The continued fraction for $\sqrt2$ is $(1;2,2,2,2,\dots)$. Using the table below, where each column below the line is the sum of the the number above that column times previous column plus the column preceding that: $$ \begin{array}{c|c} &&1&2&2&2&2&2&2\\\hline 0&1&1&3&7&17&41&99&239\\ 1&0&1&2&5&12&29&70&169 \end{array}\tag{3} $$ the first several convergents for this continued fraction are $$ \color{#00A000}{\frac11},\frac32,\color{#00A000}{\frac75},\frac{17}{12},\color{#00A000}{\frac{41}{29}},\frac{99}{70},\color{#00A000}{\frac{239}{169}},\cdots\tag{4} $$ Under- and over-estimates alternate, Thus, the green entries are under-estimates.

Since the numerators and denominators follow the recurrence $$ (S^2-2S-1)a=0\tag{5} $$ where $S$ is the shift operator $Sa_n=a_n+1$, and $(x^2-2x-1)(x^2+2x-1)=x^4-6x^2+1$, the numerators and denominators must also satisfy $$ (S^4-6S^2+1)a=0\tag{6} $$ Therefore, the recurrence for every other numerator and denominator is $$ a_n=6a_{n-2}-a_{n-4}\tag{7} $$

Thus, if we start out with $a_1=1$ and $a_2=5$, then compute successive terms with $$ a_n=6a_{n-1}-a_{n-2}\tag{8} $$ we get all integers so that $8a_n^2-4=4(2a_n^2-1)$ is a square.


Notes
$(1)$: If $q\ne0$, this is equivalent to $2q^2-1=p^2$.
$(2)$: Since $p\ge q$, we actually have $\left|\sqrt2-\frac pq\right|\le\frac1{(1+\sqrt2)q^2}\lt\frac1{2q^2}$. The claim about rational approximations is Theorem $5.6$ from this paper.
$(3)$: This table was generated as described in the preceding paragraph. It is simply using the Wallis Algorithm, in particular Corollary $2.2$, from this paper.
$(4)$: This list simply collects the convergents from table $(3)$ and colors the under-estimates green.
$(5)$: This equation is an operator-based restatement of $a_n=2a_{n-1}+a_{n-2}$.
$(6)$: Any sequence that satisfies the constraint in $(5)$ also satisfies this equation.
$(7)$: This is a restatement of $(6)$, which is a relation among every other element of the sequence. This gives us a recurrence on the numerators and denominators of the under-estimates.
$(8)$: Describe the sequence of denominators for the under-estimates.

$\endgroup$
2
$\begingroup$

-$a(n) = 6a(n-1) - a(n-2)$ with $a(1)=1, a(2)=5.$

developing it ..

$a(3)=6a(2)-a(1)$ coeffecients of $6^n$ are: $1,-1$

$a(4)=6^2a(2)-6a(1)-a(2)$ coeffecients: $1,-1,-1$

$a(5)=6^3a(2)-6^2a(1)-6a(2)-6a(2)+a(1)$ coeffecients: $1,-1,-2,1$

$a(6)=6^4a(2)-6^3a(1)-3*6^2a(2)+2*6a(1)+a(2)$ coeffecients: $1,-1,-3,2,1$

in general:

$coeff(a(n))=\{coeff(a(n-1)),0,0\}-\{0,0,coeff(a(n-2))\}$

binary analysis...

$11100000000$

$00110000000$ $k=0$


$00111000000$ $k=1$


$00111000000$

$00001100000$ $k=2$


$00111000000$

$00001100000$

$00001110000$ $k=3$


$00111000000$

$00001100000$

$00001110000$

$00000011000$ $k=4$


$00111000000$

$00001100000$

$00001110000$

$00000011000$

$00000011100$ $k=5$


first bit: 1

second bit: 1

third bit: 2+k

fourth bit: 1+k

fifth bit: 1+2+3(k-2)

sixth bit: 1+2+2(k-3)

seventh bit:1+2+3(k-4)

eighth bit: 1+2+2(k-5)

general sequence of coeffecients is :$\{1,-1,-2-n,1+n,1+2+3(k-l),-1-2-2(k-l-1)..\},l<k$


final formula:

  • $a(3)=6a(2)-a(1)$

  • $a(4)=6^2a(2)-6a(1)-a(2)$

  • $a(4+(k=1))=1*6^3a(2)-1*6^2a(1)-2*6^1a(2)+1*6^0a(1)$

  • $a(4+(k=2))=1*6^4a(2)-1*6^3a(1)-3*6^2a(2)+2*6^1a(1)-1a(2)$

...

  • $a(4+k)=1*6^{k+2}*a(2)-1*6^{k+1}*a(1)-(k+1)*6^{k}*a(2)+(k)*6^{k-1}*a(1)+(1+2+3(k-2))*6^{k-2}*a(2)-(1+2+3(k-3))*6^{k-3}*a(1)-...+(-1)^{2^{(l(l+1))mod4}}*((l+2>=k)+2*(l+1>=k)+(3-(lmod2))*(k-l))*a(lmod2+2)$ all values are non negative
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .