6
$\begingroup$

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.
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – WarrenTheRabbit Jul 6 at 17:20
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – WarrenTheRabbit Jul 7 at 1:32
  • $\begingroup$ @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$. $\endgroup$ – Izaak van Dongen Jul 7 at 10:02
1
$\begingroup$

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...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – Devansh Kamra Jul 6 at 14:43
  • 1
    $\begingroup$ @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 $\endgroup$ – Martin Hansen Jul 6 at 14:46
  • 1
    $\begingroup$ But it's easy enough to edit the answer to flow with that used in the question so I've done so... $\endgroup$ – Martin Hansen Jul 6 at 14:54
  • 1
    $\begingroup$ 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. $\endgroup$ – WarrenTheRabbit Jul 7 at 0:55
  • 1
    $\begingroup$ 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. $\endgroup$ – WarrenTheRabbit Jul 7 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.