# What is the most elementary way of proving a sequence is free of non-trivial squares?

Given the sequence A001921 $$0, 7, 104, 1455, 20272, 282359, 3932760, 54776287, 762935264, 10626317415, 148005508552, 2061450802319, 28712305723920, 399910829332567, \dots$$ which obeys the recurrence relation $$a_0 := 0,\ a_1 := 7, \quad a_{n+2} = 14a_{n+1} - a_n + 6.$$

How can I prove (or, I suppose, disprove) my conjecture that $a_0 = 0$ is the only square?

In case it helps, the conjecture is equivalent to saying that $x$ and $3x^2+3x+1$ cannot both be [positive integer] squares, though I am particularly interested in any general method of proof that attacks the recurrence relation directly.

EDIT: Here's an application.

• We have to decide, if the equation $3u^4+3u^2+1=v^2$ has a solution for $u>0$ which seems to be very difficult. Oct 29 '14 at 17:12
• Have you proven or disproven your equivalent formulation of the problem?
– John
Oct 29 '14 at 17:14
• By inference (i.e. by the solution of a related problem), I believe it to be true. I am trying to prove it now. Oct 29 '14 at 17:15
• It is not even clear, if it is decidable, whether a solution exists, I think though that the equation is still "easy" enough. Oct 29 '14 at 17:26
• Considering how large the terms of the sequence become, there is great evidence that no non-zero squares appear. Oct 29 '14 at 17:29

In this case we're lucky in that there aren't even any nonzero rational $x$ that make both $x$ and $3x^2+3x+1$ a square. Indeed it's already true that there's no nonzero rational $x$ that makes the product $x(3x^2+3x+1)$ is a square, because then $$9x(3x^2+3x+1) = (3x+1)^3-1$$ would be a square too, but it's known (by $2$-isogeny descent on the elliptic curve) that $Y^2 = X^3 - 1$ has no rational solutions other than $(X,Y)=(1,0)$.

In general, though, such questions can be quite difficult; there's a famous theorem of Siegel that guarantees finitely many solutions, and more recent work that yields effective algorithms to provably list all solutions; but these results and techniques are far from elementary, and no elementary technique is yet known to solve every such problem. Nor does starting from the recurrence seem to bring us any closer to such a solution.

• A somewhat more elementary proof that $Y^2 + 1 = X^3$ has no integer solutions other than $(1,0)$: factor over the Gaussian integers to $(Y+i) (Y-i) = X^3$; show that $Y$ is even (else there's a contradiction mod $4$) to conclude $Y\pm i = (m \pm in)^3$ for some integers $m,n$; but then $n(3m^2-n^2) = \pm 1$, so $n = \pm 1$ and $m=0$, etc. Nov 5 '14 at 5:19
• I can, in a very elementary way, get from $y^2+1=x^3$ to the equation $$3(2+r^2u)^2=u(4q^2-r^4u),$$ where $r,q,u$ are positive integers, $u \in \{1,3,6\}$, and $\gcd(q,r)=1$. Here's hoping I can get the rest of the way… Nov 5 '14 at 23:31
• Now $u=3$, and $q=3b^2+a^2$ with $(a,b) \in \{(1,1),(5,3),(19,11),\dots\}$, solutions to the equation $3B^2-A^2=2$. Nov 6 '14 at 0:37
• Doesn't this just bring us back to a "Pell equation" equivalent to the one we started with? Nov 6 '14 at 1:14
• I don't know yet: it might be "smaller" (and thus an elementary descent path). Nov 6 '14 at 1:54

Theorem. If $a$ and $b$ are integers such that $3a^4+3a^2+1=b^2\!$, then $a=0$.

Proof. Assume, contrary to the claim, that $a \ge 1$ and $b>1$ are integers satisfying the equation. Evidently $b$ is odd, say $b=2c+1$ for an integer $c \ge 1$. Hence \begin{align*} 3a^4 + 3a^2+1 &= (2c+1)^2 \\ 3a^2(a^2+1) &= 4c(c+1). \end{align*} Since $4 \nmid 3(a^2+1)$, regardless of the parity of $a$, we must have $2 \mid a^2$; hence $a$ is even, say $a=2d$ for an integer $d \ge 1$. Now \begin{align*} 3d^2(4d^2+1) &= c(c+1). \end{align*} We now show that this equation has no solutions with $c,d \ge 1$. Assume to the contrary that there exist integers $p,q,r,s \ge 1$ such that \begin{align*} 3d^2 &= pq, &&& c &= pr, \\ 4d^2+1 &= rs, &&& c+1 &= qs. \end{align*} Adding and factoring gives \begin{align*} 3d^2+c+1 &= pq+qs = q (p+s), \\ 4d^2+c+1 &= rs+pr = r(p+s), \end{align*} and then by subtraction we obtain $(p+s)(r-q) = d^2\!$. Since $3d^2=pq$, we have either $p \mid 3$ or $\gcd(p,d)>1$. The latter together with $(p+s) \mid d^2$ would contradict $\gcd(p,s) \mid \gcd(pr,qs) = \gcd(c,c+1) = 1$. Hence $p \mid 3$, so $p=1$ or $p=3$.

Case 1: $p=1$. Then $q=3d^2$, and $c=r$. Now $c+1 = qs$, so by substitution $r+1 = 3d^2s$. On the other hand, $rs-1 = 4d^2$, and adding these two relations yields \begin{align*} (rs-1)+(r+1) &= 4d^2 + 3d^2s \\ r(s+1) &= d^2(3s+4). \end{align*} Since $3s+4=3(s+1)+1$ implies $\gcd(s+1,3s+4)=1$, and $rs=4d^2+1$ implies $\gcd(r,d)=1$, we conclude $r=3s+4$ and $s+1=d^2$. Hence \begin{align*} 4d^2+1 &= rs \\ &= \bigl(3(d^2-1)+4\bigr)(d^2-1) \\ 2 &= 3d^2(d^2-2), \end{align*} which is clearly impossible.

Case 2: $p=3$. Then $q=d^2$ and $c=3r$. Now $c+1=qs$ becomes $3r+1=d^2s$. Since it is still true that $rs-1=4d^2$, we add the two relations to obtain \begin{align*} (rs-1) + (3r+1) &= 4d^2 + d^2s \\ r(s+3) &= d^2(4+s). \end{align*} Again, by considering common factors, we conclude $r=s+4$ and $s+3=d^2$. Hence \begin{align*} 4d^2+1 &= rs \\ &= (d^2+1)(d^2-3) \\ d^2(d^2-6) &= 4. \end{align*} This is also impossible, completing the proof.

• Even if this turns out to be valid, I'd still like to see a proof by descent, as well as a method of attacking the recurrence relation directly. Nov 7 '14 at 0:21

Too long for a comment. Maybe this procedure could shed some light on your problem.

Consider the Z-transform of both sides of your recurrence relation i.e. $$\mathcal{Z}\{a_{n+2}\}(z)=14\mathcal{Z}\{a_{n+1}\}(z)-\mathcal{Z}\{a_n\}(z)+6\mathcal{Z}\{1\}(z)$$ where $$\mathcal{Z}\{a_n\}(z)=\sum^{\infty}_{n=0}\frac{a_n}{z^n}$$ One can show that this transform is a linear operator and satisfies the following results $$\mathcal{Z}\{a_{n+1}\}(z)=z\mathcal{Z}\{a_{n}\}(z)-za_0$$ and $$\mathcal{Z}\{a_{n+2}\}(z)=z^2\mathcal{Z}\{a_{n}\}(z)-z^2a_0-za_1$$ Therefore the main equation becomes $$z^2\mathcal{Z}\{a_{n}\}(z)-z^2a_0-za_1=14(z\mathcal{Z}\{a_{n}\}(z)-za_0)-\mathcal{Z}\{a_{n}\}(z)+6\mathcal{Z}\{1\}(z)$$ Upon substitution with $a_0=0$ and $a_1=7$ we get $$z^2\mathcal{Z}\{a_{n}\}(z)-7z=14z\mathcal{Z}\{a_{n}\}(z)-\mathcal{Z}\{a_{n}\}(z)+6\mathcal{Z}\{1\}(z)$$ or $$\mathcal{Z}\{a_{n}\}(z)=\frac{7z+6\mathcal{Z}\{1\}(z)}{z^2-14z+1}$$ Now notice that $$\mathcal{Z}\{1\}(z)=\sum^{\infty}_{n=0}\frac{1}{z^n}=\frac{z}{z-1}$$ for $|z|>1$. Hence for $|z|>1$ we have $$\mathcal{Z}\{a_{n}\}(z)=\frac{z(7z-1)}{(z-1)(z^2-14z+1)}=\frac{z(7z-1)}{(z-1)(z-7+4\sqrt{3})(z-7-4\sqrt{3})}$$ Technically speaking this is the generating function of the series $\{a_n\}^{\infty}_{n=0}$. Taking the inverse Z-transform of the above expression yields $$a_n=\mathcal{Z}^{-1}(\mathcal{Z}\{a_{n}\}(z))(n)=\mathcal{Z}^{-1}(\frac{z(7z-1)}{(z-1)(z^2-14z+1)})(n)=\frac{1}{12}\Big((3-2\sqrt{3})(7-4\sqrt{3})^n+(3+2\sqrt{3})(7+4\sqrt{3})^n-6\Big)$$ One can verify that $a_0=0$ and $a_1=7$. Clearly $a_0$ is a square. Now the question becomes that if there exists some $n>1$ such that $a_n$ as defined explicitly by the expression above is a square. On one side we could show by induction that $a_n\in\mathbb{Z}$ for all $n$. For $n=0$ and for $n=1$ we already know that the values are integers. Assume that for $n=k$ we have $a_k\in\mathbb{Z}$. Let $n=k+1$ then \begin{align}a_{k+1}&=\frac{1}{12}\Big((3-2\sqrt{3})(7-4\sqrt{3})^{k+1}+(3+2\sqrt{3})(7+4\sqrt{3})^{k+1}-6\Big)\\ &=\frac{1}{12}\Big((3-2\sqrt{3})(7-4\sqrt{3})^{k}(7-4\sqrt{3})+(3+2\sqrt{3})(7+4\sqrt{3})^{k}(7+4\sqrt{3})-6\Big)\\ &=\frac{1}{12}\Big(7\cdot12a_k+(3-2\sqrt{3})(7-4\sqrt{3})^{k}(-4\sqrt{3})+(3+2\sqrt{3})(7+4\sqrt{3})^{k}(4\sqrt{3})+36\Big)\\ &=\frac{1}{12}\Big(7\cdot12a_k+7\cdot12a_k-(3-2\sqrt{3})(7-4\sqrt{3})^{k}-(3+2\sqrt{3})(7+4\sqrt{3})^{k}+72\Big) \\&=14a_k-a_{k-1}+6\in\mathbb{Z} \end{align} The last expression is just the original recurrence formula (one could just use this indeed to show that for all $n$ we have $a_n\in\mathbb{Z}$).