Triangular numbers
Stack dots in rows of one, two, three and onward. Which numbers turn up as the totals, and what do they do when you combine them?
Where you are 8 in Introductory number theory
Why this exists
The total 1 + 2 + \cdots + n has already turned up several times. Arithmetic series and partial sums found it by fitting two triangles of dots into a rectangle, How induction works: base case, hypothesis and step proved the same formula by induction, Conjecture, and why a pattern is not a proof found that two neighbors add to a square, and Pascal's triangle found the totals running down a diagonal of Pascal’s triangle. Each time the totals were a tool for something else.
This lesson treats them as objects in their own right. Is a given number one of them, and which one? What happens when two are combined? Which are odd? What do their reciprocals add to? Each answer is a short proof, and some run on nothing but the rule that builds each total from the one before, which is exactly the shape induction needs.
Definition
The nth triangular number T_n is the number of dots in a triangle whose rows hold 1, 2, 3, \ldots, n dots. Adding a row of n dots to the triangle for n - 1 gives the triangle for n, and the empty triangle has no dots, so as a recursive rule
A whole number m is triangular if m = T_n for some whole number n, and then n is its index. From T_0 to T_{10} the values are 0, 1, 3, 6, 10, 15 and then 21, 28, 36, 45, 55.
Taken from the lessons named above, and used here without being proved again:
The closed form gives any T_n at once; the rule gives each from the last. Example 7 proves a result from the rule alone.
Intuition
Lined up on the left, the triangle for m + n is a staircase. Its top m rows are the triangle for m. Each of the bottom n rows starts with m dots, and those make an n by m rectangle. What is left over at the bottom right has rows of 1, 2, \ldots, n: the triangle for n.
The rectangle of Arithmetic series and partial sums holds two copies of T_n, so it has n(n+1) = 2T_n dots. Four of those rectangles, wound around one center dot like a pinwheel, fill a square of side 2n + 1, so eight triangles and one dot make an odd square.
Finally, read the parities of T_1, T_2, T_3, \ldots in the list above: odd, odd, even, even, and again.
Results
Square test. For every whole number n,
So a whole number m is triangular exactly when 8m + 1 is a perfect square, and then its index is
Addition. For all whole numbers m and n,
Doubling. Taking m = n, and then adding one more row,
Parity. T_n is odd when n leaves remainder 1 or 2 on division by 4, and even when it leaves remainder 0 or 3. Starting from T_1 the pattern is odd, odd, even, even, and it repeats with period 4.
Reciprocals. For every n \ge 1,
Square triangular numbers. Some triangular numbers are also perfect squares: T_1 = 1 = 1^2, T_8 = 36 = 6^2 and T_{49} = 1225 = 35^2, and the next is T_{288} = 41{,}616 = 204^2. There are infinitely many; that is stated here without proof.
Why it is true
Proof of the square test. By the closed form, 8T_n + 1 = 4n(n+1) + 1, which is 4n^2 + 4n + 1 = (2n+1)^2. Conversely, suppose m is a whole number and 8m + 1 = s^2 with s \ge 0. Then s^2 is odd, so s is odd (the square of an even number is even, Proving statements about even and odd numbers), and since s \ge 1 we can write s = 2n + 1 for a whole number n. Then 8m + 1 = 4n^2 + 4n + 1, so \displaystyle m = \frac{n(n+1)}{2} = T_n, and \displaystyle n = \frac{s - 1}{2} is the index. \square
Proof of the addition formula. Expand the closed form:
Proof of the doubling formulas. With m = n, T_{2n} = 2T_n + n^2 = n(n+1) + n^2 = n(2n+1). Adding the row of 2n + 1 dots, T_{2n+1} = n(2n+1) + (2n+1) = (n+1)(2n+1). \square
Proof of the parity pattern. Split by the parity of n, as in Proof by cases.
If n = 2j for some whole number j, then T_n = j(2j + 1). The factor 2j + 1 is odd, so T_n has the parity of j: even when j is even (n = 4k), odd when j is odd (n = 4k + 2).
If n = 2j + 1, then T_n = (j + 1)(2j + 1), which has the parity of j + 1: odd when j is even (n = 4k + 1), even when j is odd (n = 4k + 3).
Every whole number is one of 4k, 4k + 1, 4k + 2, 4k + 3 (The division algorithm), so the four cases cover every n. \square
Proof of the reciprocal sum. By the closed form,
which is checked by putting the bracket over the common denominator k(k+1). In the sum each \displaystyle -\frac{1}{k+1} cancels the \displaystyle +\frac{1}{k+1} of the next term, so only the first and the last survive:
Such a collapsing sum is called telescoping; this one is twice the sum How induction works: base case, hypothesis and step proves by induction.
Worked examples
Is it triangular?
Decide whether 2016 and 2026 are triangular, and give the index of any that is.
SolutionFor 2016: 8 \cdot 2016 + 1 = 16{,}129 = 127^2, a perfect square, so 2016 is triangular by the square test, with index \displaystyle \frac{127 - 1}{2} = 63.
Check. \displaystyle T_{63} = \frac{63 \cdot 64}{2} = 63 \cdot 32 = 2016.
For 2026: 8 \cdot 2026 + 1 = 16{,}209 lies strictly between the consecutive squares 127^2 = 16{,}129 and 128^2 = 16{,}384, so it is not a square and 2026 is not triangular. It sits between T_{63} = 2016 and T_{64} = 2080.
Every triangular number in a range
Find every triangular number from 1000 to 1100.
SolutionA whole number m is T_n exactly when 8m + 1 = (2n + 1)^2. The condition 1000 \le m \le 1100 becomes 8001 \le (2n + 1)^2 \le 8801. Now 89^2 = 7921, 90^2 = 8100, 93^2 = 8649 and 94^2 = 8836, so the odd numbers whose squares land in the range are 91 and 93. They give n = 45 and n = 46:
Check. One step of the rule on each side: T_{44} = 1035 - 45 = 990 is below the range and T_{47} = 1081 + 47 = 1128 is above it.
Building one triangular number from others
Given T_{60} = 1830, T_{12} = 78 and T_{40} = 820, find T_{72}, T_{80} and T_{81} without multiplying out a closed form.
SolutionThe addition formula with m = 60 and n = 12:
The doubling case, T_{2n} = 2T_n + n^2 with n = 40:
Then one more row of 81 dots: T_{81} = 3240 + 81 = 3321, which agrees with T_{2n+1} = (n+1)(2n+1) = 41 \cdot 81.
Check. \displaystyle \frac{72 \cdot 73}{2} = 36 \cdot 73 = 2628 and \displaystyle \frac{80 \cdot 81}{2} = 40 \cdot 81 = 3240.
Counting odd triangular numbers
How many of T_1, T_2, \ldots, T_{1000} are odd? Is their sum even or odd?
SolutionBy the parity pattern, T_n is odd exactly when n leaves remainder 1 or 2 on division by 4. The numbers 1, \ldots, 1000 form 250 complete blocks 4k+1, 4k+2, 4k+3, 4k+4, and each block holds exactly two indices of odd triangular numbers. So 2 \cdot 250 = 500 of them are odd.
A sum of whole numbers is odd exactly when it has an odd number of odd terms, so this sum, with 500 odd terms, is even.
Check. How induction works: base case, hypothesis and step gives the sum as \displaystyle \frac{n(n+1)(n+2)}{6}, which for n = 1000 is \displaystyle \frac{1000 \cdot 1001 \cdot 1002}{6} = 167{,}167{,}000, an even number.
Sums of reciprocals
Find (a) \displaystyle \sum_{k=1}^{99} \frac{1}{T_k}, (b) \displaystyle \sum_{k=10}^{20} \frac{1}{T_k}, and (c) the smallest n for which \displaystyle \sum_{k=1}^{n} \frac{1}{T_k} is greater than 1.99.
Solution(a) The reciprocal formula with n = 99 gives \displaystyle \frac{2 \cdot 99}{100} = \frac{99}{50}.
(b) The sum does not start at k = 1, so use the telescoping form directly. Writing each term as \displaystyle 2\left(\frac{1}{k} - \frac{1}{k+1}\right), the terms from k = 10 to k = 20 cancel down to the first and the last:
(c) We need \displaystyle \frac{2n}{n+1} > 1.99. Since n + 1 > 0, multiplying through keeps the direction: 2n > 1.99n + 1.99, so 0.01n > 1.99 and n > 199. The smallest such n is 200. At n = 199 the sum is \displaystyle \frac{398}{200} = 1.99 exactly, which is not greater.
The sums climb toward 2, never reaching it: \displaystyle \frac{2n}{n+1} = 2 - \frac{2}{n+1}.
Triangular numbers that are squares
Show that 36 and 1225 are both triangular and square, and turn “T_n is a square” into an equation in two unknowns.
Solution36 = 6^2, and 8 \cdot 36 + 1 = 289 = 17^2, so 36 = T_8. Next, 1225 = 35^2, and 8 \cdot 1225 + 1 = 9801 = 99^2, so 1225 = T_{49}.
By the square test, T_n = s^2 means 8s^2 + 1 = (2n + 1)^2. With x = 2n + 1 this is
The pairs so far fit: 3^2 - 8 \cdot 1^2 = 1, 17^2 - 8 \cdot 6^2 = 1 and 99^2 - 8 \cdot 35^2 = 9801 - 9800 = 1. So does x = 577, s = 204: 577^2 = 332{,}929 and 8 \cdot 204^2 = 332{,}928. That gives \displaystyle n = \frac{577 - 1}{2} = 288 and T_{288} = 41{,}616 = 204^2. That this equation (a Pell equation) has infinitely many solutions is beyond this lesson.
A proof from the rule alone
Using only T_0 = 0 and T_n = T_{n-1} + n, and no closed form, prove that T_{m+n} = T_m + T_n + mn for all whole numbers m and n.
SolutionProof. Fix a whole number m. We prove the statement for every whole number n by induction on n (How induction works: base case, hypothesis and step).
Base case, n = 0: the left side is T_m and the right side is T_m + T_0 + 0 = T_m.
Inductive step: suppose T_{m+n} = T_m + T_n + mn for some whole number n. The rule, applied at m + n + 1, then the hypothesis, give
where the third line regroups and reorders (the associative and commutative properties) and factors mn + m, and the last uses the rule at n + 1. That is the statement for n + 1, so by induction it holds for every n, and m was arbitrary. \square
This is the staircase picture read row by row: each new bottom row adds n + 1 dots to the small triangle and m dots to the rectangle.
Boundaries
T_n is defined for whole numbers n. The closed form can be evaluated at a negative n and gives T_{-n} = T_{n-1} (Exercise 21), but “triangular” always means a whole-number index.
The square test needs 8m + 1 to be the square of a whole number; any other square root means “not triangular”, never a fractional index.
The addition formula holds for all integers as an identity of polynomials, but the staircase picture shows it only for whole numbers. The reciprocal sum starts at k = 1, since T_0 = 0 has no reciprocal.
The list 1, 36, 1225, 41{,}616 of square triangular numbers is checked, not proved complete, and that it never ends is stated without proof.
Where this goes next
The rule T_n = T_{n-1} + n is the first of many definitions that build each value from the one before, and proofs about them are inductions: Induction on a sum formula, How induction works: base case, hypothesis and step and Strong induction and well-ordering come next. The parity pattern is a remainder repeating with a period, which Modular arithmetic makes into an arithmetic of its own. pascals-triangle-recurrence explains the diagonal that holds T_n, and telescoping sums return in Infinite series and partial sums.
Exercises
The rule and the square test
- Starting from T_{10} = 55, use the rule to find T_{11}, T_{12}, T_{13} and T_{14}.
- Decide whether each number is triangular, and give the index of any that is: (a) 351, (b) 500, (c) 4950, (d) 1000.
- Find the largest triangular number below 10{,}000 and its index.
- How many triangular numbers lie between 5000 and 6000?
- Jedda stacks cans in a triangle, one can in the top row and one more in each row below it. The stack uses 300 cans. How many cans are in the bottom row?
Combining triangular numbers
- Use T_{30} = 465, T_{20} = 210 and the addition formula to find T_{50}.
- Use T_{35} = 630 and the doubling formulas to find T_{70} and T_{71}.
- Prove that 9T_n + 1 = T_{3n+1} for every whole number n. Starting from 10 = T_4, apply it twice to find two larger triangular numbers.
- Prove that T_{mn} = T_m T_n + T_{m-1} T_{n-1} for all positive integers m and n, and check it with m = 3, n = 4.
- Prove that T_{2n} = 3T_n + T_{n-1} for n \ge 1 and T_{2n+1} = 3T_n + T_{n+1} for n \ge 0.
Parity and remainders
- Without computing them, decide whether each of T_{999}, T_{1000}, T_{1001} and T_{1002} is even or odd.
- How many of T_1, T_2, \ldots, T_{250} are odd?
- Show that T_{n+4} - T_n = 4n + 10, and use it to give a second proof that the parity of T_n repeats with period 4.
- Prove that no triangular number leaves remainder 2 on division by 3.
- Prove that the last digit of a triangular number is never 2, 4, 7 or 9.
Reciprocal sums
- Find \displaystyle \sum_{k=1}^{24} \frac{1}{T_k}.
- Find \displaystyle \sum_{k=5}^{14} \frac{1}{T_k}.
- For which n is \displaystyle \sum_{k=1}^{n} \frac{1}{T_k} = \frac{19}{10}? Can the sum ever equal 2?
Reasoning
- Prove that for n \ge 1, n \mid T_n exactly when n is odd.
- Prove that the only triangular number that is a power of 2 is T_1 = 1.
- Run the rule backward, as T_{n-1} = T_n - n, starting from T_0 = 0, to find “T_{-1}”, “T_{-2}” and “T_{-3}”. Show that the closed form gives the same values, and that it gives T_{-n} = T_{n-1} for every n.
Answers
- 66, 78, 91, 105. Add 11, then 12, 13 and 14: 55 + 11 = 66, 66 + 12 = 78, 78 + 13 = 91, 91 + 14 = 105.
- (a) Yes, index 26: 8 \cdot 351 + 1 = 2809 = 53^2 and \displaystyle \frac{53 - 1}{2} = 26. (b) No: 4001 lies between 63^2 = 3969 and 64^2 = 4096. (c) Yes, index 99: 8 \cdot 4950 + 1 = 39{,}601 = 199^2. (d) No: 8001 lies between 89^2 = 7921 and 90^2 = 8100.
- T_{140} = 9870. We need n(n+1) < 20{,}000: 140 \cdot 141 = 19{,}740 works and 141 \cdot 142 = 20{,}022 does not, so T_{140} = 9870 and T_{141} = 10{,}011.
- 10. T_{99} = 4950 and T_{100} = 5050, while T_{109} = 5995 and T_{110} = 6105, so the indices 100 to 109 give the triangular numbers in the range.
- 24 cans. A stack with n rows uses T_n cans and its bottom row has n; 8 \cdot 300 + 1 = 2401 = 49^2, so \displaystyle n = \frac{49 - 1}{2} = 24.
- T_{50} = 1275: 465 + 210 + 30 \cdot 20 = 465 + 210 + 600 = 1275, and \displaystyle \frac{50 \cdot 51}{2} = 1275 agrees.
- T_{70} = 2485 and T_{71} = 2556: T_{70} = 2 \cdot 630 + 35^2 = 1260 + 1225 = 2485, and T_{71} = 36 \cdot 71 = 2556, which is also 2485 + 71.
- 91 = T_{13} and 820 = T_{40}, from 9 \cdot 10 + 1 and then 9 \cdot 91 + 1. The identity, by the closed form:
- Check: T_{12} = 78 and T_3 T_4 + T_2 T_3 = 60 + 18 = 78. Proof: the products are \displaystyle \frac{mn(m+1)(n+1)}{4} and \displaystyle \frac{mn(m-1)(n-1)}{4}, and (m+1)(n+1) + (m-1)(n-1) = 2mn + 2, so
- T_{n-1} + T_n = n^2 (the identity of Conjecture, and why a pattern is not a proof, shifted down by one), so T_{2n} = 2T_n + n^2 = 3T_n + T_{n-1}. The addition formula with n and n + 1 gives T_{2n+1} = T_n + T_{n+1} + n(n+1), and n(n+1) = 2T_n, so T_{2n+1} = 3T_n + T_{n+1}.
- T_{999} even, T_{1000} even, T_{1001} odd, T_{1002} odd. The remainders on division by 4 are 3, 0, 1, 2. For instance T_{999} = 999 \cdot 500 and T_{1001} = 1001 \cdot 501.
- 126. Odd exactly for n = 4k + 1 or 4k + 2: the indices 1, 5, \ldots, 249 give 63 and 2, 6, \ldots, 250 give 63.
- By the rule four times, T_{n+4} - T_n is (n + 1) + (n + 2) + (n + 3) + (n + 4), which is 4n + 10 = 2(2n + 5), an even number, so T_{n+4} and T_n have the same parity. Since T_0, T_1, T_2, T_3 are even, odd, odd, even, writing n = 4q + r with 0 \le r \le 3 and inducting on q (How induction works: base case, hypothesis and step) gives every T_n the parity of T_r.
- Suppose T_n = 3q + 2. Then 8T_n + 1 = 24q + 17 = 3(8q + 5) + 2, which leaves remainder 2 on division by 3. But 8T_n + 1 = (2n+1)^2 is a square, and a square leaves remainder 0 or 1 on division by 3 (Proof by cases, “Squares on division by 3”). Contradiction.
- By the closed form, T_{n+20} - T_n = 20n + 210, which is 10(2n + 21), so T_{n+20} and T_n have the same last digit, and every last digit already appears among T_0, \ldots, T_{19}. Those end in 0, 1, 3, 6, 0, 5, 1, 8, 6, 5 and then 5, 6, 8, 1, 5, 0, 6, 3, 1, 0. The digits 2, 4, 7, 9 never appear.
- \displaystyle \frac{48}{25}, the formula \displaystyle \frac{2n}{n+1} with n = 24.
- \displaystyle \frac{4}{15}. Telescoping from k = 5 to k = 14 leaves \displaystyle 2\left(\frac{1}{5} - \frac{1}{15}\right) = 2 \cdot \frac{2}{15}.
- n = 19. \displaystyle \frac{2n}{n+1} = \frac{19}{10} gives 20n = 19n + 19. The sum is never 2: \displaystyle \frac{2n}{n+1} = 2 would need 2n = 2n + 2.
- \displaystyle T_n = n \cdot \frac{n+1}{2}. If n is odd, \displaystyle \frac{n+1}{2} is an integer, so n \mid T_n. If n = 2j with j \ge 1, then T_n = j(2j + 1), and 2j \mid j(2j + 1) would give 2 \mid 2j + 1 after dividing by j, which is false since 2j + 1 is odd.
- Suppose T_n = 2^k with n \ge 1 and k \ge 0. Then n(n+1) = 2^{k+1}, so n and n + 1 both divide a power of 2, and by the fundamental-theorem-of-arithmetic each is itself a power of 2. One of two consecutive integers is odd, and the only odd power of 2 is 1. Since n + 1 \ge 2, that forces n = 1, and T_1 = 1 = 2^0.
- T_{-1} = T_0 - 0 = 0, T_{-2} = T_{-1} - (-1) = 1, T_{-3} = T_{-2} - (-2) = 3. The closed form agrees: \displaystyle \frac{(-1)(0)}{2} = 0, \displaystyle \frac{(-2)(-1)}{2} = 1, \displaystyle \frac{(-3)(-2)}{2} = 3. In general \displaystyle \frac{(-n)(-n+1)}{2} = \frac{n(n-1)}{2} = T_{n-1}.