TETRAHEDRAL NUMBERS RECIPROCALS SUM

TETRAHEDRAL NUMBERS SERIES:

This post follows with the exercises on special numbers reciprocals related series, after the blog entries about Square Pyramidal Numbers and Polygonal Numbers . In fact, this example it is not very much interesting, but I wanted to write it before to deal with more difficult problems.

$latex \displaystyle T_{n}=\frac{n(n+1)(n+2)}{6}=\binom{n+2}{3}$

$latex \displaystyle S(n)=\sum_{k=1}^{n}{\frac{1}{T_{k}}=\sum_{k=1}^{n}{\frac{6}{k(k+1)(k+2)}$

If we split the main fraction into others:

$latex \displaystyle \frac{S(n)}{6}=\sum_{k=1}^{n}{\frac{1}{k(k+1)(k+2)}}=\sum_{k=1}^{n}{\left( \frac{A}{k}+\frac{B}{k+1}+\frac{C}{k+2} \right) }$

Solving the linear system of equations it gives:

$latex \displaystyle A=\frac{1}{2} \; ; B=-1 \; ; C=\frac{1}{2};$

This three series can be summed easily with the aid of the Harmonic Numbers:

$latex \displaystyle \sum_{k=1}^{n}{\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+ \cdots +\frac{1}{n}=H_n$

$latex \displaystyle \sum_{k=1}^{n}{\frac{1}{k+1}=\frac{1}{2}+\frac{1}{3}+ \cdots +\frac{1}{n}+\frac{1}{n+1}=H_n-1+\frac{1}{n+1}$

$latex \displaystyle \sum_{k=1}^{n}{\frac{1}{k+2}=\frac{1}{3}+\frac{1}{4}+ \cdots +\frac{1}{n}+\frac{1}{n+1}+\frac{1}{n+2}=H_n-1-\frac{1}{2} + \frac{1}{n+1}+\frac{1}{n+2}$


If we substitute everything in the expression for the reciprocals sum:


$latex \displaystyle \frac{S(n)}{6}=\frac{n}{n+1}-\frac{1}{2}-\frac{1}{4} +\frac{1}{2(n+1)}+\frac{1}{2(n+2)}$

In the previous step we can see what does exactly means to be a "telescoping series", the term $latex H_n$, has vanished and there is no need to handle Euler Mascheroni Gamma and Digamma Function:

$latex H_{n}=\gamma + \psi_{0}(n+1)$

Then the formula for the n-th partial sum is:

$latex \displaystyle S(n)=\frac{3n(3+n)}{2(1+n)(2+n)}$

And evaluating the limit we get:

$latex \displaystyle S(\infty)=\lim_{n \leftarrow \infty}{S(n)}=\frac{3}{2}$

---

References:

[1]-Tetrahedral Number at- Wikipedia
[2]-Weisstein, Eric W. "Tetrahedral Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/TetrahedralNumber.html
[3] A000292-Tetrahedral (or pyramidal) numbers: C(n+2,3) = n(n+1)(n+2)/6. The On-Line Encyclopedia of Integer Sequences!

---

SPLITTING FTA FUNCTIONS (III)

PILTZ DIVISOR FUNCTIONS (2)


THEOREM-2:

$latex \tau_{j+k}(n)=\sum_{d|n}^{}{\tau_{j}(d)\cdot\tau_{k}\left(\frac{n}{d}\right)}$

Proof:

The Piltz Divisor functions are multiplicative, so it is only necessary to prove the case $latex p^{\alpha}$

In the previous post we saw how:

$latex \tau_{k}(p^\alpha)=\binom{\alpha+k-1}{k-1}$

And if we apply $latex p^\alpha$ to second member of the problem identity, then:

$latex f(p^\alpha)=\sum_{d|p^\alpha}^{}{\tau_{j}(d)\cdot\tau_{k}\left(\frac{p^\alpha}{d}\right)}=\sum_{i=0}^{\alpha}{\tau_{j}(p^i)\cdot\tau_{k}(p^{\alpha-i})=\sum_{i=0}^{\alpha}{\binom{i+j-1}{j-1}\binom{\alpha-i+k-1}{k-1}=$

$latex =\binom{\alpha+j+k-1}{j+k-1}=\tau_{j+k}(p^\alpha)$

This proof seems easy except for the binomial identity step:

$latex \sum_{i=0}^{\alpha}{\binom{i+j-1}{j-1}\binom{\alpha-i+k-1}{k-1}=\binom{\alpha+j+k-1}{j+k-1}$

After several unfruitful tries to prove it, due to my lack of mathematical skills, I resigned myself to look for information about this problem on the bibliography, this formula look very close to the one found on reference [1] or [2], but with an additional variable, and after many reviews, I was glad to find a combinatorial version of the proof into the book of Chuan Chong Chen and Khee-Meng Koh [3]

This proof solved the problem, but it let me very much unsatisfied, and I begun to rethink about this topic again.

This problem is about Number Theory and not Combinatorics, and I had to revise the first lesson about the properties of Dirichlet Product:

Dirichlet´s functional convolution is associative: we can put the brackets wherever we want, so:

$latex \tau_{j+k}(n)=(\underbrace{I_{0}(n)*...*I_{0}(n)}_{j}) *( \underbrace{I_{0}(n)*...*I_{0}(n)}_{k})=\tau_{j}(n)*\tau_{k}(n)$

This simple line proves this trivial property of the Piltz functions that I pedanticly considered as a Theorem, and it proves, as a tip, the binomial formula. The readers of this blog (if any) may forgive me.

But after all of this mess, I´ve learned many interesting things:

1) Number Theory counts with powerful mathematical tools than can be used for many unexpected purposes, just to mention the relationship between the Piltz functions and the Jacobi polynomials.
2) The properties of arithmetical functions can be used to get elegant proofs for binomial identities. (This is the opposite way that the one I took).
3) In my effort to deal with binomial identities, I discovered some formulas for determinants of matrices with binomial coefficients. (Well, there´s many articles about this topic, but I worked without previous knowledge of them). Anyhow, I haven´t found this formula somewhere but here.

---

References:

[1]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom -Catalog #: 31000005
[2]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 - Concrete Mathematics - Identity (5.26)
[3]-Chuan Chong Chen,Khee-Meng Koh - Principles and techniques in combinatorics page 88-Example 2.6.2-Shortest Routes in Rectangular Grid.

---

SPLITTING FTA FUNCTIONS (II)

PILTZ DIVISOR FUNCTIONS (1)


INTRO:

If we look for an example of "Functions that depend only on coefficients", our first idea should be the divisor function, $latex \tau_{2}(n)$ because it is multiplicative with:

$latex \tau_{2}(p^\alpha)=1+\alpha$

Here, they only appear the coefficients but not the primes.

With the help of recursive Dirichlet Convolution of the unit, $latex I_{0}(n)=1$, it is possible to construct a sequence of arithmetical functions only dependent on the coefficients of the prime factors of any number, known as Piltz Divisor Functions, $latex \tau_{k}(n)$, because they give the number of distinct solutions of the equation $latex x_{1}x_{2} \cdots x_{k}=n$, where $latex x_{1},x_{2},\cdots,x_{k}$ run indepently through the set of positive integers) or, if preferred, they give the number of ordered factorizations of $latex n$ as a product of $latex k$ terms. (References [3],[4] and [11])

DEFINITION:

$latex \displaystyle \tau_{1}(n)=I_{0}(n)=1 $

$latex \tau_{k}(n)=\sum_{d|n}^{}{\tau_{k-1}(d)\cdot I_{0}(n/d)}=\sum_{d|n}^{}{\tau_{k-1}(d)} $


This recursion can also be notated in terms of Dirichlet Product as:

$latex (f*g)(n)=\sum_{d|n}{f(d)\cdot g(n/d)}$

$latex \tau_{k}(n)=\tau_{k-1}*I_{0}(n)$

---

NOTES ON NOTATION:

The divisor function can be found on the literature as: $latex d(n)$, $latex \sigma_{0}(n)$, $latex \tau(n)$, and in this post as $latex \tau_{2}(n)$.

The "$latex \sigma$´s", and "$latex \tau$´s" are two different series of arithmetical functions that share one element in common: The divisor function. With the help of this two notations, it is possible to remark what kind of series we are working with.

On the other hand the "$latex d$", it is a simple notation that can be used for another purposes, were the belonging to this series of functions, does not matters.

Unfortunately, this happens not only with the divisor function, the mathematical notation on arithmetical functions related to Dirichlet convolution (or product) varies from one book to another, and not only distinct functions are named the same, but all cases of "non-biyectivity" between notations and functions can be found.

Hereinafter we are going to use:

$latex I_{k}(n)=n^{k}$ ( like in Reference [3] but with $latex I_{0}(n)=1$ and $latex I_{1}(n)=n$)

The identity element for Dirichlet´s product (or unit function), using Kronecker´s delta notation, is:

$latex \displaystyle \delta_{1n}= \bigg\lfloor \frac{1}{n} \bigg\rfloor$ (Reference [2])

$latex \omega(n)$ means the number of distinct prime factors of $latex n$

---

PROPERTY:

$latex \tau_{k}(n)$ is multiplicative because $latex \tau_{k-1}(n)$, and $latex \tau_{1}(n)$ are multiplicative.

This property can also be derived from the behavior of the Dirichlet Product, but we must note that although $latex \tau_{1}(n)=I_{0}(n)=1$ is a completely multiplicative function, its convolution: $latex \tau_{2}(n)$ is multiplicative, but it is not completely multiplicative.


THEOREM-1: [1] and [4]

$latex \displaystyle \tau_{k}(n)=\prod_{i=1}^{\omega(n)}{\prod_{j=1}^{k-1}\frac{\alpha_{i}+j}{j}}=\prod_{i=1}^{\omega(n)}{\binom{\alpha_{i}+k-1}{k-1}}; \; (k \ge 1)$


Proof:

$latex \displaystyle \tau_{k}(p^\alpha)=\sum_{d|p^\alpha}^{}{\tau_{k-1}(d)}=\tau_{k-1}(1)+\tau_{k-1}(p)+\tau_{k-1}(p^2)+ \cdots +\tau_{k-1}(p^\alpha)$

$latex \displaystyle \tau_{k}(p^\alpha)= \sum_{i=0}^{\alpha}{\tau_{k-1}(p^i)} =\sum_{i=0}^{\alpha}{\binom{i+k-2}{k-2}=\binom{\alpha+k-1}{k-1}$

Lemma:

$latex \displaystyle \sum_{i=0}^{\alpha}{\binom{i+k-2}{k-2}}=\binom{\alpha+k-1}{k-1}$

Proof:

From Parallel Summation Identity (References [6] and [8]):

$latex \displaystyle \sum_{k=0}^{n}{\binom{k+r}{k}}=\binom{n+r+1}{n}$

Substituing: $latex \displaystyle n\rightarrow{\alpha}$ and $latex \displaystyle k\rightarrow{i}$

$latex \displaystyle \sum_{i=0}^{\alpha}{\binom{i+r}{i}}=\binom{\alpha+r+1}{\alpha}$

$latex \displaystyle r\rightarrow{k-2}$ and with Pascal´s Symmetry Rule [7]:

$latex \displaystyle \sum_{i=0}^{\alpha}{\binom{i+k-2}{i}}= \sum_{i=0}^{\alpha}{\binom{i+k-2}{k-2}}= \binom{\alpha+k-1}{\alpha}=\binom{\alpha+k-1}{k-1}$

---

Corollary-1: Values of $latex \tau_{k}(s)$, being $latex s$ a squarefree number.

If $latex s$ is squarefree then all coefficients of its factorization are $latex \displaystyle \alpha_{i}(s)=1$, then:

$latex \displaystyle \tau_{k}(s)= \prod_{i=1}^{\omega(s)}{\binom{k}{k-1}=k^{\omega(s)}$

For a prime $latex p$, $latex \displaystyle \omega(p)=1$, and $latex \displaystyle \tau_{k}(p)=k$, and if $latex s=1$, then $latex \displaystyle \omega(1)=0$ and $latex \tau_{k}(1)=1$

---

Corollary-2:

$latex \displaystyle \tau_{k+1}(n^k)=\tau_{k}(n^k)\cdot \tau_2(n) $

Proof:

$latex \displaystyle \tau_{k+1}(n)=\tau_{k}(n)\cdot \prod_{i=1}^{\omega(n)}{\frac{\alpha_{i}+k}{k}}$

$latex \displaystyle \tau_{k+1}(n^k)=\tau_{k}(n^k)\cdot \prod_{i=1}^{\omega(n^k)}{\frac{\alpha_{i}+k}{k}}$

Like $latex \displaystyle \omega(n^k)=\omega(n)$, and $latex \displaystyle \alpha_{i}(n^k)=k\cdot\alpha_{i}(n)$:

$latex \displaystyle \tau_{k+1}(n^k)=\tau_{k}(n^k)\cdot \prod_{i=1}^{\omega(n)}{\frac{k \cdot \alpha_i+k}{k}}=\tau_{k}(n^k)\cdot \prod_{i=1}^{\omega(n)}{(\alpha_i+1)}=\tau_{k}(n^k)\cdot \tau_2(n) $

---

References:

[1]-p.167-Exercise 5.b - Leveque, William J. (1996) [1977]. Fundamentals of Number Theory. New York: Dover Publications. ISBN 9780486689067
[2]-T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, pages 29 and 38
[3]-J. Sándor: On the Arithmetical Functions $latex d_{k}(n)$ and $latex d_{k}^{*}(n)$, Portugaliæ Mathematica 53, No. 1 (1996)
[4]-I.Vinogradov, Fundamentos de la Teoría de los Números, Editorial RUBIÑOS, ISBN 84-2222-210-8, Segunda Edición,chapter II, Exercise 11, page 44
[5]-J. Sándor, B. Crstici, Handbook of Number Theory (Vol II), Kluwer Academic Publishers, Springer, 2004 ISBN 1402025467, 9781402025464
[6]-Ken.J.Ward, Ken Ward's Mathematics Pages, Parellel Summation-Formula 2.2.2
[7]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom -Catalog #: 1000001
[8]-Matthew Hubbard and Tom Roby - Pascal's Triangle From Top To Bottom - Catalog #: 1100002
[9]-A000012-The simplest sequence of positive numbers: the all 1's sequence. The On-Line Encyclopedia of Integer Sequences!
[10]-A000005-d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n. The On-Line Encyclopedia of Integer Sequences!
[11]-A007425-d_3(n), or tau_3(n), the number of ordered factorizations of n as n = rst. The On-Line Encyclopedia of Integer Sequences!

---

NOTES ON LEGENDRE'S FORMULA

MORE FACTS ABOUT PRIME FACTORIZATION OF FACTORIALS.

In the previous post, we introduced these functions, just as a small trick to calculate the limit we were looking for, but unlikely of what they seem to be, they are less artificial than expected.

Legendre´s formula for the exponent of p in the prime factorization of n!:

$latex \displaystyle\alpha(n,p)=\sum _{i=1}^{\lfloor log_p(n)\rfloor}{ \bigg\lfloor\frac{n}{p^i} \bigg\rfloor = \sum _{i=1}^{\infty} { \bigg\lfloor\frac{n}{p^i} \bigg\rfloor$

Integer Approximation for the Legendre's formula:

$latex \displaystyle \alpha^{*}(n,p)=\bigg\lfloor \frac{n}{p-1}\bigg\rfloor = \bigg\lfloor\sum _{i=1}^{\infty}{\frac{n}{p^i}}\bigg\rfloor$

The diference between one function and its approximation is the error function.

Error Function for the Legendre's formula:

$latex \displaystyle \epsilon(n,p)=|\alpha^{*}(n,p) - \alpha(n,p) |= \alpha^{*}(n,p) - \alpha(n,p)$

$latex \displaystyle \epsilon(n,p)= \bigg\lfloor\sum _{i=1}^{\infty}{\frac{n}{p^i}}\bigg\rfloor - \sum _{i=1}^{\infty} { \bigg\lfloor\frac{n}{p^i} \bigg\rfloor $

We can use $latex \lfloor x \rfloor = x - \left\{ x \right\}$ to get another beautiful expression for the error function:

$latex \displaystyle \epsilon(n,p)= \sum _{i=1}^{\infty} { \left\{ \frac{n}{p^i} \right\} - \left\{ \sum _{i=1}^{\infty}{\frac{n}{p^i}} \right\} $

This function shows fractal behavior:



Particular Values for $latex \epsilon(n,p)$:

$latex \epsilon(n,2)=A011371(n)=n-A000120(n)$, References [1] and [2]

$latex \epsilon(2^{n},2)=1$

$latex \epsilon(2^{n}+1,2)=2$

$latex \epsilon(p^{n},p)=0; \; (p > 2)$

$latex \epsilon(p^{n}-1,p)=n$

$latex \epsilon(p^{n}+1,p)=0; \; (p > 3)$

More facts about Legendre´s $latex \alpha(n,p)$

$latex \alpha(n,2)$ gives also the number of 1's in binary expansion of $latex n$ (or the sum of all its binary digits).

And if we extend the range of this formula, been $latex b$ any number not necessarily prime, then:

$latex \displaystyle \alpha(b^{n},b)=\frac{b^{n}-1}{b-1}=R_{n}^{(b)}$

It gives the base $latex b$ repunits, and so for base $latex 2$:

$latex \alpha(2^{n},2)=2^{n}-1=M_{n}$

It gives the Mersenne Numbers.

Amazingly, this uninteresting topic, at first sight, becomes a joint between: Repunits, Mersenne numbers, Factorials, primes, fractals, counting of digits...

Number Theory is it!

---

References:

[1]-A011371-n minus (number of 1's in binary expansion of n). Also highest power of 2 dividing n!. The On-Line Encyclopedia of Integer Sequences!
[2]-A000120-1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n). The On-Line Encyclopedia of Integer Sequences!
[3]-Cooper, Topher and Weisstein, Eric W. "Digit Sum." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/DigitSum.html

---

Archives:

[a]-121809-Notes on Legendre´s Formula.nb

---

TRAILING ZEROS IN n!

BEHAVIOR OF THE PERCENTAJE OF TRAILING ZEROS IN THE DECIMAL EXPANSION OF n!

It was many and many a year ago, In a kingdom by the sea , I spent a very good time reading an spanish translation of Martin Gardner´s "Mathematical Magic Show" [1] , just because Annabel was not very much interested on me.

In this compilation from Scientific American, Gardner dedicated some pages to this topic in an article called "Factorial Oddities".

Gardner explained how, as $latex n$ increases, $latex n!$ is having more and more factors including the prime factor $latex 5$, that with other factors with any $latex 2$ it gives $latex 10$´s that accumulates in the decimal expansion of $latex n!$ creating a long tail of zeros [2] that fill the least significant digits of this kind of huge numbers.

As it is possible to calculate this number of trailing zeros without having to expand the whole factorial, I wondered (when I was sixteen) if this final zeros were giving very much information about the digits of the whole factorial number or not.

To answer this question, it is necessary to study the behaviour of $latex PTZ(n)$ the percentage between the trailing zeros and the total number of digits of $latex n!$ when $latex n$ tends to infinity.

Number of Digits of n!: [3]

$latex \displaystyle D_{10}(n!)=1+\lfloor log_{10}(n!) \rfloor$

Exponent of p in the prime factorization of n!: (Legendre´s formula)

$latex \displaystyle\alpha(n,p)=\sum _{i=1}^{\lfloor log_p(n)\rfloor}{ \bigg\lfloor\frac{n}{p^i} \bigg\rfloor $

Number of Trailing Zeros in n!. (See sequence [2])

$latex NTZ(n!)=\alpha(n,5) $

PTZ(n!) = Percentage of trailing zeros of the total digits in n! (%)

$latex \displaystyle PTZ(n!)=100*\frac{NTZ(n!)}{D_{10}(n!)}$

But if we want to test the limit of $latex PTZ(n)$ we need to work more handy bounds of this functions, notated with an added asterisk, and that they are going to hold for:

$latex \displaystyle D_{10}^{*}(n!) < D_{10}(n!)$ $latex \displaystyle NTZ^{*}(n!) \ge NTZ(n!)$ $latex \displaystyle PTZ^{*}(n!) > PTZ(n!)$

Approximation for the Number of Digits of n!:

We can sustitute the famous Stirling's approximation instead of $latex n!$ in the formula for $latex D_{10}(n!)$:

$latex \displaystyle n! \approx \sqrt{2\pi n} \left({\frac{n}{e}\right)}^n$

$latex \displaystyle D_{10}(n!)=\left\lfloor \frac{-n+\left(n+\frac{1}{2}\right) \log (n)+\frac{1}{2} \log (2 \pi )}{\log (10)}\right\rfloor +1 +\delta_{n,1}$

The last formula gives the exact value for the number of digits of $latex n!$, for $latex n>0$, because the error for the Stirling´s formula is $latex O\left(\frac{1}{n}\right)$

But for our purposes we must make some changes inside $latex D_{10}(n)$ to get a continuous lower bound:

$latex \displaystyle D_{10}^{*}(n!)=\frac{-n+\left(n+\frac{1}{2}\right) \log (n)+\frac{1}{2} \log (2 \pi )}{\log (10)} < D_{10}(n)$ Approximation for the Legendre's formula and for the Number of Trailing Zeros:

$latex \displaystyle\alpha(n,p)= \sum _{i=1}^{\lfloor log_p(n)\rfloor} { \bigg\lfloor\frac{n}{p^i} \bigg\rfloor = \sum _{i=1}^{\infty} { \bigg\lfloor\frac{n}{p^i} \bigg\rfloor \leq \bigg\lfloor\sum _{i=1}^{\infty}{\frac{n}{p^i}}\bigg\rfloor =\bigg\lfloor \frac{n}{p-1}\bigg\rfloor =\alpha^{*}(n,p)$

$latex NTZ^{*}(n!) =\frac{n}{4} \ge \bigg\lfloor \frac{n}{4}\bigg\rfloor = \alpha^{*}(n,5) \ge \alpha(n,5)=NTZ(n!)$

Final Result and Limit:

$latex \displaystyle PTZ(n!)\approx PTZ^{*}(n!)=100*\frac{NTZ^{*}(n!)}{D_{10}^{*}(n!)}$

$latex \displaystyle\lim_{n \to{+}\infty}{PTZ^{*}(n!)}=0$

$latex PTZ(n!)$ is always positive and it is upper bounded by a continuous function that tend to zero as $latex n$ tends to infinity.

So the number of trailing zeros of $latex n!$ is giving lesser information about the decimal digits of $latex n!$ when the more grows $latex n$

This result may not cause any surprise, but long time ago I had a lot of fun when I was able to prove and plot it.

This ideas does not finish here, but on the contrary there are many many things than can be derived from this introductory point, and that are going to be material for further development in this blog.

---

References:

[1]-Gardner, M. "Factorial Oddities." Ch. 4 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, pp. 50-65, 1978
[2]-A027868-Number of trailing zeros in n! The On-Line Encyclopedia of Integer Sequences!
[3]-A055642-Number of digits in decimal expansion of n. The On-Line Encyclopedia of Integer Sequences!
[5]-Trailing Zero @ Wikipedia
[6]-Stapel, Elizabeth. "Factorials and Trailing Zeroes." Purplemath. Available from
http://www.purplemath.com/modules/factzero.htm
[7]-A061010-Number of digits in (10^n)!. The On-Line Encyclopedia of Integer Sequences!

---

Archives:

[a]-121209-Number of Trailing Zeros of n!.nb

---