You are currently browsing the tag archive for the ‘generating functions’ tag.

It’s been quite a while since I’ve posted anything; I’ve been very busy with non-mathematical things this past month, and probably will be for at least another few weeks. In the meantime, I’d been idly thinking of another Problem of the Week to post, and while I was thinking of one such problem… I got stuck. So instead of just baldly posing the problem, this time I’ll explain how far as I got with it, and then ask you all for help.

The problem is easy to state: except for 1, are there any positive integers which are simultaneously triangular, square, and pentagonal numbers?

Just asking for all numbers which are simultaneously triangular and square is a fun little exercise in number theory, involving Pell’s equation and (yes) continued fractions. I’ll sketch how this goes. We are trying to solve the Diophantine equation $\displaystyle m^2 = \frac{n(n+1)}{2}$

By completing the square and manipulating a little, we get $8m^2 = (2n+1)^2 - 1.$

This converts to a Pell equation $x^2 - 2y^2 = 1$ where $x = 2n+1$, $y = 2m$. Writing the Pell equation as $N(x + \sqrt{2}y) := (x + \sqrt{2}y)(x - \sqrt{2}y) = 1,$

and using the fact that the norm map $N: \mathbb{Q}(\sqrt{2}) \to \mathbb{Q}$ just defined is a multiplicative homomorphism (because the Galois automorphism $x + \sqrt{2}y \mapsto x - \sqrt{2}y$ is also multiplicative), we see that the set of solutions $\{(x, y): N(x + \sqrt{2}y) = 1\}$

forms a group, under the group multiplication law $(x, y) \cdot (x', y') = (x x' + 2y y', x y' + y x')$

which is read off just by expanding $(x + \sqrt{2}y)(x' + \sqrt{2}y')$. The right branch of the hyperbola $x^2 - 2y^2 = 1$ thus forms a group (under this multiplication law, with identity $(1, 0)$) which is isomorphic to the additive group of real numbers. The set of integer solutions sitting on this branch forms a discrete subgroup, and hence is isomorphic to the additive group of integers (provided that nontrivial solutions exist!). To find a generator of this group, just look for the integer solutions to $x^2 - 2y^2 = 1$ which come closest to the identity $(1, 0)$; they are $(x, y) = (3, 2), (3, -2)$.

So, $(3, 2)$ generates the set of positive integer solutions. The next is $(3, 2)^2 = (3 \cdot 3 + 2(2 \cdot 2), 3 \cdot 2 + 2 \cdot 3) = (17, 12)$

and in general, the solutions $(x_n, y_n) = (3, 2)^n$ are given recursively by $(x_n, y_n) = (3x_{n-1} + 4y_{n-1}, 2x_{n-1} + 3y_{n-1}).$

Let’s go back a minute to our original problem, which asked for numbers which are both triangular and square. We read off the $k^{th}$ triangle-square, $m_k^2 = n_k(n_k+1)/2$, from $(x_k, y_k) = (2n_k + 1, 2m_k)$. For example, $(x_2, y_2) = (17, 12) \Rightarrow (n_2, m_2) = (8, 6)$

and so the square $36 = 6^2$ is simultaneously the triangular number $1 + 2 + \ldots + 8$. From $(x_3, y_3) = (99, 70)$, we have $(m_3, n_3) = (49, 35)$, and so $35^2$ is the next triangle-square. The next after that is $204^2$. And so on.

It would be nice to express these solutions in closed form. To this end, let me observe that the quotients $x_k/y_k = 3/2, 17/12, 99/70, \ldots$ are rational approximants to the continued fraction of $\sqrt{2}$: $3/2 = 1 + 1/2,$ $17/12 = 1 + 1/(2 + 1/(2 + 1/2)),$ $99/70 = 1 + 1/(2 + 1/(2 + 1/2 + 1/(2 + 1/2), \ldots$

(A similar observation applies to any Pell equation: positive solutions to $x^2 - Dy^2 = 1$, where $D$ is square-free, can be read off by examining every other rational approximant to the continued fraction for $\sqrt{D}$. This, I find, is a very cool fact.)

Starting from the first two rational approximants $p_0/q_0 = 1/1, p_1/q_1 = 3/2$, the remaining approximants $p_k/q_k$ can be read off from the recursive rule (*) $p_{k+1} = 2p_k + p_{k-1} \qquad q_{k+1} = 2q_k + q_{k-1}$

and for the purpose of determining the triangle-squares, we are really interested only in every other one of the denominators $q_k$, that is to say, $q_1, q_3, q_5, \ldots$. We can get a recursive rule for these from $q_{k+2} = 2q_{k+1} + q_k = 2(2q_k + q_{k-1}) + q_k = 6q_k - q_{k-2}$

where the last equation follows easily from the recursive rule (*). The same recursion thus gives the $y_k$ and $m_k$: $y_k = 2, 12, 70, 408, \ldots,$ $m_k = 1, 6, 35, 204, \ldots,$

namely $m_k = 6m_{k-1} - m_{k-2}$.

To get a closed form for the $m_k$ (whose squares are triangular), we can now apply the familiar method of generating functions (see here for a worked example of this method to derive the closed form for the Fibonacci numbers). Form $f(x) = m_1 + m_2 x + m_3 x^2 + \ldots = 1 + 6x + 35x^2 + \ldots$

and use the recursive rule for the $m_k$ to deduce (after some manipulation) that $\displaystyle f(x) = \frac1{1 - 6x + x^2}.$

The denominator expands as $(1 - (3 + \sqrt{8})x)(1 - (3 - \sqrt{8})x)$; by the method of partial fractions, we obtain $\displaystyle f(x) = \frac{(3 + \sqrt{8})/2\sqrt{8}}{1 - (3 + \sqrt{8})x} - \frac{(3 - \sqrt{8})/2\sqrt{8}}{1 - (3 - \sqrt{8})x}$

and from there, expanding the preceding line in geometric series, we derive a closed form for the $m_k$: $\displaystyle m_k = \frac1{2\sqrt{8}}((3 + \sqrt{8})^k - (3 - \sqrt{8})^k)$

Nice! If you prefer, this is just the integer part of $\displaystyle \frac1{2\sqrt{8}}(3 + \sqrt{8})^k$.

So, the $k^{th}$ triangular square is $\displaystyle \frac1{32}((3 + \sqrt{8})^{2k} + (3 - \sqrt{8})^{2k} - 2).$

Sweet.

Having gone through this analysis, the same method can be used to determine those squares which are pentagonal (the first few pentagonal numbers are $1, 1+4, 1+4+7, 1+4+7+10, \ldots$). I’ll let readers work this out if they like; suffice it to say that the $k^{th}$ square which is also pentagonal is the square of $\displaystyle \frac1{2\sqrt{24}}((5 + \sqrt{24})^{2k-1} - (5 - \sqrt{24})^{2k-1}).$

And that’s about as far as I got with this. After trying a few numerical forays with a hand-held calculator, my gut feeling is that I’d be amazed if there were any triangular-square-pentagonals past $m = 1$. But can anyone clinch the case?

[Edit: I’ve corrected the exponents in the last displayed line, from $k$ to $2k-1$.]

### Blog Stats

• 346,162 hits prof dr drd horia or… on My first post prof drd horia orasa… on My first post prof dr mircea orasa… on Inequality with log notedscholar on Self-referential Paradoxes, In… prof dr mircea orasa… on Inequality with log prof dr mircea orasa… on Inequality with log prof dr mircea orasa… on 2010 in review kenji on Basic category theory, I prof dr mircea orasa… on Solution to POW-10: Another ha… prof drd horia orasa… on Continued fraction for e prof drd horia orasa… on Inequality with log prof dr mircea orasa… on Solution to POW-12: A graph co… prof dr mircea orasa… on The Character of Physical… prof dr mircea orasa… on Milk and Tea puzzle prof drd horia orasa… on Inequality with log