# Proving that 2 out of every 3 triangular numbers are divisible by 3

I am trying to prove the observation that the sequence of triangular numbers are divisible in the repeating pattern of not-divisible, divisible and divisible. I've never done proofs before and I'm also a long-time away from doing any maths. High-school dropout level of maths kind of thing. So I'm not confident about my thinking processes and I would like some help and feedback.

Observed pattern: not divisible, divisible, divisible, not divisible, divisible, divisible, etc
1           = 1   no
1+2         = 3   yes
1+2+3       = 6   yes
1+2+3+4     = 10  no
1+2+3+4+5   = 15  yes
1+2+3+4+5+6 = 21  yes


I reason that a number is divisible by three if it can be written as $$3n$$, where $$n$$ is an integer.

Since the triangular numbers, $$T_1$$, $$T_2$$ and $$T_3$$, or

1        = 1
1 2      = 3
1 2 3    = 6 

respectively,

can be represented as:

$$T_1 = 3i + 1$$

$$T_2 = T_1 + 3i + 2$$
$$T_2 = 3i + 1 + 3i + 2 = 6i + 3 = 3(2i+1)$$

$$T_3 = T_1 + T_2 + 3i + 3$$
$$T_3 = 3i + 1 + 3i + 2 + 3i + 3 = 9i + 6 = 3(3i+2)$$

where $$i=0$$,

I conclude that $$T_1$$ is not divisible by 3 but that $$T_2$$ and $$T_3$$ are because they can be expressed in the form $$3n$$.

If it is correct to conclude this for $$T_1$$, $$T_2$$ and $$T_3$$, where $$i=0$$, it would be correct to conclude the same for $$T_4$$, $$T_5$$ and $$T_6$$, where $$i=1$$, and for $$T_7$$, $$T_8$$ and $$T_9$$, where $$i=2$$ and so on and so on for all integer values of $$i$$.

Thus, triangular numbers do repeat the

not divisible
divisible
divisible
pattern forever because they repeat the

$$3i + 1$$
$$3(2i + 1)$$
$$3(3i + 3)$$

pattern forever for all integers $$i$$.

Is my reasoning valid? Thanks for your time.

Your proof is specific to $$1,2,3$$. What you should do is use the fact that $$T_k=\frac 12k(k+1)$$. Now you can work $$\bmod 3$$ and just point out that if $$k \equiv 1 \pmod 3, T_k \equiv 1 \pmod 3$$ as well because $$k+1 \equiv 2 \pmod 3$$. If $$k \equiv 2$$ or $$3 \pmod 3$$, one of the factors is a multiple of $$3$$ so $$T_k$$ is.

You have a really good insight there. If you learn about residue classes modulo $$3$$ some day, you might recognize your approach as a result of repeatedly adding the residue classes $$1,$$ $$2,$$ and $$3$$ (aka the residue class of $$0$$) to the sum.

The only thing you are missing in the sums is a suitable representation for the sum of all the terms before $$3i+1.$$. When $$i=0$$ this is not a problem since there are no previous terms and the sum of no terms is $$0.$$ But for any larger $$i$$ you should notice that after you add $$3i+1$$ you have a sum which is larger than just $$3i+1.$$

But you have shown that the sum of all the previous terms ($$1$$ to $$3i$$) is divisible by $$3$$, so it is $$3k$$ for some integer $$k$$. If you just account for that, and make the induction part of your argument a little more explicit, I think you could have a very nice proof.

The key point is you recognized a useful pattern.

• It will take me some time to work through and understand all the amazing answers. You summarise a gap in the vocabulary of the argument very well when you describe the lack of 'a suitable representation for the sum of all the terms before 3i+1'. I try to articulate an argument based on the n terms of the nth-triangular number but don't manage to tie it together. In fact, I confuse the issue by not carefully defining the difference between an nth triangular number and an nth term. @Izaak, I think, points to this issue with his comment about the confusion of how I have phrased things. – WarrenTheRabbit Jul 6 at 17:20

You are quite correct. You can simply summarize it as:

The $$n_{th}$$ triangular number is defined as $$T_n=\dfrac{n(n+1)}{2}$$

Now for any number $$n$$, there can be only three cases, that is, $$n\equiv 0\space\text {(mod 3)},\space n\equiv 1\space\text {(mod 3) and } n\equiv 2\space\text{(mod 3)}$$

Now in only one of these cases, that is, $$n\equiv 1\space\text {(mod 3)}$$, we have $$T_n\not\equiv 0\space\text{(mod 3)}$$

$$\therefore$$ Every $$2$$ of $$3$$ consecutive triangular numbers will be divisible by $$3$$.

Your proof is not quite correct, or perhaps not complete. Particularly, you need a lot more justification in this step:

If it is correct to conclude this for $$T_1$$, $$T_2$$ and $$T_3$$, where $$i=0$$, it would be correct to conclude the same for $$T_4$$, $$T_5$$ and $$T_6$$, where $$i=1$$, and for $$T_7$$, $$T_8$$ and $$T_9$$, where $$i=2$$ and so on and so on for all integer values of $$i$$.

For example, in the case $$i = 2$$, $$3 \cdot 2 + 1$$ is not a triangular number. This is perhaps in part due to some confusion with how you've phrased things. I suspect you meant to use a mixture of "for all" and "there exists".

Here's how you could give a more complete proof from the inductive definition of $$T_i$$, not using the formula.

Claim: for all $$i \ge 0$$, $$T_{3i + 1} = 3k + 1$$ for some $$k$$, $$T_{3i + 2} = 3n$$ for some $$n$$, and $$T_{3i + 3} = 3m$$ for some $$m$$.

Proof: By induction on $$i$$. In the case $$i = 0$$, this is true, by taking $$k = 0$$, $$n = 1$$, $$m = 2$$.

Now suppose that the claim holds for $$i$$, consider the claim for $$i + 1$$.

We have that $$T_{3(i + 1) + 1} = T_{3i + 3} + 3i + 4 = 3m' + 3i + 4 = 3(m' + i + 1) + 1$$ for some $$m'$$. So take $$k = m' + i + 1$$ to fulfil the first part of the claim.

Continuing on, $$T_{3(i + 1) + 2} = T_{3i + 4} + 3i + 5 = 3k + 1 + 3i + 5 = 3(k + i + 2)$$. So take $$n = k + i + 2$$ to fulfil the second part of the claim.

Lastly, $$T_{3(i + 1) + 3} = T_{3i + 5} + 3i + 6 = 3n + 3i + 6 = 3(n + i + 2)$$. So take $$m = n + i + 2$$ to fulfil the last part of the claim.

This proves exactly what you wanted to show.

• Thank you very much, Izaak. It will take me a bit to understand your response but I really like how well-structured your argument is. I will try to emulate that clarity in the future. The main roadblock to understanding is that I'm unclear about some of the operations you are doing in your algebraic sequences. I don't understand how you get $T_{3(i + 1) + 1} = T_{3i + 3} + 3i + 4$, for example. – WarrenTheRabbit Jul 7 at 1:32
• @WarrenTheRabbit, You're welcome! I sort of skipped a step there. I could have written $T_{3(i + 1) + 1} = T_{3i + 3 + 1} = T_{3i + 3} + 3i + 3 + 1$, which uses the definition of a triangular number: for any $n$, we have $T_{n + 1} = T_n + n + 1$. – Izaak van Dongen Jul 7 at 10:02

You could try and pin down your observation by observing that a formula for triangular numbers is, $$T_n=\frac{1}{2}(n)(n+1)$$ such that $$T_1=1, T_2=3, T_3=6, T_4=10, ...$$

Proving the formula for triangular numbers is not difficult. Ask if you want it.

All numbers give a remainder of either 0, 1 or 2 when divided by 3. That is, they are of one of the forms $$3m$$ or $$3m+1$$ or $$3m+2$$ for integer $$m$$.

$$T_{3m}=\frac{1}{2}(3m)(3m+1)$$ which is divisible by 3

$$T_{3m+1}=\frac{1}{2}(3m+1)(3m+2)$$ which is NOT divisible by 3

$$T_{3m+2}=\frac{1}{2}(3m+2)(3m+3)$$ which is divisible by 3

Comments or requests for clarification welcome...

• As the $n_th$ can also be defined as the sum of first $n$ natural numbers, it would be better if you use $T_n=\dfrac{n(n+1)}{2}$. – Devansh Kamra Jul 6 at 14:43
• @Devansh Kamra Quickly grabbed from wikipedia "Some definitions, including the standard ISO 80000-2,[1][2] begin the natural numbers with 0, corresponding to the non-negative integers 0, 1, 2, 3, …" Link : en.wikipedia.org/wiki/Natural_number – Martin Hansen Jul 6 at 14:46
• But it's easy enough to edit the answer to flow with that used in the question so I've done so... – Martin Hansen Jul 6 at 14:54
• The formula you give for triangular numbers makes a lot of sense to me. I'm not sure about proving it but I think I can see that I can set out each term in a triangular number as a column of Xs, put them all adjacent to each other and imagine the result is a half-filled rectangle with width n and height n+1. – WarrenTheRabbit Jul 7 at 0:55
• I like how simply you list all possible representations of a natural number's divisibility by 3 and then show how only one of those possible representations produces an expression without a factor of three when plugged into the triangular number formula. I think a lot of the other answers use the same logic but they introduce symbols/concepts/operations I'm not familiar with so it is a bit harder going. – WarrenTheRabbit Jul 7 at 0:55