Generating equation for Diophantine equation 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?
 A: 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*}
A: 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.
