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)$:





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?


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?

  • $\begingroup$ @Sil My mistake. I'll edit the question to reflect this. But my basic question is the same: How is the closed form arrived at? $\endgroup$ – Jens Jul 12 '18 at 21:36

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.

  • $\begingroup$ Yes, but how was the closed form achieved? What method was used to find the closed form? This is what I don't understand. $\endgroup$ – Jens Jul 12 '18 at 22:46
  • $\begingroup$ @Jens Since now all you need is closed form for Pell's numbers, and those satisfy $P_0=0, P_1=1, P_n=2P_{n-1}+P_{n-2}$... Can you find a closed form from linear recurrence relation? $\endgroup$ – Sil Jul 13 '18 at 3:26

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*}

  • $\begingroup$ OK, but how does this relate to finding a generating function? $\endgroup$ – Jens Jul 11 '18 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.