Monday, October 28, 2019

Proving triangular number congruence patterns

For the patterns proven in this post, see here and here.

1. The formula for triangular numbers is Tn = n(n + 1) ÷ 2

This is common knowledge, but I include it for the benefit of any readers who may be even less mathematically inclined than myself.

The nth triangular number (written Tn) is the sum of the natural numbers from 0 to n. Such numbers are called "triangular" because that number of points can be arranged in a triangular configuration as shown below.


Deriving the formula for triangular numbers is fairly straightforward. Take a given number, n, and write out 1 + 2 + ... + n. The sum of those numbers will be Tn. Now, below that, write the same sum in the opposite direction, n + n-1 + ... + 1. The example below shows what this looks like for n = 5.


Each of the two rows adds up to Tn, so the total of the two rows is 2Tn. If we look at the vertical columns, each of them adds up to n + 1. The first column is 1 + n; the second is 2 + (n - 1); the third is 3 + (n - 2); and so on. There are n columns in all, so 2Tn = n(n + 1). The formula for Tn, therefore, is n(n + 1) ÷ 2.

(Sorry if using an obelus instead of fractional notation makes these equations a little hard to read. It allows me to type them inline instead of inserting an image file for each equation.)


2. For any modulus k, the series of triangular numbers reduced modulo k repeats, with a period no greater than 2k.

This part was discovered by Kevin McCall, though I've reformulated it somewhat.

It is postulated that, for any modulus kT2k ≡ 0 (mod k). This means that T2k is evenly divisible by k; in other words, that T2k ÷ k is an integer.

Plugging 2k into our triangular number formula, we get T2k = 2k(2k + 1) ÷ 2. Dividing by k gives us T2k ÷ = 2k(2k + 1) ÷ 2k = 2k + 1. Since k is itself an integer, 2k + 1 is an integer as well. Therefore, T2k ≡ 0 (mod k).

Now consider the next triangular number in the series, T2+ 1. For any given triangular number,  Tn , T+ 1 T + n + 1. (For example, for n = 10, the 10th triangular number is 55, and 55 + 10 + 1 = 66, which is the 11th triangular number.) Since 2k + 1 ≡ 1 (mod k), this amounts (in the modular arithmetic we are using) to adding 1, and T2+ 1 will be congruent to 1 (mod k).

Now the whole series of triangular numbers begins with 0. Then we add 1, then 2, then 3, and so on to infinity to generate the whole series.
  • T0 = 0
  • T1 = T0 + 1 = 1
  • T2 = T1 + 2 = 3
  • T3 = T2 + 3 = 6
  • T4 = T3 + 4 = 10
  • etc.
It should be clear that, when we reach T2k , the whole process begins again.

  • T2k ≡ 0 (mod k)
  • T2+ 1 = T2k + 2k + 1 ≡ 1 (mod k)
  • T2+ 2 = T2k + 1 + 2k + 2 ≡ 1 + 2 ≡ 3 (mod k)
  • T2+ 3 = T2k + 2 + 2k + 3 ≡ 3 + 3 ≡ 6 (mod k)
  • T2+ 4 = T2k + 3 + 2k + 4 ≡ 6 + 4 ≡ 10 (mod k)
  • etc.

We can see that any time Tn ≡ 0 and Tn + 1 ≡ 1 (mod k), the series will repeat. We know that this always happens where n = 2k. Therefore, the period of the repetition must be either 2k or else a number by which 2k is evenly divisible.


3. The period of repetition is always either k (if k is odd) or 2k (if k is even).

If k is and odd number, the series of triangular numbers reduced modulo k will begin to repeat at k rather than 2k because Tk ≡ 0 (mod k), meaning that Tk ÷ k is an integer. Tk ÷ = k(k + 1) ÷ 2k = (k + 1) ÷ 2. Since k is odd, k + 1 is even, so (k + 1) ÷ 2 is an integer. T+ 1 will then be equal to Tk + k + 1 ≡ 1 (mod k), and so on.

At this point my direct reliance on Kevin McCall's proof stops. Everything below is my own. (Kevin has proved it all, too, but I have not yet read his proof and will not do so until I have first proved it all myself.)

How do we know that the period is never smaller than k? Might it sometimes be k ÷ 2, for instance? No. While it sometimes happens that Tj ≡ 0 (mod k), where j < k, it is never also true that Tj + 1 ≡ 1 (mod k), which is what is necessary for the series to repeat. Recall that T+ 1 T + n + 1. Therefore, where Tj ≡ 0 (mod k) and j < k, it follows that T+ 1 j + 1 (mod k). The only way j + 1 can be congruent to 1 (mod k) is if j ≡ 0 (mod k), which we have specified that it is not. (With the exception of 0, no number less than k can be congruent to 0 modulo k.)

Therefore, the period of repetition is always precisely k (if k is odd) or 2k (if k is even).


4. The repeating series is always palindromic.

It is postulated that for any modulus k, the series for triangular numbers from T0 to T2k - 1 reduced modulo k (which series goes on to repeat itself forever, as proven above) is palindromic. This means that
  • T0 ≡ T2k - 1 (mod k)
  • T1 ≡ T2k - 2 (mod k)
  • T2 ≡ T2k - 3 (mod k)
  • etc.
Stating this generally, we can say that Tn ≡ T2k - (n +1) (mod k). Replacing Tn with the formula for triangular numbers, we arrive at the following equation: n(n + 1) ÷ 2 ≡ (2k - (n + 1))(2k - n) ÷ 2 (mod k).

Since multiplying both sides by the same number preserves congruence, we can simplify this to: n(n + 1) ≡ (2k - (n + 1))(2k - n) (mod k).

Doing the math, we find that this is equivalent to: n(n + 1) ≡ n(+ 1) + k(4k - 2(2n + 1)) (mod k).

Subtracting n(n + 1) from both sides, we get: k(4k - 2(2n + 1)) ≡ 0 (mod k). Trivially, any multiple of k is congruent to 0 modulo k, so this is true. Therefore, the series is palindromic.


5. Where k is even, the number at the center of the palindrome is k ÷ 2

The period of the repeating palindrome is 2k where k is even, so the number at the center of the palindrome is Tk = k(k + 1) ÷ 2. This number should be congruent to ÷ 2 (mod k).

Multiplying both sides by 2, we get k(k + 1) ≡ k (mod k). Trivially, nk ≡ k ≡ 0 (mod k), for any integer value of n, so this is true.


Now that everything has been proven that I set out to prove, I will look at Kevin McCall's full proof and, if it is different from my own (as I suspect it will be), post it as well.

No comments:

Annunciation rescheduled to coincide with eclipse

I just saw this on Ann Barnhardt's blog : March 25th is the fixed date of the great Feast of the Annunciation… BUT since March 25th fall...