Proving triangular number congruence patterns

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

1. The formula for triangular numbers is T_n = 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 n^th triangular number (written T_n) 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 T_n. 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 T_n, so the total of the two rows is 2T_n. 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 2T_n = n(n + 1). The formula for T_n, 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 k, T_2k ≡ 0 (mod k). This means that T_2k is evenly divisible by k; in other words, that T_2k ÷ k is an integer.

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

Now consider the next triangular number in the series, T_{2k + 1}. For any given triangular number,  T_n , T_{n + 1} = T_n  + 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 T_{2k + 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.

• T₀ = 0
• T₁ = T₀ + 1 = 1
• T₂ = T₁ + 2 = 3
• T₃ = T₂ + 3 = 6
• T₄ = T₃ + 4 = 10
• etc.

It should be clear that, when we reach T_2k , the whole process begins again.

• T_2k ≡ 0 (mod k)
• T_{2k + 1} = T_2k + 2k + 1 ≡ 1 (mod k)
• T_{2k + 2} = T_{2k + 1} + 2k + 2 ≡ 1 + 2 ≡ 3 (mod k)
• T_{2k + 3} = T_{2k + 2} + 2k + 3 ≡ 3 + 3 ≡ 6 (mod k)
• T_{2k + 4} = T_{2k + 3} + 2k + 4 ≡ 6 + 4 ≡ 10 (mod k)
• etc.

We can see that any time T_n ≡ 0 and T_{n + 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 T_k ≡ 0 (mod k), meaning that T_k ÷ k is an integer. T_k ÷ k = k(k + 1) ÷ 2k = (k + 1) ÷ 2. Since k is odd, k + 1 is even, so (k + 1) ÷ 2 is an integer. T_{k + 1} will then be equal to T_k + 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 T_j ≡ 0 (mod k), where j < k, it is never also true that T_{j + 1} ≡ 1 (mod k), which is what is necessary for the series to repeat. Recall that T_{n + 1} = T_n  + n + 1. Therefore, where T_j ≡ 0 (mod k) and j < k, it follows that T_{j + 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 T₀ to T_{2k - 1} reduced modulo k (which series goes on to repeat itself forever, as proven above) is palindromic. This means that

• T₀ ≡ T_{2k - 1} (mod k)
• T₁ ≡ T_{2k - 2} (mod k)
• T₂ ≡ T_{2k - 3} (mod k)
• etc.

Stating this generally, we can say that T_n ≡ T_{2k - (n +1)} (mod k). Replacing T_n 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(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 T_k = k(k + 1) ÷ 2. This number should be congruent to k ÷ 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.