In this paper we introduce and study the hyper-Mersenne numbers, a class of integer sequences extending the classical Mersenne numbers which arise in a combinatorial and algebraic context. Using generating functions, we derive explicit formulae and identities for these sequences. In particular, we find relations to binomial coefficients and figurate numbers. We also provide a closed-form expression for the determinant of associated matrices, valid in full generality.
Numbers of the form \(2^n -1\), known as Mersenne numbers, represent the sum of powers of 2 from \(1\) to \(2^{n-1}\), \[2^0 + 2^1 + \cdots + 2^{n-1} = 2^n -1.\]
The French Franciscan and 16th-century mathematician Marin Mersenne studied these numbers in the context of constructing prime numbers. Mersenne numbers appear in numerous combinatorial situations, including famous problems of the tower of Hanoi and the wheat on chessboard [8]. They also appear as the number of set partitions, i.e. as the Stirling numbers of the second kind with the lower index 2. In the Online Encyclopedia of Integer Sequences (OEIS), Mersenne numbers are listed as sequence number 225 (A000225).
Prime Mersenne numbers play a prominent role in number theory. It is well known that if \[M_n:= 2^n -1, \enspace n \in \mathbb{N}_0,\] is a prime then \(n\) is a prime. More on this issue one can find in a work by S. Ligh and P. Jones [9]. Divisibility properties of the Mersenne numbers are studied by P. Erdös [6], by C. Pomerance [12], and then by P. Erdös, P. Kiss and C. Pomerance [7]. On the search of the biggest Mersenne prime let us mention work of C. Noll and L. Nickel [11] as well as that done by W. N. Colquitt and L. Welsh [3]. There is a famous unsolved problem on primality of Mersenne numbers, the question whether there are infinitely many Mersenne primes. K. Boklan and J. Conway state a stunning conjecture that there are finitely many prime numbers \(M_p\) with \(p\) being a twin prime [2].
Among recent results, it is worth mentioning achievement of R. T. Eakin [5]. In this work the author proves that for all positive integers \(n\) the corresponding Mersenne number \(M_n\) can be expanded as \[\begin{aligned} M_n = \binom{2n}{n} ^{-1} \sum_{r=1}^{n} \Bigg \{ \Big(\frac{n+1}{r}\Big ) \binom{2n-2r}{n-r} \sum_{k=0}^{ \lfloor (r-1)/2 \rfloor} (-1)^k \binom{2r}{k} \binom{n+3r-2k}{r-2k-1} \Bigg \}. \end{aligned}\]
This binomial sum was conjectured when a problem in analytical spectroscopy was considered [4].
In addition to Mersenne numbers, it is known that their generalizations also appear within enumerative problems of combinatorial objects. For the purpose to illustrate this, now we define the \(1\)-Mersenne sequence of numbers, denoted \(M_n^{(1)}\), as a partial sum of Mersenne numbers.
Definition 1.1. We define the sequence \((M_n^{(1)})_{n \ge 0}\) of \(1\)-Mersenne numbers as the sequence whose \(n\)-th term is equal to the sum of the first \(n\) Mersenne numbers, \[\begin{aligned} M_n^{(1)}:= \sum_{k=0}^{n} M_k, \enspace n \ge 0. \end{aligned}\]
Thus, the first few 1-Mersenne numbers are \[(M_n^{(1)})_{n \ge 0}= ( 0, \enspace 1, \enspace 4, \enspace 11, \enspace 26, \enspace 57, \enspace 120, \enspace 247, \enspace 502, \enspace 1013, \ldots).\]
Recursive nature of the \(1\)-Mersenne numbers we present in the following
Proposition 1.2. The elements of the sequence \(\Big(M_{n}^{(1)} \Big)_{n \ge 0}\) of \(1\)-Mersenne numbers satisfy the recurrence relation \[\begin{aligned} M_{n}^{(1)} = 2 M_{n-1}^{(1)} + n. \end{aligned}\]
Proof. From the Definition 1.1 we have an obvious relation \[M_{n}^{(1)} = M_{n-1}^{(1)} + M_n,\] and furthermore \[\begin{aligned} M_{n}^{(1)} = M_{n-1}^{(1)} + 2 M_{n-1} +1 = M_{n-1}^{(1)} + 2( M_{n-1}^{(1)} – M_{n-2}^{(1)} ) +1, \end{aligned}\] which results with \[\begin{aligned} \label{forTelescoping1} M_{n}^{(1)} = 3M_{n-1}^{(1)} -2 M_{n-2}^{(1)} +1. \end{aligned} \tag{1}\]
We iteratively use relation (1) to get \[\begin{aligned} M_{n}^{(1)} =& (2 M_{n-1}^{(1)} + M_{n-1}^{(1)}) – 2 M_{n-2}^{(1)} +1 \\ =& 2 M_{n-1}^{(1)} + 3 M_{n-2}^{(1)} – 2M_{n-3}^{(1)} – 2 M_{n-2}^{(1)} +2 \\ =& 2 M_{n-1}^{(1)} + M_{n-2}^{(1)} – 2 M_{n-3}^{(1)} +2 \\ =& 2 M_{n-1}^{(1)} + 3 M_{n-3}^{(1)} – 2M_{n-4}^{(1)} – 2 M_{n-3}^{(1)} +3 \\ =& 2 M_{n-1}^{(1)} + M_{1}^{(1)} – 2M_{0}^{(1)} + n-1\\ =& 2 M_{n-1}^{(1)} + n. \end{aligned}\]
This completes the proof of the lemma. ◻
It is known that the sequence \(M_n^{(1)}\) enumerates the Dyck paths of length \(2n+2\) with the long ascent of length at least 2 (the sequence A000295 in the OEIS). There are also families of permutations counted by this sequence. Recall that for non-negative numbers \(n\) and \(k\), \(n\geq k\), Eulerian number \(\left\langle {n \atop k} \right\rangle\) is defined as the number of permutations \(\pi_1, \pi_2, \ldots, \pi_n\) of \([n]\) that have \(k\) ascents (i.e. \(k\) places where \(\pi_j < \pi_{j+1}\)). Eulerian numbers form a triangular matrix, whose entries satisfy the recurrence formula \[ \left\langle {n \atop k} \right\rangle = (k+1)\left\langle {n-1 \atop k} \right\rangle + (n-k)\left\langle {n-1 \atop k-1} \right\rangle, \quad n>0. \tag{2}\]
Note that the recurrence presented in Proposition 1.2 generates the same sequence of numbers as the recurrence (2) for \(k=1\) (with indices of terms shifted by 1).
Those facts motivate us for further generalization of Mersenne numbers, which lead to the notion of \(r\)-Mersenne numbers that we introduce in the following Definition 1.3, \(r \in \mathbb{N}_0\). We also refer to \(r\)-Mersenne numbers as hyper-Mersenne numbers of the \(r\)-th generation. Recent refinements of classical problems within Mersenne numbers also motivate us for this work [1, 8].
Definition 1.3. The \(r\)-Mersenne sequence \((M_n^{(r)})_{n \ge 0}\) is the sequence of numbers \(M_n^{(r)}\) that satisfy the recurrence relation \[\begin{aligned} M_n^{(0)}:=2^n-1, \enspace \enspace M_n^{(r)}:= \sum_{k=0}^{n} M_k^{(r-1)} \enspace (r\geq 1),\enspace \enspace M_0^{(r)}=0. \end{aligned}\]
When \(r=0\) we deal with classical Mersenne numbers.
In the following sections, we study the combinatorial and algebraic properties of hyper-Mersenne numbers. In Section 2 we give generating functions in full generality and then use it to prove identities for these sequences. In particular, we prove that the hyper-Mersenne numbers are expressed as the sums of binomial coefficients. In Section 3 we present relations with the figurate numbers.
The main contribution of this paper is given in Theorem 4.4, where we consider Hankel-type matrices whose entries are hyper-Mersenne numbers and obtain a closed-form expression for their determinants. Determinants of Hankel and Toeplitz matrices associated with classical sequences, such as Fibonacci, Lucas, and related combinatorial numbers, have been extensively studied in the literature. Our result provides an explicit determinant formula for matrices generated by hyper-Mersenne numbers, thus extending this line of research to a new family of combinatorially defined sequences. These results are presented in Section 4.
We let \(F^{(r)} (z)\) be a generating function of the \(r\)-Mersenne numbers, \[\begin{aligned} F^{(r)} (z):= z + M_2^{(r)} z^2 + \cdots+M_n^{(r)} z^n+ \cdots = \sum_{n \ge 0} M_n^{(r)} z^n. \end{aligned}\]
For the purpose to derive closed form for the generating function \(F^{(r)} (z)\), firstly we will consider hyper-Mersenne numbers of the \(1\)st generation.
In particular, having known that \[\begin{aligned} M_{n}^{(1)} =& 2 M_{n-1}^{(1)} +n , \end{aligned}\] we obtain \(n=M_{n-1}^{(1)} -2M_{n-2}^{(1)}+1\), and \[\begin{aligned} M_{n}^{(1)} =& 3 M_{n-1}^{(1)} -2M_{n-2}^{(1)}+1. \end{aligned}\]
Now, shifting this equality by one index gives \[\begin{aligned} 1=M_{n-1}^{(1)} -3M_{n-2}^{(1)} +2 M_{n-3}^{(1)} , \end{aligned}\] and the substitution yields \[\begin{aligned} \label{linearRecurr1} M_{n}^{(1)} = 4M_{n-1}^{(1)} – 5 M_{n-2}^{(1)} +2M_{n-3}^{(1)}. \end{aligned} \tag{3}\]
Now we employ relation (3) to get closed form of the generating function for \(1\)-Mersenne numbers. We have \[\begin{aligned} F^{(1)} (z) =& z + M_2 z^2+ \sum_{n \ge3 } \Big(4 M_{n-1}^{(1)} – 5 M_{n-2}^{(1)} +2 M_{n-3}^{(1)} \Big) z^n \\ =& z + 4z^2 + 4z \sum_{n \ge3 } M_{n-1}^{(1)} z^{n-1} – 5z^2 \sum_{n \ge3 } M_{n-2}^{(1)} z^{n-2} + 2z^3 \sum_{n \ge3 } M_{n-3}^{(1)} z^{n-3}\\ =&z+4z^2+4z\left( F^{(1)}(z)-z\right)-5z^2F^{(1)}(z)+2z^3F^{(1)}(z)\\ =& z + 4zF^{(1)}( z)- 5z^2F^{(1)}(z) + 2z^3F^{(1)}(z), \end{aligned}\] and finally \[\begin{aligned} F^{(1)} (z) = \frac{z}{-2z^3 + 5 z^2 -4z +1}, \end{aligned}\] which we express as \[\begin{aligned} \label{linearRecurr2} F^{(1)} (z) = \frac{-z}{(2z-1)(z-1)^2}. \end{aligned} \tag{4}\]
Lemma 2.1. The closed form of the generating function \(F^{(r)}(z)\) for \(r\)-Mersenne numbers is equal to \[\begin{aligned} F^{(r)} (z) = \frac{(-1)^{r} z}{ (2z-1)(z-1)^{r+1}}. \end{aligned}\]
Proof. We provide a proof by induction. We have \[\begin{aligned} F^{(r)} (z)=& z + M_2^{(r)} z^2 +M_3^{(r)} z^3 + \cdots +M_n^{(r)} z^n + \cdots \\ =& M_1^{(r-1)}z + \Big(M_1^{(r-1)} + M_2^{(r-1)} \Big) z^2 + \Big(M_1^{(r-1)} + M_2^{(r-1)} + M_3^{(r-1)} \Big) z^3 + \cdots\\ =& \Big(M_1^{(r-1)}z + M_2^{(r-1)}z^2 +M_3^{(r-1)}z^3+\cdots+ M_n^{(r-1)}z^n +\cdots \Big) \\ &+ \Big(M_1^{(r-1)}z^2 + M_2^{(r-1)}z^3 +M_3^{(r-1)}z^4+\cdots + M_n^{(r-1)}z^{n+1} +\cdots\Big) +\cdots \\ =& F^{(r-1)} (z) + z F^{(r-1)} (z) + z^2 F^{(r-1)} (z) + z^3 F^{(r-1)} (z) + \cdots \\ =& F^{(r-1)} (z) \Big(\frac{1}{1-z}\Big). \end{aligned}\]
Once having known generating function for \(r=1\) (relation (4)), the induction step completes the proof: \[\begin{aligned} F^{(r)} (z) =& F^{(r-1)} (z) \cdot \frac{1}{1-z}\\ =& \frac{(-1)^{r-1} z}{ (2z-1)(z-1)^{r}} \cdot \frac{-1}{z-1}\\ =&\frac{(-1)^{r} z}{ (2z-1)(z-1)^{r+1}}. \end{aligned}\] ◻
In particular, according to Lemma 2.1, when \(r=2\) we have \[\begin{aligned} \frac{z}{(2z-1)(z-1)^{3}} = z + 5z^2 + 16z^3 +42z^4 +99z^5 +219z^6 +466z^7 + 968z^8 + \cdots, \end{aligned}\] and for \(r=3\) we have \[\begin{aligned} \frac{-z}{(2z-1)(z-1)^{4}} = z + 6z^2 + 22z^3 +64z^4 +163z^5 +382z^6 +848z^7 + 1816z^8 + \cdots, \end{aligned}\] etc.
Note that the consideration which derives generating function (4) shows that coefficients in denominator of \(F^{(r)} (z)\) define recurrence relation for the \(r\)-Mersenne sequence of numbers. We let \(m_1^{(r)}, m_2^{(r)}, \ldots, m_{r+2}^{(r)}\) denote these coefficients, obtained from \((1-2z)(z-1)^{r+1}\) expanded as a polynomial in \(z\), for the \(r\)-Mersenne numbers, \[\begin{aligned} \label{linhomrecurr} M_n^{(r)} = m_1^{(r)} M_{n-1}^{(r)} – m_2^{(r)} M_{n-2}^{(r)} + \cdots +(-1)^{r+1}m_{r+2}^{(r)} M_{n-r-2}^{(r)}. \end{aligned} \tag{5}\]
Moreover, Lemma 2.1 gives an algorithm to compute coefficients in the recurrence for \(M_n^{(r)}\) once having known those for \(M_n^{(r-1)}\). Thus, we have \[\begin{aligned} m_i^{(r)} = m_{i-1}^{(r-1)} + m_{i}^{(r-1)}, \enspace 1 < i < r+2, \end{aligned}\] with \[\begin{aligned} \label{lastcoeff} m_1^{(r)}=& r+3, \mbox{ and} \\ m_{r+2}^{(r)} =&2. \end{aligned}\]
The recurrence coefficients \(m_1^{(r)}, m_2^{(r)}, \ldots, m_{r+2}^{(r)}\) encode the linear homogeneous recurrence relation satisfied by the \(r\)-Mersenne numbers. As \(r\) varies, these coefficients themselves satisfy the recurrence, \[m_i^{(r)} = m_{i-1}^{(r-1)} + m_i^{(r-1)},\] which suggests an intrinsic triangular structure across successive generations of hyper-Mersenne sequences.
In order to present it in a unified way, and to make explicit the dependence of recurrence coefficients on the parameter \(r\), it is natural to collect all coefficients \(\{m_j^{(i-1)}\}\) into a single lower triangular array. We define triangular matrix \(C = [c_{i,j}]\), \(c_{0,0}:=2\), \(c_{i,j} = m_j^{(i-1)}\), \(i \ge 1\), \(c_{i,j} = 0\) for \(j > i+2\). We list some elements of matrix \(C\), \[C= \begin{pmatrix} 2 \\ 3 & 2 \\ 4 & 5 & 2\\ 5 & 9 & 7 & 2\\ 6 & 14 & 16 & 9 & 2\\ 7 & 20 & 30 & 25 & 11 & 2\\ 8 & 27 & 50 & 55 & 36 & 13 & 2\\ 9 & 35 & 77 & 105 & 91 & 49 & 15 & 2\\ & && \vdots &&&& \ddots \end{pmatrix}.\]
Example 2.2. Using relation (5) and matrix \(C\), one can calculate the value of \(M_{8}^{(2)}\). In that case we have the recurrence \[\begin{aligned} M_{n}^{(2)} = 5 M_{n-1}^{(2)} – 9M_{n-2}^{(2)} + 7M_{n-3}^{(2)} -2 M_{n-4}^{(2)}, \end{aligned}\] to get \(M_{8}^{(2)} = 968\).
Note that rows of of \(C\) possess further interesting properties, in particular constant alternating sum of a row elements.
Once having generating functions for \(r\)-Mersenne numbers one can perform partial fraction decomposition to get the explicit formula for a certain sequence. When \(r=1\) we obtain \[\begin{aligned} \frac{-z}{(2z-1)(1- z)^{2}} = – \frac{2}{2z-1} + \frac{1}{z-1} – \frac{1}{(z-1)^2}, \end{aligned}\] which leads to the explicit formula for \(1\)-Mersenne numbers \[\begin{aligned} M_n^{(1)} = 2^{n+1} – n -2. \end{aligned}\]
Furthermore, when \(r=2\) we obtain \[\begin{aligned} \frac{z}{(2z-1)(z- 1)^{3}} = – \frac{4}{2z-1} + \frac{2}{z-1} – \frac{1}{(z-1)^2} + \frac{1}{(z-1)^3}, \end{aligned}\] which gives \[\begin{aligned} M_n^{(2)} = 2^{n+2} – \binom{n+2}{2} – n – 3, \end{aligned}\] as the explicit formula for 2-Mersenne numbers. Now, the value of \(M_8^{(2)}\) that we calculate in Example 2.2 one get directly by expression \(2^{10} – \binom{10}{2} – 11 (=968)\). We formalize these reasoning to prove such formulas in full generality.
Theorem 2.3. For the \(n\)-th \(r\)-Mersenne number we have \[\begin{aligned} \label{explicitRMersenne} M_n^{(r)} = 2^{n+r} – \sum_{k=0}^{r} \binom{n+r}{k}, \end{aligned} \tag{6}\] where \(n, r \geq0\).
Proof. We obtain partial fraction decompositions for every natural number \(r\), \[\begin{aligned} \label{partialFractionDecomposition} \frac{(-1)^{r} z}{ (2z-1)(z-1)^{r+1}} = – \frac{2^r}{2z-1} + \frac{2^{r-1}}{z-1} – \cdots \frac{1}{(z-1)^{r}} +(-1)^{r} \frac{1}{(z-1)^{r+1}}, \end{aligned} \tag{7}\] by means of induction.
For the base case (\(r=1\)), we have \[\frac{-z}{(2z-1)(z-1)^2}=\frac{A}{2z-1}+\frac{B_1}{z-1}+\frac{B_2}{(z-1)^2}.\]
Solving the system gives \[A=-2,\qquad B_1=1,\qquad B_2=-1.\]
Thus \[\frac{-z}{(2z-1)(z-1)^2}=\frac{-2}{2z-1}+\frac{1}{z-1}+\frac{-1}{(z-1)^2}.\]
Assume that for some \(r\in\mathbb{N}\) we have \[\frac{(-1)^r z}{(2z-1)(z-1)^{r+1}}=-\frac{2^r}{2z-1}+\sum_{k=1}^{r+1}\frac{(-1)^{k-1} 2^{r-k}}{(z-1)^k}.\]
Now we shell provide an inductive step. Observe \[\frac{(-1)^{r+1} z}{(2z-1)(z-1)^{r+2}}=-\frac{1}{z-1}\frac{(-1)^r z}{(2z-1)(z-1)^{r+1}}.\]
Using the induction hypothesis, \[-\frac{1}{z-1}\left(-\frac{2^r}{2z-1}+\sum_{k=1}^{r+1}\frac{(-1)^{k-1} 2^{r-k}}{(z-1)^k}\right)=\frac{2^r}{(2z-1)(z-1)}-\sum_{k=1}^{r+1}\frac{(-1)^k 2^{r-k}}{(z-1)^{k+1}}.\]
Since \[\frac{2^r}{(2z-1)(z-1)}=-\frac{2^{r+1}}{2z-1}+\frac{2^r}{z-1},\] we obtain \[-\frac{2^{r+1}}{2z-1}+\frac{2^r}{z-1}-\sum_{k=1}^{r+1}\frac{(-1)^k 2^{r-k}}{(z-1)^{k+1}}.\]
Reindexing the sum (\(j=k+1\)) gives \[-\frac{2^{r+1}}{2z-1}+\frac{2^r}{z-1}+\sum_{j=2}^{r+2}\frac{(-1)^{j-1} 2^{r+1-j}}{(z-1)^j}=-\frac{2^{r+1}}{2z-1}+\sum_{j=1}^{r+2}\frac{(-1)^{j-1} 2^{r+1-j}}{(z-1)^j}.\]
Hence \[\frac{(-1)^{r+1} z}{(2z-1)(z-1)^{r+2}}=-\frac{2^{r+1}}{2z-1}+\sum_{k=1}^{r+2}\frac{(-1)^{k-1} 2^{r+1-k}}{(z-1)^k}.\]
Once having relation (7), one obtains an explicit formula for \(r\)-Mersenne numbers, applying \[\frac{1}{(1-\alpha z)^m } = \sum_{k \ge 0} \binom{m+k-1}{k} \alpha^k z^k.\] ◻
We have \[\begin{aligned} \frac{(-1)^r z}{(2z-1)(z-1)^{r+1}}=& -\frac{2^r}{2z-1}+ \frac{2^{r-1}}{z-1}- \cdots- \frac{1}{(z-1)^r}+ (-1)^r \frac{1}{(z-1)^{r+1}}\\ =& \frac{2^r}{1-2z}- \frac{2^{r-1}}{1-z}- \frac{2^{r-2}}{(1-z)^2}- \cdots- \frac{1}{(1-z)^r}- \frac{1}{(1-z)^{r+1}}\\ =&2^r \sum_{n \ge 0} 2^n z^n- 2^{r-1} \sum_{n \ge 0} \binom{n}{n} z^n- 2^{r-2} \sum_{n \ge 0} \binom{n+1}{n} z^n- \cdots\\ &- \sum_{n \ge 0} \binom{n+r-1}{n} z^n- \sum_{n \ge 0} \binom{n+r}{n} z^n\\ =&2^{n+r}- 2^{r-1} \sum_{n \ge 0} \binom{n}{0} z^n- 2^{r-2} \sum_{n \ge 0} \binom{n+1}{1} z^n- \cdots\\ &- \sum_{n \ge 0} \binom{n+r-1}{r-1} z^n- \sum_{n \ge 0} \binom{n+r}{r} z^n. \end{aligned}\]
Thus, coefficients within \(z^n\) represent the \(n\)-th term of \(r\)-Mersenne sequence, \[\begin{aligned} M_n^{(r)}=& 2^{n+r}- 2^{r-1} \binom{n}{0}- 2^{r-2} \binom{n+1}{1}- \cdots- \binom{n+r-1}{r-1}- \binom{n+r}{r}\\ =& 2^{n+r}- \binom{n+r}{0}- \binom{n+r}{1}- \cdots- \binom{n+r}{r}\\ =& 2^{n+r}- \sum_{j=0}^{r} \binom{n+r}{j}.\quad \square \end{aligned}\]
Corollary 2.4. The \(n\)-th \(r\)-Mersenne number is equal to the sum of first \(n\) binomial coefficients in the \((n+r)\)-th row of Pascal triangle, \[\begin{aligned} M_n^{(r)} = \sum_{k=0}^{n-1} \binom{n+r}{k}. \end{aligned}\]
Proof. According to the explicit formula (6) and basic properties of binomial coefficients we have \[\begin{aligned} M_n^{(r)} =& \sum_{k=0}^{n+r} \binom{n+r}{k} – \sum_{k=0}^{r} \binom{n+r}{k} = \sum_{k=r+1}^{n+r} \binom{n+r}{k} = \sum_{k=0}^{n-1} \binom{n+r}{k}. \end{aligned}\]
The last equality follows from the symmetry of the binomial coefficient, \(\binom{n+r}{k}= \binom{n+r}{n+r-k}.\) ◻
Thus, \(r\)-Mersenne numbers can be expressed as the sum of binomial coefficients, as it is shown in Corollary 2.4. Table 1 illustrates the case \(r=2\).
\[\begin{array}{ccccc} &1 &\\ &1 \enspace \enspace 1 &\\ &1 \enspace \enspace \enspace 2 \enspace \enspace \enspace 1 &\\ &{\bf 1} \enspace \enspace \enspace 3 \enspace \enspace \enspace 3 \enspace \enspace \enspace 1 & \\ &{\bf 1} \enspace \enspace \enspace {\bf 4} \enspace \enspace \enspace 6 \enspace \enspace \enspace 4 \enspace \enspace \enspace 1&\\ &{\bf 1} \enspace \enspace \enspace {\bf 5} \enspace \enspace \enspace {\bf 10} \enspace \enspace 10 \enspace \enspace \enspace 5 \enspace \enspace \enspace1 &\\ &{\bf 1} \enspace \enspace \enspace {\bf 6} \enspace \enspace \enspace {\bf 15} \enspace \enspace {\bf 20} \enspace \enspace 15 \enspace \enspace \enspace 6 \enspace \enspace \enspace 1& \\ & \cdots & \end{array}\]
The next Corollary 2.5 follows immediately from Theorem 2.3 and the Pascal recurrence.
Corollary 2.5. The alternating sum of \(k\)-Mersenne numbers \(M_{n+1}^{(0)}, M_{n}^{(1)}, \ldots , M_{n+1-k}^{(k)},\) \(\ldots, M_{1}^{(n)}\), \(k=0,1, \ldots, n\) is equal to \(2^n\), \[\begin{aligned} \label{cor2} \sum_{k=0}^{n} (-1)^k M_{n+1-k}^{(k)} = 2^n. \end{aligned} \tag{8}\]
Proof. In order to prove this corollary, we consider two different cases, determined by the parity of \(n\).
When \(n\) is odd, the number of terms of the l.h.s. of (8) is even. After applying Theorem 2.3 to these terms, i.e. to the \[M_{n+1}^{(0)} – M_{n}^{(1)} + \cdots – M_{1}^{(n)},\] and cancellation, for the l.h.s. of (8) we obtain \[\begin{aligned} \sum_{k=0}^{n} (-1)^k M_{n+1-k}^{(k)}=& \binom{n+1}{1} + \binom{n+1}{3} + \cdots + \binom{n+1}{n}\\ =& \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n}\\ =& 2^n. \end{aligned}\]
When \(n\) is even, again we apply Theorem 2.3 to terms on the l.h.s. of (8). After cancellation we have \[\begin{aligned} \sum_{k=0}^{n} (-1)^k M_{n+1-k}^{(k)}=& 2^{n+1} – \left[ \binom{n+1}{0} + \binom{n+1}{2} + \cdots + \binom{n+1}{n} \right]\\ =& 2^{n+1} – \sum_{j=0}^{n} \binom{n}{j}= 2^n (2 – 1)= 2^n. \end{aligned}\]
This calculation completes the proof. ◻
In this section we shall see that figurate numbers appears as differences among hyper-Mersenne numbers. Recall that the figurate numbers are generalization of triangular numbers. Figurate numbers are defined as the number of points with integer coordinates (lattice points) of a simplex.
For the \(n\)-th figurate number with parameter (dimension) \(r\), denoted \(F_n^{(r)}\), there is Fermat’s fundamental recurrence \[r F_n^{(r)} = n F_{n+1}^{(r-1)},\] and based on this recurrence relation Pascal found the explicit formula \[\begin{aligned} \label{FermatPascalFigurate} F_n^{(r)} = \binom{n+r-1}{r}. \end{aligned} \tag{9}\]
It is worth mentioning that finite power sums (Faulhaber sums) can be expressed via figurate numbers. Recently, it has shown that the sum \(\sum_{j=1}^n j^p\), \(p=1, 2, \ldots\) is a linear combination of figurate numbers [10].
The figurate number \(F_n^{(2)}\) is called triangular number. The figurate number \(F_n^{(3)}\) is called pyramidal number. In higher dimensions \(r \ge 4\), figurate numbers are called hyper-tetrahedron numbers.
We shall now provide a relation between figurate and hyper-Mersenne numbers. For \(r=2\) it holds that \[\begin{aligned} \label{forTelescoping2} M_n^{(2)} =& M_{n-1}^{(2)} + M_n^{(1)}\\ =& M_{n-1}^{(2)} + \left(2M_{n-1}^{(1)} + n\right)\\ =& M_{n-1}^{(2)} + 2\left(M_{n-1}^{(2)} – M_{n-2}^{(2)}\right) + n\\ =& 3M_{n-1}^{(2)} – 2M_{n-2}^{(2)} + n, \end{aligned}\] by an analogue argument as we apply in Proposition 1.2. When using this relation iteratively, one get \[\begin{aligned} M_n^{(2)} &= 2M_{n-1}^{(2)} + M_{n-1}^{(2)} – 2M_{n-2}^{(2)} + n\\ &= 2M_{n-1}^{(2)} + \left[3M_{n-2}^{(2)} – 2M_{n-3}^{(2)} + (n-1)\right] – 2M_{n-2}^{(2)} + n\\ &= 2M_{n-1}^{(2)} + M_{n-2}^{(2)} – 2M_{n-3}^{(2)} + (n-1) + n\\ &= 2M_{n-1}^{(2)} + \left[3M_{n-3}^{(2)} – 2M_{n-4}^{(2)} + (n-2)\right] – 2M_{n-3}^{(2)} + (n-1) + n\\ &= 2M_{n-1}^{(2)} + M_{n-3}^{(2)} – 2M_{n-4}^{(2)} + (n-2) + (n-1) + n\\ &= \cdots \\ &= 2M_{n-1}^{(2)} + 1 + 2 + \cdots + n\\ &= 2M_{n-1}^{(2)} + \binom{n+1}{2}. \end{aligned} \label{recurr2} \tag{10}\]
Namely, all terms apart of \(1, 2, \ldots, n, 2 M_{n}^{(2)}\) cancel each other which immediately gives the relation above. Similarly, for \(3\)-Mersenne numbers we obtain the recurrence relation \[\begin{aligned} \label{recurr3} M_{n}^{(3)} = 2 M_{n-1}^{(3)} + \binom{n+2}{3}, \end{aligned} \tag{11}\] this time summing triangular numbers. Thus, to get binomial coefficient in (10) and (11) we employ the well known binomial identity \[\begin{aligned} \label{hockeystickIdentity} \sum_{j=k}^n \binom{j}{k} = \binom{n+1}{k+1}, \end{aligned}\] (as we also did when proving Proposition 1.2). Indeed, the pattern that one may anticipate on relations (10), (11) and Proposition 1.2 holds true. We prove it in the following Theorem 3.1.
Theorem 3.1. The \(n\)-th \(r\)-Mersenne number is equal to the sum of twice the value of its predecessor and \(n\)-th \(r\)-figurate number, \[\begin{aligned} M_{n}^{(r)} = 2 M_{n-1}^{(r)} + F_n^{(r)}. \end{aligned}\]
Proof. The base case \(r=1\) is given by formula (10). Assuming that for the \((r-1)\)-Mersenne numbers relation \[M_{n}^{(r-1)} = 2 M_{n-1}^{(r-1)} + \binom{n+r-2}{r-1},\] holds true, we obtain \[\begin{aligned} M_n^{(r)} &= M_{n-1}^{(r)} + M_n^{(r-1)}\\ &= M_{n-1}^{(r)} + \left(2M_{n-1}^{(r-1)} + \binom{n+r-2}{r-1}\right)\\ &= M_{n-1}^{(r)} + 2\left(M_{n-1}^{(r)} – M_{n-2}^{(r)}\right)+ \binom{n+r-2}{r-1}\\ &= 3M_{n-1}^{(r)} – 2M_{n-2}^{(r)} + \binom{n+r-2}{r-1}. \end{aligned} \label{generalRecurrForTelescoping} \tag{13}\]
In the second step of the proof, we iteratively use recurrence (13) to get \[\begin{aligned} M_{n}^{(r)} =& 2 M_{n-1}^{(r)} + M_{n-1}^{(r)} – 2 M_{n-2}^{(r)} + \binom{n+r-2}{r-1} \\ =& 2 M_{n-1}^{(r)}+ \left( 3M_{n-2}^{(r)} – 2 M_{n-3}^{(r)} + \binom{n+r-3}{r-1} \right) – 2 M_{n-2}^{(r)} + \binom{n+r-2}{r-1}\\ =& 2 M_{n-1}^{(r)}+ 2 M_{n-2}^{(r)} + \cdots + 2M_{2}^{(r)} +\left( 3M_{1}^{(r)}-2M_{0}^{(r)} + \binom{r}{r-1}\right)\\ & – 2M_{1}^{(r)} – \cdots -2M_{n-2}^{(r)} + \binom{r+1}{r-1} + \binom{r+2}{r-1} + \cdots + \binom{n+r-2}{r-1}\\ =& 2\sum_{k=1}^{n-1}M_{k}^{(r)}-2\sum_{k=1}^{n-2}M_{k}^{(r)}+M_{1}^{(r)}-2M_{0}^{(r)}+\sum_{k=0}^{n-2}\binom{r+k}{r-1}\\ =& 2 M_{n-1}^{(r)} +\sum_{k=0}^{n-1}\binom{r-1+k}{r-1}, \end{aligned}\] since \(M_{0}^{(r)}=0\) and \(M_{1}^{(r)}=1=\binom{r-1}{r-1}\). When applying identity (12) and the fact that \[\sum_{k=0}^{n-1}\binom{r-1+k}{r-1}=\sum_{j=r-1}^{n+r-2}\binom{j}{r-1},\] the sum of appearing binomial coefficients is equal to the \(n\)-th \(r\)-figurate number, i.e. we have \[\begin{aligned} M_{n}^{(r)} = 2 M_{n-1}^{(r)} + \binom{n+r-1}{r}. \end{aligned}\]
Application of the Pascal’s formula (9) for figurate numbers completes the proof. ◻
Using relation (5) hyper-Mersenne sequences can be defined by the vector recurrence relation \[\begin{aligned} \label{vecrecurrelation} \begin{pmatrix} M_{n+1}^{(r)} & M_{n+2}^{(r)} & \cdots & M_{n+r+2}^{(r)} \end{pmatrix} = \begin{pmatrix} M_n^{(r)} & M_{n+1}^{(r)} & \cdots & M_{n+r+1}^{(r)} \end{pmatrix} Q_{r+2}, \end{aligned} \tag{14}\] where \(Q_{r+2}\) is a square matrix, \[Q_{r+2}= \begin{pmatrix} 0 & 0 & \cdots & 0 & 0 & (-1)^{r+1}m_{r+2}^{(r)}\\ 1 & 0 & \cdots & 0 & 0 & (-1)^r m_{r+1}^{(r)}\\ 0 & 1 & \cdots & 0& 0 & (-1)^{r-1}m_r^{(r)}\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 & -m_2^{(r)}\\ 0 & 0 & \cdots & 0 & 1 & m_1^{(r)}\\ \end{pmatrix}.\]
We define \(A_{r,n}\) to be the \((r+2)\times (r+2)\) matrix with entries \[(A_{r,n})_{i,j}=M^{(r)}_{n+i+j}, \qquad 0\le i,j\le r+1.\]
That is, \[A_{r,n}= \begin{pmatrix} M_n^{(r)} & M_{n+1}^{(r)} & \cdots & M_{n+r+1}^{(r)} \\ M_{n+1}^{(r)} & M_{n+2}^{(r)} & \cdots & M_{n+r+2}^{(r)} \\ \vdots & \vdots & \ddots & \vdots \\ M_{n+r+1}^{(r)} & M_{n+r+2}^{(r)} & \cdots & M_{n+2r+2}^{(r)} \end{pmatrix}.\]
Lemma 4.1. For \(n\in \mathbb N\) and the matrices \(A_{r,n} \enspace and \enspace Q_{r+2}\) we have \[\begin{aligned} A_{r,n} = A_{r,0} Q_{r+2}^n. \end{aligned}\]
Proof. Relation (14) can be written as \(A_{r,n} = A_{r,n-1} Q_{r+2}\). Applying this relation recursively, we obtain the result by successive right multiplication with \(Q_{r+2}\), \[\begin{aligned} A_{r,n} =& A_{r,n-1} Q_{r+2}\\ =&( A_{r,n-2} Q_{r+2}) Q_{r+2} \\ =& A_{r,n-2} Q_{r+2}^2 \\ =& A_{r,0} Q_{r+2}^n. \end{aligned}\] ◻
Example 4.2. For the second generation of the hyper-Mersenne numbers we have \[\begin{aligned} A_{2,0}= \begin{pmatrix} M_0^{(2)} & M_1^{(2)} & M_2^{(2)}& M_3^{(2)} \\ M_1^{(2)} & M_2^{(2)} & M_3^{(2)}& M_4^{(2)} \\ M_2^{(2)} & M_3^{(2)} & M_4^{(2)}& M_5^{(2)} \\ M_3^{(2)} & M_4^{(2)} & M_5^{(2)}& M_6^{(2)} \end{pmatrix} = \begin{pmatrix} 0 & 1 & 5 & 16 \\ 1 & 5 & 16 & 42 \\ 5&16 & 42 & 99 \\ 16 & 42 & 99 & 219 \end{pmatrix}, \end{aligned}\] \[\begin{aligned} Q_4=\begin{pmatrix} 0&0&0&-m_4^{(2)}\\1&0&0&m_3^{(2)}\\0&1&0&-m_2^{(2)}\\0&0&1&m_1^{(2)} \end{pmatrix} = \begin{pmatrix} 0&0&0&-2\\1&0&0&7\\0&1&0&-9\\0&0&1&5 \end{pmatrix}. \end{aligned}\]
Now we determine the matrix \(A_{2,3}\) by Lemma \(\ref{thmrelzeron}\), \[\begin{aligned} A_{2,3} = & \begin{pmatrix} 0 & 1 & 5 & 16 \\ 1 & 5 & 16 & 42 \\ 5&16 & 42 & 99 \\ 16 & 42 & 99 & 219 \end{pmatrix} \cdot \begin{pmatrix} 0&0&0&-2\\1&0&0&7\\0&1&0&-9\\0&0&1&5 \end{pmatrix}^3 \\ =& \begin{pmatrix} 16&42&99&219\\ 42&99&219&466\\99&219&466&968\\219&466&968&1981 \end{pmatrix}. \end{aligned}\]
Lemma 4.3. For \(r \in \mathbb N\) we have \(\det(Q_{r+2})=2\).
Proof. The Laplace expansion along the first row give us \[\begin{aligned} \det(Q_{r+2})=& \begin{vmatrix} 0 & \cdots & 0 & (-1)^{r+1}m_{r+2}^{(r)}\\ 1 & \cdots & 0 & (-1)^r m_{r+1}^{(r)}\\ \vdots & \ddots & \vdots & \vdots \\ 0 & \cdots & 1 & m_1^{(r)}\\ \end{vmatrix}\\ =&(-1)^{r+3}(-1)^{r+1}m_{r+2}^{(r)}\\ =& m_{r+2}^{(r)}=2. \end{aligned}\] ◻
Theorem 4.4. For \(r \in \mathbb N\) and \(n \in \mathbb N_0\) determinant of a matrix \(A_{r,n}\) is \[\begin{aligned} \det(A_{r,n}) = (-1)^{ \lfloor \frac{r+2}{2} \rfloor} 2^{n+r}, \end{aligned}\]
Proof. Firstly we calculate \[\det(A_{r,0})=\det \begin{pmatrix} M_0^{(r)} & M_1^{(r)} & \cdots & M_r^{(r)} & M_{r+1}^{(r)}\\ M_1^{(r)} & M_2^{(r)} & \cdots & M_{r+1}^{(r)} & M_{r+2}^{(r)}\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ M_r^{(r)} & M_{r+1}^{(r)} & \cdots & M_{2r}^{(r)} & M_{2r+1}^{(r)}\\ M_{r+1}^{(r)} & M_{r+2}^{(r)} & \cdots & M_{2r+1}^{(r)} & M_{2r+2}^{(r)}\\ \end{pmatrix}.\]
We evaluate the determinant using elementary column and row operations. Firstly, we perform successive column subtractions from right to left: for each \(j=r+2,r+1,\dots,2\), we replace the \(j\)-th column by the difference between the \(j\)-th and the \((j-1)\)-st columns. We then repeat this procedure in a triangular manner, applying it to the last \(r+1\) columns, then to the last \(r\) columns, and so on, until it is applied only to the last two columns. After these operations, we obtain that \(\det(A_{r,0})\) is \[\begin{aligned} \det(A_{r,0}) =&\det \begin{pmatrix} M_0^{(r)} & M_1^{(r-1)} & \cdots & M_r^{(0)} & M_{r+1}^{(0)}\\ M_1^{(r)} & M_2^{(r-1)} & \cdots & M_{r+1}^{(0)} & M_{r+2}^{(0)}\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ M_r^{(r)} & M_{r+1}^{(r-1)} & \cdots & M_{2r}^{(0)} & M_{2r+1}^{(0)}\\ M_{r+1}^{(r)} & M_{r+2}^{(r-1)} & \cdots & M_{2r+1}^{(0)} & M_{2r+2}^{(0)}\\ \end{pmatrix}. \end{aligned}\]
Next, we replace the \((r+2)\)nd column by subtracting twice the \((r+1)\)-st column from it. Using the relation \(M^{(0)}_{n+1}=2M^{(0)}_n+1\) that follows from Definition 1.3 it follows that all entries in the \((r+2)\)nd column are equal to \(1\): \[\begin{aligned} \det(A_{r,0}) =&\det \begin{pmatrix} M_0^{(r)} & M_1^{(r-1)} & \cdots & M_r^{(0)} & 1\\ M_1^{(r)} & M_2^{(r-1)} & \cdots & M_{r+1}^{(0)} & 1\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ M_r^{(r)} & M_{r+1}^{(r-1)} & \cdots & M_{2r^{(0)}} & 1\\ M_{r+1}^{(r)} & M_{r+2}^{(r-1)} & \cdots & M_{2r+1}^{(0)} & 1\\ \end{pmatrix}. \end{aligned}\]
We then interchange the columns symmetrically, namely, the first with the \((r+2)\)nd, the second with the \((r+1)\)-st, the third with the \(r\)-th, and so on. This changes the determinant by the factor \((-1)^{\lfloor (r+2)/2 \rfloor}\).
After that, we perform the same sequence of operations on the rows of the resulting matrix until we obtain an upper triangular matrix: \[\begin{aligned} \det(A_{r,0}) =& (-1)^{\lfloor \frac{r+2}{2} \rfloor}\det \begin{pmatrix} 1 & M^{(0)}_r & M_{r-1}^{(1)} & \cdots & M_1^{(r-1)} & M_0^{(r)}\\ 0 & M^{(0)}_r +1 & M^{(0)}_r & \cdots & M_2^{(r-2)} & M_1^{(r-1)}\\ 0 & 0 & 1 & \cdots & M_3^{(r-3)}-M_2^{(r-2)} &M_2^{(r-2)}- M_1^{(r-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & M^{(0)}_r – M_{r-1}^{(1)}\\ 0 & 0 & 0 & \cdots & 0 & 1\\ \end{pmatrix}\\ =&(-1)^{\lfloor \frac{r+2}{2} \rfloor}(M^{(0)}_r+1)\\ =&(-1)^{\lfloor \frac{r+2}{2} \rfloor}2^r. \end{aligned}\]
By Lemma 4.1 and Lemma 4.3, we finally obtain \[\begin{aligned} \det(A_{r,n})=&\det(A_{r,0})(\det(Q{r+2}))^n\\=&(-1)^{\lfloor \frac{r+2}{2} \rfloor}2^{r+n}, \end{aligned}\] which completes the proof. ◻
Example 4.5. As an illustration of Theorem 4.4, consider the matrix \(A_{2,3}\) given by \[\begin{aligned} A_{2,3}= \begin{pmatrix} M_0^{(2)} & M_1^{(2)} & M_2^{(2)}& M_3^{(2)} \\ M_1^{(2)} & M_2^{(2)} & M_3^{(2)}& M_4^{(2)} \\ M_2^{(2)} & M_3^{(2)} & M_4^{(2)}& M_5^{(2)} \\ M_3^{(2)} & M_4^{(2)} & M_5^{(2)}& M_6^{(2)} \end{pmatrix} = \begin{pmatrix} 16&42&99&219\\ 42&99&219&466\\99&219&466&968\\219&466&968&1981 \end{pmatrix}. \end{aligned}\]
We compute its determinant using the same elementary column and row transformations as in the proof of Theorem 4.4. First, subtract consecutive columns from right to left: replace the fourth column by \(C_4-C_3\), the third by \(C_3-C_2\), and the second by \(C_2-C_1\). This yields \[\begin{aligned} A_{2,3} = \begin{pmatrix} 16&26&57&120\\ 42&57&120&247\\ 99&120&247&502\\ 219&247&502&1013 \end{pmatrix}. \end{aligned}\]
Next, applying the column operations \(C_4 \leftarrow C_4 – C_3\) and \(C_3 \leftarrow C_3 – C_2\) yields the first matrix below, while the subsequent transformation \(C_4 \leftarrow C_4 – 2C_3\) produces the second one. \[\begin{aligned} A_{2,3} = \begin{pmatrix} 16&26&31&63\\ 42&57&63&127\\ 99&120&127&255\\ 219&247&255&511 \end{pmatrix}= \begin{pmatrix} 16&26&31&1\\ 42&57&63&1\\ 99&120&127&1\\ 219&247&255&1 \end{pmatrix}. \end{aligned}\]
Interchanging the first and the fourth columns, as well as the second and the third columns, we change the determinant by the factor \((-1)^2\). Hence, \[\begin{aligned} \det{A_{2,3}} = (-1)^2\det{\begin{pmatrix} 1&31&26&16\\ 1&63&57&42\\ 1&127&120&99\\ 1&255&247&219 \end{pmatrix}}. \end{aligned}\]
Finally, applying successive row subtractions, we obtain \[\begin{aligned} \det{A_{2,3}} =\det{\begin{pmatrix} 1&31&26&16\\ 0&32&31&26\\ 0&0&1&5\\ 0&0&0&1 \end{pmatrix}}. \end{aligned}\]
Therefore, \[\det(A_{2,3}) =1\cdot 32\cdot1\cdot1=32\left(= (-1)^{\lfloor \frac{2+2}{2} \rfloor} 2^{3+2}\right),\] which agrees with Theorem 4.4.
Remark 4.6(Numerical Verification).We verify Theorem 4.4 for several small values of \(r\) and \(n\).
For \(r=1\) and \(n=0\), \[A_{1,0}= \begin{pmatrix} 0 & 1&4\\ 1 & 4&11\\ 4&11&26 \end{pmatrix}, \qquad \det(A_{1,0})=-2,\] which agrees with \[(-1)^{\lfloor (1+2)/2 \rfloor}2^{0+1}=-2.\] For \(r=2\) and \(n=1\), \[A_{2,1}= \begin{pmatrix} 1 & 5 & 16 & 42\\ 5 & 16 & 42 & 99\\ 16 & 42 & 99 & 219\\ 42 & 99 & 219 & 466 \end{pmatrix}, \qquad \det(A_{2,1})=8,\] which matches \[(-1)^{\lfloor (2+2)/2 \rfloor}2^{1+2}=8.\]
These explicit computations confirm the validity of Theorem 4.4 for small parameters.
For every \(r \ge 0\), the resulting sequence coincides with either \(A00079\) or its negation \(-A00079\) in the On-Line Encyclopedia of Integer Sequences (OEIS)[13], with the starting index shifted by one position for each increment of \(r\).
For parameter \(n=1\) Theorem 4.4 gives the sequence \[(-2,\enspace -4, \enspace 8, \enspace 16, \enspace -32,\enspace -64, … ,(-1)^{\left \lfloor{ \frac{r+2}{2}} \right\rfloor} 2^{1+r}, …),\] which is the sequence A120617 in OEIS.
It is well known that the classical Mersenne numbers \(M_n = 2^n-1\) are closely related to the Stirling numbers of the second kind. More precisely, the number of set partitions of an \((n+1)\)-element set into exactly two non-empty subsets is equal to \(M_n\), \[S(n+1, k) = 2^n-1 =M_n.\]
There are similar connection with Eulerian numbers, \[\left\langle {n+1 \atop 1} \right\rangle = M_n^{(1)}.\]
This provides a natural interpretation of Mersenne numbers in a combinatorial context. As such, it is natural to ask whether there exists a combinatorial interpretation of hyper-Mersenne numbers in term of related discrete structures. We have this as an open problem: Is there a class of combinatorial objects enumerated by \(M_n^{(r)}\) for \(r \ge 2\)?
Divisibility properties of Mersenne numbers are of prominent interest in number theory. This motivate the question how known number theoretical properties are inherited by the hyper-Mersenne numbers.
In the last section of the paper we present the explicit formula for determinant of the matrix consisting of hyper-Mersenne numbers, using algebraic methods. We assume that presented matrices have further regularities, such as positive definiteness and other positivity properties, that might be also related to some physical systems.
The authors thank the anonymous referee for useful comments and suggestions that improved the paper.