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 2
Tn. 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 2
Tn =
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
k,
T2k ≡ 0 (mod
k). This means that
T2k is evenly divisible by
k; in other words, that
T2k ÷
k is an integer.
Plugging 2
k into our triangular number formula, we get
T2k = 2
k(2
k + 1) ÷ 2. Dividing by
k gives us
T2k ÷
k = 2
k(2
k + 1) ÷ 2
k = 2
k + 1. Since
k is itself an integer, 2
k + 1 is an integer as well. Therefore,
T2k ≡ 0 (mod
k).
Now consider the next triangular number in the series,
T2k + 1. For any given triangular number,
Tn ,
Tn + 1 =
Tn + 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 2
k + 1 ≡ 1 (mod
k), this amounts (in the modular arithmetic we are using) to adding 1, and
T2k + 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)
- T2k + 1 = T2k + 2k + 1 ≡ 1 (mod k)
- T2k + 2 = T2k + 1 + 2k + 2 ≡ 1 + 2 ≡ 3 (mod k)
- T2k + 3 = T2k + 2 + 2k + 3 ≡ 3 + 3 ≡ 6 (mod k)
- T2k + 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 = 2
k. Therefore, the period of the repetition must be either 2
k or else a number by which 2
k 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 2
k because
Tk ≡ 0 (mod
k), meaning that
Tk ÷
k is an integer.
Tk ÷
k =
k(
k + 1) ÷ 2
k = (
k + 1) ÷ 2. Since
k is odd,
k + 1 is even, so (
k + 1) ÷ 2 is an integer.
Tk + 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
Tn + 1 =
Tn + n + 1. Therefore, where
Tj ≡ 0 (mod
k) and
j <
k, it follows that
Tj + 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 2
k (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 ≡ (2
k - (
n + 1))(2
k -
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 Tk = 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.