Product rule for simplex numbers

172 Views Asked by At

The $n$th triangular number is defined as $T_2(n) = n(n+1)/2$, and there is an interesting product rule for triangular numbers: $$T_2(mn) = T_2(m)\,T_2(n) + T_2(m-1)\,T_2(n-1).$$

The tetrahedral numbers $T_3(n) = n(n+1)(n+2)/6$ satisfy a similar product rule: $$T_3(mn) = T_3(m)\,T_3(n) + 4 T_3(m-1)\,T_3(n-1) + T_3(m-2)\,T_3(n-2).$$

Can these product rules be generalized to higher dimensions? Are there analogous formulas for $T_k(mn)$, where $$T_k(n) = \frac1{k!} n(n+1)(n+2)\cdots(n+k-1)\ ?$$

2

There are 2 best solutions below

0
On

By denoting with $(n)_k$ the falling Pochhammer symbol $$(n)_k = n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$$ we have: $$ (mn+1)_2 = \frac{1}{2}\left((m+1)_2(n+1)_2+(m)_2(n)_2\right)\tag{1}$$ that leads to the first identity. Since: $$ (mn+2) = \alpha(n+2)(m+2)+\beta(n-1)(m-1) $$ is solved by $\alpha=\frac{1}{3}$ and $\beta=\frac{2}{3}$ and $$ (mn+2) = \gamma(n+1)(m+1)+\delta(n-2)(m-2)$$ is solved by $\gamma=\frac{2}{3}$ and $\delta=\frac{1}{3}$, multiplying both sides of $(1)$ by $(mn+2)$ we get: $$ (mn+2)_3 = \frac{1}{6}\left((m+2)_3(n+2)_3+4(m+1)_3(n+1)_3+(m)_3(n)_3\right)\tag{2}$$ that leads to the second identity.

Trying to reproduce the same argument, we may look for $\alpha$ and $\beta$ such that: $$(mn+3)=\alpha(m+3)(n+3)+\beta(m-1)(n-1),$$ so equating the coefficients of $mn$ we get $\alpha+\beta=1$ and equating the coefficients of $(m+n)$ we get $3\alpha-\beta=0$, from which $\alpha=\frac{1}{4},\beta=\frac{3}{4}$. The constant terms match since $\frac{9}{4}+\frac{3}{4}=3$. So we go on and try to find $\gamma,\delta$ such that: $$(mn+3)=\gamma(m+2)(n+2)+\delta(m-2)(n-2).$$ However, by choosing $\gamma=\delta=\frac{1}{2}$ the constant term does not match. Ouch. This gives that the formula for pentatope numbers depends on tetrahedral numbers, too. For istance, by multiplying both sides of $(2)$ by $(mn+3)$ we get: $$\begin{array}{rcl}(mn+3)_4 &=& \frac{1}{24}\left((m+3)_4(n+3)_4+11(m+2)_4(n+2)_4\right. \\&+&\left.11(m+1)_4(n+1)_4+(m)_4(n)_4\color{red}{-16(m+1)_3(n+1)_3}\right).\end{array}\tag{3}$$

If we don't care introducing further terms, we can simply go on as we did for producing $(3)$ from $(2)$.

0
On

The n'th K'th-Simplex number is (2 = triangle, 3 = tetrahedral, etc...)

$$T_k{(n)} = \frac{1}{k!} \frac{(n+k-1)!}{(n - 1)!} = \begin{pmatrix} n + k - 1 \\ k\end{pmatrix}$$

It appears that without exploiting the above fact there are multiple product rules that can be derived:

One possible strategy to derive product rules is to use Induction

Note that $$T_k(n) = \frac{n + k - 1}{k} T_{k-1} (n) $$

Then notice

$$T_2(n) - T_2(n-1) = n$$ $$T_3(n) - 2 T_3(n-1) + T_3(n-2) = n$$ And in general

$$ \sum_{i = 0}^{k-1} \left[ (-1)^i \begin{pmatrix} k -1 \\ i \end{pmatrix} T_k(n- i)\right] = n$$

And as a corollary to this

$$T_{k+1}(m) - T_{k+1}(m-1) = T_{k}(m)$$

So now let us attempt to derive a general product rule for $T_k(mn)$ assuming we know the product rule for $T_{k-1}(mn)$ as

$$ T_{k-1} = P(T_{k-1}(m), T_{k-1}(n), T_{k-1}(m-1), T_{k-1}(n-1) ... )$$

We immediately find that each argument $T_{k-1}(w)$ of P can be re-written as $T_{k}(w) - T_{k}(w-1)$ and therefore $P$ can be rewritten as function of terms of the form $T_k$ furthermore:

$$ T_k(mn) = \frac{mn + k - 1}{k}T_{k-1}(mn)$$

$$ T_k(mn) = \frac{mn + k - 1}{k}P$$

Now using the above summation formulas (we conclude)

$$ T_k(mn) = \frac{\left( \sum_{i = 0}^{k-1} \left[ (-1)^i \begin{pmatrix} k -1 \\ i \end{pmatrix} T_k(m- i)\right] \right) \left( \sum_{i = 0}^{k-1} \left[ (-1)^i \begin{pmatrix} k -1 \\ i \end{pmatrix} T_k(n- i)\right] \right) + k - 1}{k} P$$

Thus giving us a messy BUT working general rule for deriving product identities given a previous product identity $P$. Convert each term in this identity into the higher $T_k$ form and then proceed to compute:

$$frac{\left( \sum_{i = 0}^{k-1} \left[ (-1)^i \begin{pmatrix} k -1 \\ i \end{pmatrix} T_k(m- i)\right] \right) \left( \sum_{i = 0}^{k-1} \left[ (-1)^i \begin{pmatrix} k -1 \\ i \end{pmatrix} T_k(n- i)\right] \right) + k - 1}{k}$$

multiply those two and a new product identity has been found

using this we attempt to derive the triangular number identity from just the normal numbers

$$T_1(mn) = T_1(m) T_1(n)$$

Therefore

$$T_1(mn) = (T_2(m) - T_2(m-1))(T_2(n) - T_2(n-1))$$

Now

$$T_2(mn) = \frac{mn + 1}{2}T_2(mn)$$

$$m = T_2(m) - T_2(m-1)$$ $$n = T_2(n) - T_2(n-1)$$

Therefore

$$T_2(mn) = \frac{(T_2(m) - T_2(m-1))(T_2(n) - T_2(n-1))+1}{2}(T_2(m) - T_2(m-1))(T_2(n) - T_2(n-1)) $$

This is and further derivations appear to be non-trivially different from the product rules you have come across. That is unless one actually simplifies both product rules it isn't obvious how to simplify one into the other