Explain this convergence among Pythagorean triplets

Why do the ratios of successive values of integers $a$ and $c$, where $a^{2}+(a+1)^{2}=c^{2}$, appear to converge to $$\frac{a_{n+1}}{a_{n}},\frac{c_{n+1}}{c_{n}}\rightarrow3+2\sqrt{2}$$

I rigorously generated all the {a,c} pairs where $a^{2}+(a+1)^{2}=c^{2}$ for $a<10^6$:

{3, 5}, {20, 29}, {119, 169}, {696, 985}, {4059, 5741}, {23660, 33461}, {137903, 195025}, {803760, 1136689}...

We can see that the fit to the ratio just gets better and better...

$$\frac{c_{8}}{c_{7}}=\frac{1136689}{195025}\approx5.82842712473...$$

$$3+2\sqrt{2}\approx5.82842712475...$$

Why does this ratio emerge? And with no other pairs between that satisfy the condition?

• Something to do will Pell's equation, no doubt. – Lord Shark the Unknown Jun 24 '18 at 8:07
• Have you measured how good this observation is at actually predicting next solutions? – Arnaud Mortier Jun 24 '18 at 8:15
• Related: oeis.org/A001652 – Arnaud Mortier Jun 24 '18 at 8:16
• $3+2\sqrt{2}$ is one root of $x^2-6x+1$ and in fact the $c_n$ satisfy the relation $$c_{n+2}=6c_{n+1}-c_n$$ And the $a_n$ apparently satisfy $$a_{n+2}=6a_{n+1}-a_n+2$$ This should be the key for the explanation. – Peter Jun 24 '18 at 8:29

\begin{align} a^{2}+(a+1)^{2}&=c^{2} \\ 2a^2+2a+1&=c^2 \\ 2\left(a+\frac{1}{2}\right)^2 +\frac{1}{2}&=c^2 \\ (2a+1)^2+1&=2c^2 \\ 2c^2-(2a+1)^2&=1 \\ 2c^2-d^2&=1 \quad | \quad d=2a+1 \end{align}

The above pell equation: $2c^2-d^2=1$ factors into $(c\sqrt 2-d)(c\sqrt 2 +d)=1$. With the initial solution being $(c_0,d_0)=(1,1)$, we have that $(\sqrt 2-1)(\sqrt 2 +1)=1$. Since we are permitted to multiply any equation by a constant we choose $(\sqrt 2-1)^2(\sqrt 2 +1)^2=(3-2\sqrt2)(3+2\sqrt 2)=1^2=1$. Doing this results in

\begin{align} (c\sqrt 2-d)(3-2\sqrt 2)(c\sqrt 2 +d)(3+2\sqrt 2)&=1 \\ &\implies \\ 2(3c+2d)^2-(4c+3d)^2&=1 \end{align}

This allows you to show iterative solutions:

$$\begin{cases} c_{k+1}=3c_k+2d_k \\ d_{k+1}=4c_k+3d_k \end{cases}$$

Which can be solved by the method I outlined here to produce:

$$c_k=\frac{2+\sqrt 2}{4} \left(3+2\sqrt 2\right)^k+\frac{2-\sqrt 2}{4} \left(3-2\sqrt 2\right)^k$$

note that the effect of $(3-2\sqrt 2)^k$ diminishes with increasing k, explaining your observation

• Wow! Thank you, not just for the answer but for the excellent explanation! – Jerry Guern Jun 24 '18 at 10:09
• @JerryGuern thanks bud. Some of the janitors don't like it when you render things clearly, but I much prefer it that way.... – AmateurMathPirate Jun 24 '18 at 10:25
• Excellent explanation, but note that for this to be a complete solution one step is missing: proving that this algorithm produces all solutions to the initial equation, and not only some of them. – Federico Poloni Jun 24 '18 at 20:10
• @FedericoPoloni in all honesty I'm stumped as to how to do that – AmateurMathPirate Jun 25 '18 at 6:28
• The usual trick is: each solution is associated to a power of $(\sqrt{2}+1)^k = c_k\sqrt{2}+d_k$; let $c,d$ a hypothetical solution outside of your "main sequence", with $c_k < c < c_{k+1}$. Then, $(c\sqrt{2}+d) / (c_k\sqrt{2}+d_k)$ produces a solution that is smaller than the minimal solution $(c_0, d_0)$, contradiction. (One also needs to prove that $c_0=d_0=1$ is the minimal solution, but that is trivial in this case). – Federico Poloni Jun 25 '18 at 6:41

The sequence $a_n$ is https://oeis.org/A001652.

This sequence is defined by $$\cases{a_n=6a_{n-1}+a_{n-2}+2\\ a_0=0\\a_1=3}$$

Therefore the ratio $r_n={a_n\over a_{n-1}}$ has limit $3+2\sqrt 2$ as observed by Klaus Brockhaus. I'll add a proof later.

The equation $a^2+(a+1)^2=c^2$ is equivalent to $$(2a+1)^2+1=2c^2\tag1$$ That is, $\frac{2a+1}c$ is a close under-approximation to $\sqrt2$. In fact, it can be shown that if $$\left|\,\frac pq-r\,\right|\le\frac1{2q^2}\tag2$$ then $\frac pq$ is a continued fraction convergent for $r$. From $(1)$, we get $$\left(\sqrt2-\frac{2a+1}c\right)\left(\sqrt2+\frac{2a+1}c\right)=\frac1{c^2}\tag3$$ From $(3)$, we get \begin{align} \left(\sqrt2-\frac{2a+1}c\right)\sqrt2 &\le\left(\sqrt2-\frac{2a+1}c\right)\left(\sqrt2+\frac{2a+1}c\right)\\ &=\frac1{c^2}\\[3pt] &\le1\tag4 \end{align} Thus, $\frac{2a+1}c\ge\sqrt2-\frac1{\sqrt2}$ and therefore $\sqrt2+\frac{2a+1}c\ge2\sqrt2-\frac1{\sqrt2}\gt2$. Applying $(3)$ again, we get that $$\left|\,\frac{2a+1}c-\sqrt2\,\right|\le\frac1{2c^2}\tag5$$ Thus, we see that $\frac{2a+1}c$ must be a convergent for $\sqrt2$.

If $\frac{2a+1}c$ is a convergent for $\sqrt2$, then it can be shown that $$\left|\,\frac{2a+1}c-\sqrt2\,\right|\le\frac1{2c^2}\tag6$$ If $\frac{2a+1}c\lt\sqrt2$, then we have \begin{align} \left(\sqrt2-\frac{2a+1}c\right)\left(\sqrt2+\frac{2a+1}c\right) &\le\frac1{2c^2}\left(2\sqrt2+\frac1{2c^2}\right)\\ 2c^2-(2a+1)^2&\le\sqrt2+\frac1{4c^2}\tag7 \end{align} which means that $a$ and $c$ satisfy $(1)$.

Thus, $(1)$ is satisfied precisely when $\frac{2a+1}c$ is a continued fraction convergent for $\sqrt2$ which is an under-estimate with odd numerator.

The continued fraction for $\sqrt2$ is $(1;\overline{2})$, so the convergents start $$\begin{array}{c|c} &&1&2&2&2&2&\cdots\\\hline 0&1&\color{#C00}{1}&3&\color{#C00}{7}&17&\color{#C00}{41}&\cdots\\\hline 1&0&\color{#C00}{1}&2&\color{#C00}{5}&12&\color{#C00}{29}&\cdots \end{array}\tag8$$ Because of the repetition of the continued fraction after the first term, the recurrence for the numerators and denominators for $n\ge1$ is $$x_n=2x_{n-1}+x_{n-2}\tag9$$ From this recurrence we get that all the numerators will be odd. It is a fact about continued fractions that convergents oscillate above and below the target limit, so that we only look at the convergents with even index: $1,\frac75,\frac{41}{29},\ldots$. Using $(9)$, we can derive the recurrence for every other numerator and denominator: $$x_n=6x_{n-2}-x_{n-4}\tag{10}$$ This is the recurrence for the even indexed numerators and denominators from $(8)$; and thus, the possible values of $2a+1$ and $c$ from $(1)$: $$\begin{array}{c|c} 2a_n+1&1&7&41&239&\cdots\\\hline c_n&1&5&29&169&\cdots \end{array}\tag{11}$$ where both $2a_n+1$ and $c_n$ satisfy the recurrence $$x_n=6x_{n-1}-x_{n-2}\tag{12}$$ Solutions to the linear recurrence in $(12)$ are linear combinations of $\left(3+\sqrt8\right)^n$ and $\left(3-\sqrt8\right)^n$: \begin{align} 2a_n+1&=\frac{1+\sqrt2}2\left(3+\sqrt8\right)^n+\frac{1-\sqrt2}2\left(3-\sqrt8\right)^n\tag{13}\\ c_n&=\frac{2+\sqrt2}4\left(3+\sqrt8\right)^n+\frac{2-\sqrt2}4\left(3-\sqrt8\right)^n\tag{14} \end{align} $(13)$ gives the formula $$a_n=-\frac12+\frac{1+\sqrt2}4\left(3+\sqrt8\right)^n+\frac{1-\sqrt2}4\left(3-\sqrt8\right)^n\tag{15}$$ As $n\to\infty$, $(14)$ and $(15)$ become asymptotically \begin{align} a_n&\sim\frac{1+\sqrt2}4\left(3+\sqrt8\right)^n\tag{16}\\ c_n&\sim\frac{2+\sqrt2}4\left(3+\sqrt8\right)^n\tag{17} \end{align}

Supplemental, from the OP:

I generalized AmateurMathPirate's answer to arbitrary $a,a+n,c$:

$$a=\frac{n}{4}\left(\left(1+\sqrt{2}\right)\left(3+2\sqrt{2}\right)^{k}+\left(1-\sqrt{2}\right)\left(3-2\sqrt{2}\right)^{k}\right)-\frac{n}{2}$$

$$b=a+n$$

$$c=\frac{n}{4}\left(\left(2+\sqrt{2}\right)\left(3+2\sqrt{2}\right)^{k}+\left(2-\sqrt{2}\right)\left(3-2\sqrt{2}\right)^{k}\right)$$

It's easy to prove that $a,b,c$ are a triple for any choice of positive $n,k$

This form doesn't cover all triplets, for example {5,12,13}.

And for the record, I only figured out this relation after I read AmateurMathPirate's answer above.