Generating equation for Diophantine equation

Question

Given a triangular tower of bricks where the bottom row has $N$ bricks, the next row has $N-1$ bricks, etc, we can ask the question: For which $N$ does there exist a smaller tower with $M \lt N$ bricks (somewhere above the bottom row) such that the number of bricks in the $M$ tower is half the bricks in the $N$ tower?

The Diophantine equation to solve here is:$$N(N+1)=2M(M+1)$$

and the first few solutions are $(N,M)$:

$(3,2)$

$(20,14)$

$(119,84)$

$(696,492)$

Searching OEIS for the $M$ solutions we find it here. In the Formula section of that link it gives the generating function of this sequence as: $$ M(k)=\frac{1}{8}\left(-4+(2+\sqrt{2})(3+2\sqrt{2})^k +(2-\sqrt{2})(3-2\sqrt{2})^k\right) $$ My question is: How in the world was this generating function arrived at?

It seems incredible to me that a closed formula exists for this Diophantine equation. Is this always the case?

EDIT

As @Sil pointed out in a comment, the formula at the OEIS link is not a generating function, but a closed formula. My question though, is basically the same. How was this closed formula arrived at?

Answer 1

By viewing the links, formulas, and other information of sequences A001652, A001653, and A053141 what will be found is that, in terms of Pell, $P_{n}$, and Pell-Lucas, $Q_{n}$, numbers is that $$N_{k} = \frac{Q_{2k+1} - 2}{4} \hspace{10mm} M_{k} = \frac{P_{2k+1} - 1}{2}.$$ When these values are placed into the equation as a check it will be found that the resulting identity is a known value for these number sets.

Since the first few values of $$\binom{n+1}{2} = 2 \, \binom{m+1}{2}$$ in terms of $(n,m)$ are $(n,m) \in \{ (3,2), (20,14), (119,84), (696,492), \cdots \}$. For the "$m$" values $m \in \{2, 14, 84, 492, \cdots \}$ it can be determined that $m_{k} = 6 \, m_{k-1} - m_{k-2} + 2$. The solution of this difference equation is $2 \, m_{k} = P_{2k+1} -1$, where $P_{n}$ are the Pell numbers. A similar process can be taken for the "$n$" values and yields the formula as stated in terms of the Pell-Lucas numbers.

Answer 2

Multiply the equation by $4$ and complete the square to put it into Pell's equation \begin{eqnarray*} 4N^2+4N+1=2(4M^2+4M+1)-1 \\ (2N+1)^2-2(2M+1)^2=-1 \\ n^2-2m^2=-1. \end{eqnarray*}