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?
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.