Binomial Expansion Using Modular Arithmetic

 1

1    1

1    2    1

1    3    3    1

1    4    6    4    1

1    5    10    10    5    1

1    6    15    20    15    6    1

1    7    21    35    35    21    7    1

Above we see the beginning of Pascal's Triangle, that is of great assistance is working out the coefficients of the terms in the binomial expansion of \( (a+b)^n \) for various positive integer values of \(n\). The first line corresponds to \(n=0\), then \(n=1\), \(n=2\) and so on. For example:$$(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4$$A common mistake that's made by beginner's is to write the following:$$(a+b)^n=a^n+b^n$$What is regarded as a mistake actually turns out to true for certain values of \(n\) when modular arithmetic is involved.

Let's consider mod 2 where only two numbers exist: 0 and 1. Any numbers larger than 1 reduce to either 0 or 1. Thus \(2 \equiv 0 \, mod \, 2\) and \(3 \equiv 1 \, mod \, 2\) etc. Let's look at the expansion of \( (a+b)^2 \) in this light. We have:$$ \begin{align} (a+b)^2 &=a^2+2ab+b^2\\ &=a^2+b^2 \end{align}$$In the case of mod 2, the \(2ab\) term must equal zero What about mod 3? The only numbers here are 0, 1 and 2 with \(3 \equiv 0 \,mod \,3 \). The binomial expansion for the case of \(n=3\) becomes:$$ \begin{align} (a+b)^3 &=a^3+3a^3b+3ab^2+b^3\\ &=a^3+b^3 \end{align}$$Here the \(3a^2b\) and \(3ab^2\) terms equal zero. We seem to on a roll. Let's consider the case of \(n=4\) or mod 4. Here the only numbers are 0, 1, 2 and 3 with \(4 \equiv 0 \, mod \, 4\), \(5 \equiv 1 \, mod \, 4\), \(6 \equiv 2 \, mod \, 4\) and so on. Thus we have:$$ \begin{align} (a+b)^4 &= a^4 + 4a^3b+6a^2b^2+4ab^3+b^4\\ &=a^4 + 2a^2b^2+b^4 \end{align}$$In this case, things don't quite work out because the middle term \(6a^2b^2\) after conversion to \(2a^2b^2\).

What about the case of \(n=5\) or mod 5? Here the numbers are 0, 1, 2, 3 and 4 and the expansion of \( (a+b)^5\) works out as follows:$$ \begin{align} (a+b)^5 &= a^5 + 5a^4b + 10a^3b^2+10a^2b^3+5ab^4+b^5 \\ &=a^5+b^5 \end{align}$$The central terms all disappear because \(5 \equiv 0 \, mod \,5\) and \(10 \equiv 0 \, mod \, 5\). If we consider the case of mod 6, the simplification fails but works again for mod 7. The generalisation from all of this is that if \(p\) is prime and we are working with mod \(p\) then the following always holds true:$$(a+b)^p=a^p+b^p$$I'm thankful to this YouTube video for informing me of this interesting twist on the binomial expansion.

Pentatope Numbers

Today I turned 26176 days old and one of the properties of this number, as listed in the Online Encyclopaedia of Integer Sequences (OEIS), is that it's a member of OEIS A118411:

A118411

Numerator of sum of reciprocals of first n pentatope numbers A000332.

 The sequence runs:

1, 6, 19, 136, 83, 119, 656, 73, 190, 121, 1816, 559, 679, 815, 3872, 1139, 886, 513, 2360, 2023, 2299, 2599, 11696, 3275, 7306, 1353, 5992, 1653, 5455, 5983, 26176, ...

I didn't know what pentatope numbers were so I needed to find out. Firstly, this type of number is a particular example of a more general type of number, the polytope number. It can exist in any number of dimensions and so we can speak of an \(n\)-polytope where \(n\) represents the number of dimensions. However, we get into deep water quickly if we wax too general so I'll bring it back to specifics for the moment by looking at Pascal's triangle (Figure 1).

Figure 1: Derivation of pentatope numbers from
    a left-justified Pascal's triangle. Source.

So a pentatope number could be defined as any number in the fifth cell of any row of Pascal's triangle starting with the 5-term row 1 4 6 4 1. The terms are given by OEIS A000332:

1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, ...

Pascal's triangle lists the binomial coefficients and the pentatope numbers (let's refer to them as \(P_n\)), can be expressed in terms of these coefficients, specifically:$$P_n=\binom{n+3}{4} \text{ where }n \geq 1$$This reads as the number of ways to choose \(n+3\) things four at a time. An alternative representation involves the use of the rising factorial, so that we can write:$$P_n=\frac {n^{ \overline 4}}{4!}=\frac{n(n+1)(n+2)(n-3)}{24} \text { where }n \geq 1$$The infinite sum of the reciprocals of all pentatope numbers is \(\frac{4}{3} \) and this takes us back to OEIS A118411, the sequence that started this post. In other words:$$ \sum^ {\infty}_{n=1} \frac{4!}{n(n+1)(n+2)(n+3)}=\frac{4}{3}$$This sequence only shows the numerators, so let's write some SageMath code to generate the actual fractions (permalink). See Figure 2.

Figure 2

The result is:

(1, 1), (6, 5), (19, 15), (136, 105), (55, 42), (83, 63), (119, 90), (656, 495), (73, 55), (190, 143), (121, 91), (1816, 1365), (559, 420), (679, 510), (815, 612), (3872, 2907), (1139, 855), (886, 665), (513, 385), (2360, 1771), (2023, 1518), (2299, 1725), (2599, 1950), (11696, 8775), (3275, 2457), (7306, 5481), (1353, 1015), (5992, 4495), (1653, 1240), (5455, 4092), (5983, 4488), (26176, 19635)

Now \(\frac{4}{3}=1. \dot{3} \) and even \( \frac{6}{5}=1.2 \) is getting close to this. If we look at the final fraction in the above list, we see that: $$\frac{26176}{19635}=1.33312961548256$$ Clearly the fractions are getting closer to \(1. \dot{3}\). The generating function for the pentatope numbers is:$$ \frac{x}{(1-x)^5}=x+5x^2+15x^3+35x^4+...$$Referring back to Figure 1, it can be seen that the pentatope numbers are the cumulative sums of the tetrahedral number, just as the tetrahedral numbers are the cumulative sums of the triangular numbers and the triangular numbers are the cumulative sums of the natural numbers. 

To quote from this source:

"Pentatope" is a recent term. Regarding the fifth row, Pascal wrote that ... since there are no fixed names for them, they might be called triangulo-triangular numbers. Pentatope numbers exists in the 4D space and describe the number of vertices in a configuration of 3D tetrahedrons joined at the faces.

This is a big topic and a lot more could be said of about pentatopes and polytopes but that will do for now as we are focusing on the pentatope numbers.