How to prove that infinitely many even numbers $n$, are there such that $n+1$ and $n/2+1$ are both squares?
Note that if $x^2=n/2+1$ and $y^2=n+1$, then we have Pell's equation $$ 2x^2-y^2=1 $$ which has an infinite number of solutions.
How to generate $n$: by solving Pell's equation
Let $y_0=1$, $y_1=7$,and $y_k=6y_{k-1}-y_{k-2}$, then we get the infinite sequence $n_k=y_k^2-1$. The first few $n_k$ are $$ 0,48,1680,57120,1940448,\dots $$ The ratio of one $n_k$ to the last tends to $17+12\sqrt2\doteq33.97$
An equivalent formulation of your problem is: Show that there are infinitely many integer pairs $(p,q)$ such that $p^2 = 2q^2 - 1$ (where I have just written $p^2$ for $n+1$ and $q^2$ for $n/2+1$).
You can generate such pairs using the well-known sequence of rational approximations to $\sqrt2$:
$$\frac{1}{1},\frac{3}{2},\frac{7}{5},\frac{17}{12},\frac{41}{29},\frac{99}{70},\ldots$$
Here, each term is derived from the previous term by the recurrence $$\frac{p}{q} \mapsto \frac{p+2q}{p+q}$$
If you square each of these approximations, you will notice that the odd-numbered terms satisfy $p^2 = 2q^2 - 1$, and the even-numbered terms satisfy $p^2 = 2q^2 + 1$. And indeed, with a little algebra you can verify that:
- if $p^2 = 2q^2 - 1$, then $(p+2q)^2 = 2(p+q)^2 + 1$; and
- if $p^2 = 2q^2 + 1$, then $(p+2q)^2 = 2(p+q)^2 - 1$.
So the odd-numbered terms provide you with the sequence that you are looking for.
