TETRAHEDRAL NUMBERS RECIPROCALS SUM

25 12 2009

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.

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

\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:

\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:

\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:

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

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

\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 sustitute everything in the expression for the reciprocals sum:

\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 H_n, has vanished and there is no need to handle the Euler Mascheroni Gamma and the Digamma Function:

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

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

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

And taking the limit we get:

\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)

23 12 2009

PILTZ DIVISOR FUNCTIONS (2)


THEOREM-2:

\displaystyle\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 p^{\alpha}

In the previous post we saw how:

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

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

\displaystyle 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})}

\displaystyle=\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}=\tau_{j+k}(p^\alpha)

This proof seems easy except for the binomial identity step:

\displaystyle\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, so we can put the brackets wherever we want, so:

\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)

21 12 2009

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, \tau_{2}(n) because it is multiplicative with:

\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, 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, \tau_{k}(n), because they give the number of distinct solutions of the equation x_{1}x_{2} \cdots x_{k}=n, where 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 n as a product of k terms. (References [3],[4] and [11])

DEFINITION:

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

\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:

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

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


NOTES ON NOTATION:

The divisor function can be found on the literature as: d(n), \sigma_{0}(n), \tau(n), and in this post as \tau_{2}(n).
The “\sigma´s”, and “\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 “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:

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

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

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

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


PROPERTY:

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

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

THEOREM: [1] and [4]

\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:

\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)

\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:

\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]):

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

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

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

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

\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 \tau_{k}(s), being s a squarefree number.

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

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

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


Corollary-2:

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

Proof:

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

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

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

\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 d_{k}(n) and 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

18 12 2009

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!:

\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:

\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:

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

\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 \lfloor x \rfloor = x - \left\{ x \right\} to get another beautiful expression for the error function:

\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 \epsilon(n,p):

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

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

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

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

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

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

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

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

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

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

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

\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!

12 12 2009

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 n increases, n! is having more and more factors including the prime factor 5, that with other factors with any 2 it gives 10´s that accumulates in the decimal expansion of 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 PTZ(n) the percentage between the trailing zeros and the total number of digits of n! when n tends to infinity.

Number of Digits of n!: [3]

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

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

\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])

\displaystyle NTZ(n!)=\alpha(n,5)

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

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

But if we want to test the limit of 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:

\displaystyle D_{10}^{*}(n!) < D_{10}(n!)

\displaystyle NTZ^{*}(n!) \ge NTZ(n!)

\displaystyle PTZ^{*}(n!) > PTZ(n!)

Approximation for the Number of Digits of n!:

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

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

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

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

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

\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:

\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)

\displaystyle 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:

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

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

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

So the number of trailing zeros of n! is giving lesser information about the decimal digits of n! when the more grows 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






BINOMIAL MATRIX (III)

24 10 2009

If A_n is an square matrix with elements:

\displaystyle a_{i,j}=\binom{i+j+k}{i}

Then:

\displaystyle |A_{n}|=\binom{n+k+1}{k+1}=\binom{n+k+1}{n}


Proof:

The \displaystyle A_{n} matrix can be decomposed as the product of a lower triangular matrix, L_{n}, and an upper triangular matrix, U_{n}:

\displaystyle A_{n}=L_{n}*U_{n}

Example:

A_{3}=

\displaystyle \left(\begin{array}{ccc} 2+k & 3+k & 4+k \\ \frac{1}{2} (2+k) (3+k) & \frac{1}{2} (3+k) (4+k) & \frac{1}{2} (4+k) (5+k) \\ \frac{1}{6} (2+k) (3+k) (4+k) & \frac{1}{6} (3+k) (4+k) (5+k) & \frac{1}{6} (4+k) (5+k) (6+k)\end{array}\right)

\displaystyle L_{n}=\left( \begin{array}{ccc} 1 & 0 & 0 \\ \frac{3+k}{2} & 1 & 0 \\ \frac{1}{6} (3+k) (4+k) & \frac{2 (4+k)}{3} & 1 \end{array} \right)

\displaystyle U_{n}=\left(\begin{array}{ccc} 2+k & 3+k & 4+k \\ 0 & \frac{3+k}{2} & 4+k \\ 0 & 0 & \frac{4+k}{3} \end{array} \right)

After some trial and error puzzle, we can propose as decomposition:

\displaystyle l_{i,j}=\frac{j}{i} \binom{i+k+1}{j+k+1}

\displaystyle u_{i,j}=\frac{j+k+1}{j}\binom{j}{i}

If this decomposition is the correct one then the matrix product should be a_{i,j}:

\displaystyle \sum_{r=1}^n{l_{i,r} \cdot u_{r,j}}=\sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}

Where:

\displaystyle l_{i,r}=\frac{r}{i} \binom{i+k+1}{r+k+1}

\displaystyle u_{r,j}=\frac{j+k+1}{j}\binom{j}{r}

l_{i,r}\cdot u_{r,j}, can be simplified, changing the binomial coefficient to the gamma function, as:

\displaystyle l_{i,r} \cdot u_{r,j}=\frac{j+k+1}{i}\binom{j-1}{r-1}\binom{i+k+1}{r+k+1}

\displaystyle \sum_{r=1}^{min(i,j)}{l_{i,r} \cdot u_{r,j}}=\sum_{r=1}^{min(i,j)}{\frac{j+k+1}{i}\binom{j-1}{r-1}\binom{i+k+1}{r+k+1}} =

\displaystyle = \frac{j+k+1}{i} \cdot \sum_{r=1}^{min(i,j)}{\binom{j-1}{r-1}\binom{i+k+1}{r+k+1}} = \frac{j+k+1}{i} \cdot \binom{i+j+k}{j+k+1}=

\displaystyle=\frac{i}{i}\cdot \binom{i+j+k}{j+k}=\binom{i+j+k}{i} =a_{i,j}

In the last part of the proof, involving binomial coefficients, we have used: (See ref [1] and [2])

1) \displaystyle \sum_{r}^{}{\binom{l}{r+m} \binom{s}{r+n}}=\binom{l+s}{l-m+n}

2) \displaystyle r\binom{i}{r}=i \binom{i-1}{r-1}

Now we can calculate easily |A_n|, because the LU-decomposition used is the so called Doolittle decomposition, where the matrix L_{n} has all ones on its diagonal.

\displaystyle |A_{n}|=\prod_{i=1}^{n}{l_{i,i} \cdot u_{i,i}}=\prod_{i=1}^{n}{u_{i,i}}=\prod_{i=1}^{n}{\frac{i+k+1}{i}}=\binom{n+k+1}{n}


Archives:[a]-092609-Binomial Matrix (III).nb


References:

[1]-Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994 – Concrete Mathematics – Identity (5.32) in Table 169.
[2]-Matthew Hubbard and Tom Roby – Pascal’s Triangle From Top To Bottom – the binomial coefficient website– Catalog #: 3100004.
 
  





THE CLONE WARS

24 10 2009

I´m tired of rewritting the same posts again and again due to the problems with the external \LaTeX services that work with blogger, so I decided to make some changes in order to be the more self-sufficient as possible.

1) I´ve changed mathtex3.js, the java code that gives the blog \LaTeX functionality (In particular some lines inside the Don’t MOdify Under THis Line Unless You Know What You Are Doing !! piece of code). I hope this does not cause too much damage inside the Death Star.

2) Now, I´ve uploaded this modified java code, to my web page: (Psychedelic-mathtex.js). Now, this code, depends on me, but in the end, this java program invokes the external servers: http://www.forkosh.dreamhost.com/mathtex.cgi and http://mathcache.appspot.com/

3) With the modifications inside Psychedelic-mathtex.js, I can use the same post indistinctively in Blogger and in WordPress.

4) Now, this blog, has a clon copy in WordPress.com , under the original and unexpected name of Psychedelic Geometry

5) WordPress offers its own \LaTeX service, so I expect some stability.

6) I´ve begun, also, another blog about technology, chemistry, and many other things I ignore, called: Psychedelic Thermodynamics