13
$\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$
  • 8
    $\begingroup$ You get $w^2 - 2x^2 = -1$. That is a negative Pell equation. $\endgroup$ – Daniel Fischer Jun 15 '15 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 '15 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 '15 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$ – johannesvalks Jul 19 '15 at 13:48
6
$\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$
2
$\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$
2
$\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$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.