Editing Triangular number (section)

==Formula==
{{Pascal triangle simplex numbers.svg|2=triangular numbers}}
The triangular numbers are given by the following explicit formulas:
<!-- THE END OF THE NEXT LINE HAS BINOMIAL NOTATION. PLEASE DO NOT CHANGE IF YOU ARE UNFAMILIAR. -->
{{bi|left=1.6|1=<math>\displaystyle
\begin{align} T_n &= \sum_{k=1}^n k = 1+2+ \dotsb +n \\
&= \frac{n^2+n \vphantom{(n+1)}}{2} = \frac{n(n+1)}{2} \\
&= {n+1 \choose 2}
\end{align}</math>}}
where <math>\textstyle {n+1 \choose 2}</math> is notation for a [[binomial coefficient]]. It represents the number of distinct pairs that can be selected from {{math|''n'' + 1}} objects, and it is read aloud as "{{mvar|n}} plus one choose two".

The fact that the <math>n</math>th triangular number equals <math>n(n+1)/2</math> can be illustrated using a [[Proof without words|visual proof]].<ref>{{cite web|url=https://www.mathsisfun.com/algebra/triangular-numbers.html|title=Triangular Number Sequence|website=Math Is Fun}}</ref> For every triangular number <math>T_n</math>, imagine a "half-rectangle" arrangement of objects corresponding to the triangular number, as in the figure below.  Copying this arrangement and rotating it to create a rectangular figure doubles the number of objects, producing a rectangle with dimensions <math>n \times (n+1)</math>, which is also the number of objects in the rectangle.  Clearly, the triangular number itself is always exactly half of the number of objects in such a figure, or: <math>T_n = \frac{n(n+1)}{2} </math>.  The example <math>T_4</math> follows:

{{bi|left=1.6
|<math> 2T_4 = 4(4+1) = 20 </math> (green plus yellow) implies that <math>T_4 = \frac{4(4+1)}{2} = 10 </math> (green).&nbsp;&nbsp;&nbsp; [[File:Illustration of Triangular Number T 4 Leading to a Rectangle (yellow-green).svg]]
}}

This formula can be proven formally using [[mathematical induction]].<ref>{{cite book |last=Spivak |first=Michael |author-link=Michael Spivak |date=2008 |title=Calculus |edition=4th |url=https://books.google.com/books?id=7JKVu_9InRUC&pg=PA21 |location=Houston, Texas |publisher=Publish or Perish |pages=21–22 |isbn=978-0-914098-91-1}}</ref> It is clearly true for <math>1</math>:

<math display=block>T_1 = \sum_{k=1}^{1}k = \frac{1(1 + 1)}{2} = \frac{2}{2} = 1.</math>

Now assume that, for some natural number <math>m</math>, <math>T_m = \sum_{k=1}^{m}k = \frac{m(m + 1)}{2}</math>.  We can then verify it for <math>m+1</math>:
<math display=block>
\begin{align}
  \sum_{k=1}^{m+1}k &= \sum_{k=1}^{m}k + (m + 1) \\
                    &= \frac{m(m + 1)}{2} + m + 1\\
                    &= \frac{m^2 + m}{2} + \frac{2m + 2}{2}\\
                    &= \frac{m^2 + 3m + 2}{2}\\
                    &= \frac{(m + 1)(m + 2)}{2},
\end{align}
</math>

so if the formula is true for <math>m</math>, it is true for <math>m+1</math>. Since it is clearly true for <math>1</math>, it is therefore true for <math>2</math>, <math>3</math>, and ultimately all natural numbers <math>n</math> by induction.

The German mathematician and scientist, [[Carl Friedrich Gauss]], is said to have found this relationship in his early youth, by multiplying {{math|{{sfrac|''n''|2}}}} pairs of numbers in the sum by the values of each pair {{math|''n'' + 1}}.<ref name=Gauss>{{cite web |last=Hayes |first=Brian |title=Gauss's Day of Reckoning |url=http://www.americanscientist.org/issues/pub/gausss-day-of-reckoning/1 |website=American Scientist |publisher=Computing Science |access-date=2014-04-16 |archive-date=2015-04-02 |archive-url=https://web.archive.org/web/20150402141244/http://www.americanscientist.org/issues/pub/gausss-day-of-reckoning/1 }}</ref> However, regardless of the truth of this story, Gauss was not the first to discover this formula, and some find it likely that its origin goes back to the [[Pythagoreans]] in the 5th century BC.<ref>{{cite web|last=Eves|first=Howard|title=Webpage cites AN INTRODUCTION TO THE HISTORY OF MATHEMATICS|url=http://mathcentral.uregina.ca/QQ/database/QQ.09.98/matt1.html|publisher=Mathcentral|access-date=28 March 2015}}</ref> The two formulas were described by the Irish monk [[Dicuil]] in about 816 in his [[Computus]].<ref>{{cite journal |last=Esposito |first=Mario |author-link=Mario Esposito (scholar) |title=An unpublished astronomical treatise by the Irish monk Dicuil |journal=[[Proceedings of the Royal Irish Academy, Section C]] |volume=26 |location=Dublin |date=August 1907 |pages=378–446+i (PDF pages 704–773) |lang=en,la |url=https://archive.org/details/proceedingsofroy2619roya}}</ref> An English translation of Dicuil's account is available.<ref>{{cite journal |last1=Ross |first1=H.E. |last2=Knott |first2=B.I. |title=Dicuil (9th century) on triangular and square numbers |journal=British Journal for the History of Mathematics |year=2019 |volume=34 |issue=2 |pages=79–94 |doi=10.1080/26375451.2019.1598687 |url=https://dspace.stir.ac.uk/handle/1893/29437|hdl=1893/29437 |hdl-access=free }}</ref>

Occasionally it is necessary to compute large triangular numbers where the standard formula <code>t = n*(n+1)/2</code> would suffer [[integer overflow]] before the final division by 2.  For example, {{math|''T''<sub>20</sub>}} = 210 < 256, so will fit into an [[8-bit byte]], but not the intermediate product 420.  This can be solved by dividing either {{mvar|n}} or {{mvar|n+1}} by 2 before the multiplication, whichever is even.  This does not require a [[conditional branch]] if implemented as <code>t = (n|1) * ((n+1)/2)</code>.  If <code>n</code> is odd, the [[binary OR]] operation <code>n|1</code> has no effect, so this is equivalent to <code>t = n * ((n+1)/2)</code> and thus correct.  If <code>n</code> is even, setting the low bit with <code>n|1</code> is the same as adding 1, while the 1 added before the division is [[Division (mathematics)#Of integers|truncated away]], so this is equivalent to <code>t = (n+1) * (n/2)</code> and also correct.