Úvod

Tento příspěvek se věnuje trojúhelníkovým číslům, ozn. $T_n$, definovaným předpisem $$ T_n = \sum_{k=1}^n k, \quad n \in \mathbb{N}. $$ Název odkazuje na jejich geometrickou interpretaci: $T_n$ je počet teček, které lze pravidelně uspořádat do rovnostranného trojúhelníku o straně s $n$ tečkami, jak ukazuje následující obrázek:

Čtenář jistě zná z dřívějšího studia uzavřený vzorec, který nás zbaví symbolu sumy, $$ T_n = \frac{n(n+1)}{2}, \quad n\in\mathbb{N}. $$ V databázi celočíselných posloupností OEIS najdeme tuto posloupnost pod označením A000217 (OEIS ji indexuje od $T_0 = 0$).

Trojúhelníková čísla mají dlouhou historii. Již pythagorejci (6. až 5. století př. n. l.) zkoumali vlastnosti čísel pomocí kamínků rozkládaných na podložce. Jejich posvátná tetraktys, trojúhelník z deseti bodů, není nic jiného než $T_4$. Podle tradice si také všimli, že dvě stejná trojúhelníková čísla lze složit do „podlouhlého“ obdélníkového tvaru obdélníku o stranách $n$ a $n+1$, což je přesně myšlenka, ke které se vrátíme v části o geometrickém pohledu níže.

Vzorec pro součet znal pravděpodobně také Gauss, ale zhruba tisíc let před ním se objevuje úloha o součtu čísel od $1$ do $100$ ve sbírce Propositiones ad acuendos iuvenes („Úlohy k bystření mládeže“), připisované Alkuinovi z Yorku (zemřel 804), učenci na dvoře Karla Velikého. Na schodišti o sto schodech sedí na prvním schodu jeden holub, na druhém dva, na třetím tři a tak dále až po stý schod. Kolik je holubů dohromady? Alkuin úlohu řeší párováním schodů, na kterých sedí dohromady $100$ holubů: první s devadesátým devátým, druhý s devadesátým osmým atd. Takových párů je $49$ a bez páru zůstane padesátý a stý schod, celkem je tedy holubů $49\cdot100 + 50 + 100 = 5050$.

V textu níže prozkoumáme několik různorodých přístupů k nalezení explicitního vyjádření $T_n$. Každý z nich bude založen na mírně jiném úhlu pohledu a bude využívat velmi různorodé techniky. Znalost tohoto vzorce je užitečná, objevuje se poměrně často. Nejlepší způsob jak si ho zapamatovat, je znát jeho interpretaci a i důvod proč platí. Pak je výrazně snazší si ho případně znovu odvodit.

Uhodnutí a matematická indukce

Nejpřímočařejší cestou ke vzorci pro $T_n$ je vypsat si prvních několik hodnot, $$ \begin{aligned} T_1 &= 1, \\ T_2 &= 1 + 2 = 3, \\ T_3 &= 1 + 2 + 3 = 6, \\ T_4 &= 1 + 2 + 3 + 4 = 10, \\ T_5 &= 1 + 2 + 3 + 4 + 5 = 15. \end{aligned} $$ Po chvíli zírání (viz též graf níže) a zahřívání mozkových závitů si všimneme, že tyto hodnoty vystihuje vztah $T_n = \frac{n(n+1)}{2}$. Skutečně, $$ \begin{aligned} T_1 &= 1 = \frac{1\cdot2}{2}, \\ T_2 &= 3 = \frac{2\cdot3}{2}, \\ T_3 &= 6 = \frac{3\cdot4}{2}, \\ T_4 &= 10 = \frac{4\cdot5}{2}, \\ T_5 &= 15 = \frac{5\cdot6}{2}. \end{aligned} $$ Tím jsme ale vztah $T_n = \frac{n(n+1)}{2}$ ověřili jen pro $n=1,2,3,4,5$. S tím se nemůžeme spokojit!

Platnost pro zbývajících nekonečně mnoho přirozených čísel $n$ dokážeme matematickou indukcí. Pro $n=1$ jsme vztah ověřili výše, zbývá tedy provést indukční krok. Předpokládejme, že pro nějaké $n\in\mathbb{N}$ platí $T_n = \frac{n(n+1)}{2}$ (indukční předpoklad, IP). Potom $$ \begin{aligned} T_{n+1} &= \sum_{k=1}^{n+1} k = \left(\sum_{k=1}^n k\right) + n+1 \\ &\overset{\text{IP}}{=} \frac{n(n+1)}{2} + n + 1 \\ &= \frac{n(n+1)+2(n+1)}{2} \\ &= \frac{(n+1)(n+2)}{2}, \end{aligned} $$ což jsme chtěli dokázat.

Tento postup odvození je sice elementární, ale nenabízí hlubší pochopení. Vzorec jsme v podstatě uhodli (zásadní a těžký krok) a poté pouze dokázali jeho platnost.

Uhodnutí vs. Ansatz

Uhodnout vzorec pro $T_n$ z prvních několika hodnot nemusí být úplně jednoduché. Třeba máme špatný den nebo nemáme štěstí. I v obecnějším případě ale můžeme na problém zaútočit mechaničtější technikou. Podíváme-li se na graf prvních několika hodnot,

měla by nám být povědomá kvadraticky vypadající závislost. Totéž napoví i rozdíly sousedních hodnot: $T_{n+1} - T_n = n+1$ rostou lineárně, takže druhé diference jsou konstantní, což je diskrétní obdoba konstantní druhé derivace kvadratické funkce. Můžeme se proto pokusit hledat vzorec v obecném tvaru (tzv. Ansatz, německy přístup či nástavec) $$ T_n = \alpha n^2 + \beta n + \gamma. $$ Neznámé konstanty zkusíme určit z prvních několika hodnot (tři neznámé, tedy tři rovnice): $$ \begin{aligned} T_1 &= \alpha + \beta + \gamma = 1, \\ T_2 &= 4\alpha + 2\beta + \gamma = 3, \\ T_3 &= 9\alpha + 3\beta + \gamma = 6. \end{aligned} $$ Gaussovou eliminační metodou (GEM), kterou zde nebudeme rozepisovat, snadno najdeme jediné řešení $\alpha=\frac{1}{2}$, $\beta=\frac{1}{2}$ a $\gamma=0$. Máme tedy kandidáta na vzorec, $T_n = \frac{n(n+1)}{2}$, který jsme ověřili pro $n=1,2,3$. Jeho platnost pro zbývající $n$ opět dokážeme matematickou indukcí.

Samotné vyřešení soustavy přitom nic nedokazuje. Třemi body s různými $x$-ovými souřadnicemi vždy prochází právě jeden polynom stupně nejvýše dva, takže soustava by měla řešení, i kdyby hledaná závislost kvadratická vůbec nebyla. Skutečnou informací je náš odhad tvaru vzorce. Kontrola dalším členem, např. $T_4 = \frac{4\cdot5}{2} = 10$, je užitečná zkouška, důkazem je ale teprve indukce.

„Gaussův trik“

Podle apokryfní legendy dostali mladý Gauss a jeho spolužáci ve škole za úkol sečíst všechna přirozená čísla od $1$ do $100$, tedy vypočítat $T_{100}$. Gauss si údajně všiml, že čísla nemusí sčítat postupně od nejmenšího po největší, ale může je sčítat po párech: $$ 1 + 2 + \cdots + 100 = (1+100) + (2+99) + \cdots + (50+51). $$ Každá ze závorek má součet $101$ a závorek je celkem $50$, takže $T_{100} = 50 \cdot 101 = 5050$. Jde vlastně o tentýž nápad, který o tisíc let dříve použil Alkuin.

Při přímém přenesení na obecné $n$ bychom museli rozlišit sudé a liché $n$, protože pro liché $n$ zbude uprostřed číslo bez páru. Rozboru se lze vyhnout drobnou obměnou: součet napíšeme dvakrát, jednou vzestupně a jednou sestupně, a sečteme čísla stojící pod sebou: $$ \begin{array}{rcccccccc} T_n &=& 1 &+& 2 &+& \cdots &+& n \\ T_n &=& n &+& (n-1) &+& \cdots &+& 1 \\ \hline 2T_n &=& (n+1) &+& (n+1) &+& \cdots &+& (n+1) \end{array} $$ V $k$-tém sloupci stojí čísla $k$ a $n+1-k$, takže každý z $n$ sloupců dává součet $n+1$. Proto $2T_n = n(n+1)$, tj. $T_n = \frac{n(n+1)}{2}$ pro všechna přirozená $n$. Případ $n=5$ ilustruje následující obrázek:

Tento postup je už více osvětlující. Jakmile pochopíte myšlenku se sečtením $T_n$ se sebou samým jen v jiném pořadí (spárování), tak je už poměrně těžké na ni zapomenout.

Geometrický pohled

Další způsob odvození vychází z geometrické představy názorně vystihující předchozí úvahy.

Trojúhelníkové číslo $T_n$ si můžeme představit jako počet teček v rovině uspořádaných do sloupečků o $1$, $2$, $3$, …, $n$ tečkách, které dohromady tvoří pravoúhlý trojúhelník. Přiložíme-li k němu stejný trojúhelník otočený o $180^\circ$, doplníme ho na obdélník o $n$ sloupcích a $n+1$ řádcích. Případ $T_5$ ukazuje následující obrázek:

Obdélník obsahuje $n(n+1)$ teček a jeden trojúhelník, který nás ve skutečnosti zajímá, právě polovinu z nich, tj. $T_n = \frac{n(n+1)}{2}$. Právě takto podle tradice uvažovali pythagorejci se svými kamínky.

Kombinatorický pohled

Součet prvních $n$ přirozených čísel lze snadno kombinatoricky interpretovat. Kolika způsoby lze z $n+1$ lidí vybrat dvojice? Vzhledem k symetrii vztahu „být ve dvojici“ lze celkový počet dvojic spočítat takto: označíme-li uvažované lidi čísly $1$ až $n+1$, pak člověk s číslem $n+1$ má možnost utvořit $n$ dvojic. Člověk s číslem $n$ může utvořit dalších $n-1$ nových dvojic. Pokračujeme tak dále až k člověku číslo $2$, který může vytvořit $1$ novou dvojici. Celkový počet dvojic tak je $n + (n-1) + \cdots + 2 + 1$. Počet způsobů jak vybrat dvojice z $n+1$ lidí je ovšem roven kombinačnímu číslu $\binom{n+1}{2}$, tudíž

$$ T_n = \binom{n+1}{2} = \frac{n(n+1)}{2}, \quad n\in\mathbb{N}. $$

Algebraický trik

Ke kýženému vzorci se můžeme dostat i přímým výpočtem. Nejprve sčítance upravíme na první pohled neintuitivním způsobem: $$ T_n = \sum_{k=1}^n k = \frac{1}{2}\sum_{k=1}^n\left(k^2 + 2k + 1 - k^2 - 1\right). $$ Úprava je korektní: v závorce se vše kromě $2k$ odečte a dvojka se zkrátí s $\frac{1}{2}$. Jejím smyslem je vytvořit v sumě rozdíl $(k+1)^2 - k^2$. Po rozdělení na tři sumy dostaneme $$ T_n = \frac{1}{2} \left( \sum_{k=1}^n (k+1)^2 - \sum_{k=1}^n k^2 - \sum_{k=1}^n 1 \right). $$ Součet $n$ jedniček je $n$. V závorce pak zbývá rozdíl dvou sum, které mají stejné meze, ale jejich sčítance jsou vůči sobě posunuté o $1$. Odečtou se tak všechny členy kromě posledního členu první sumy a prvního členu druhé sumy (jde o tzv. teleskopickou sumu), a proto $$ T_n = \frac{1}{2}\left((n+1)^2 - 1 - n\right) = \frac{n(n+1)}{2}. $$ Síla tohoto triku se ukáže teprve u složitějších součtů. Stejný postup s rozdílem $(k+1)^3 - k^3$ vede ke vzorci pro $\sum_{k=1}^n k^2$, který bychom uhodli mnohem obtížněji a párovací trik z předchozí části textu by zde také nepomohl. Stejným trikem lze sečíst $\sum_{k=1}^n k^\ell$ pro $\ell\in\mathbb{N}$.

Lineární rekurence

Dalším možným přístupem je využít mašinerii lineárních rekurentních rovnic. Pro tak jednoduchou úlohu jde o kanón na vrabce, dobře na ní ale uvidíme, jak metoda funguje. Z definice $T_n$ plyne rekurentní vztah $$ T_{n+1} - T_n = n + 1, \quad n\geq1. $$ Jde o lineární rekurentní rovnici s konstantními koeficienty, s nenulovou (kvazi)polynomiální pravou stranou a s počáteční podmínkou $T_1 = 1$.

Pro takové rovnice umíme řešení sestrojit. Charakteristický polynom $p(z) = z - 1$ má jediný kořen $z = 1$. Obecné řešení přidružené homogenní rovnice je proto tvaru $\alpha \cdot 1^n = \alpha$, kde $\alpha$ je zatím neurčená reálná konstanta. Zbývá najít partikulární řešení nehomogenní rovnice. Víme, že existuje ve tvaru $(\beta n + \gamma) \cdot n^1 \cdot 1^n$, kde faktor $n^1$ odpovídá tomu, že $1$ je jednonásobným kořenem charakteristického polynomu. Dosazením tohoto tvaru do rekurence dostaneme po jednoduchých úpravách $$ (2\beta-1)n+\beta+\gamma-1 = 0, \quad n \geq 1. $$ Tyto rovnosti platí pro všechna uvedená $n$ právě tehdy, když $\beta = \frac{1}{2}$ a $\gamma = \frac{1}{2}$. Obecné řešení naší rekurentní rovnice je tedy tvaru $$ T_n = \alpha + \frac{n(n+1)}{2}, $$ kde konstantu $\alpha$ určíme z počáteční podmínky. Protože $T_1 = 1$ a zlomek na pravé straně má pro $n=1$ hodnotu $1$, je nutně $\alpha = 0$.

Krok stranou

Existují i obskurnější způsoby odvození uzavřeného vzorce pro $T_n$. Jako ukázku uveďme jeden, který využívá vzorec pro součet prvních několika členů geometrické posloupnosti a diferenciální počet. Zajímavé na něm je, že první krok spočívá v zesložitění řešené úlohy. Uvádíme ho pro to, že podobné techniky často pomohou v případech, kdy předchozí elementární selhávají.

Pro pevně zvolené $n \in \mathbb{N}$ definujme funkci $$ f(x) = \sum_{k=1}^n k x^{k-1}, \quad x\in\mathbb{R}. $$ Zřejmě platí $T_n = f(1)$. Ve sčítancích $kx^{k-1}$ ale poznáváme derivaci funkce $x^k$. Díky linearitě derivace tak lze naši funkci zapsat ve tvaru $$ f(x) = \left( \sum_{k=1}^n x^k \right)'. $$ Suma pod derivací by nám měla být povědomá: jde o součet prvních $n$ členů geometrické posloupnosti s prvním členem $x$ a kvocientem $x$. Pro $x \neq 1$ tedy platí $$ \begin{aligned} f(x) &= \left(x \cdot \frac{1 - x^n}{1 - x} \right)' = \frac{1-x^n}{1-x} + x\cdot \frac{-nx^{n-1}(1-x)-(1-x^n)(-1)}{(1-x)^2} \\ &=\frac{1-x^n}{1-x} + x \cdot \frac{1 - nx^{n-1} + (n-1)x^n}{(1-x)^2}. \end{aligned} $$ Funkce $f$ je polynom, a tedy spojitá, takže hodnotu $T_n = f(1)$ dostaneme jako limitu tohoto výrazu pro $x \to 1$. Obě dílčí limity jsou typu $\frac{0}{0}$ a spočteme je pomocí l'Hospitalova pravidla (detaily vynecháváme): $$ \begin{aligned} T_n &= \lim_{x\to1} f(x) = \lim_{x\to1}\frac{1-x^n}{1-x}+ 1 \cdot \lim_{x\to1}\frac{1 - nx^{n-1} + (n-1)x^n}{(1-x)^2} \\ &=\lim_{x\to1}\frac{-nx^{n-1}}{-1} + \lim_{x\to1}\frac{-n(n-1)x^{n-2} + n(n-1)x^{n-1}}{-2(1-x)} \\ &=n + n(n-1) \lim_{x\to1}\frac{-(n-2)x^{n-3}+(n-1)x^{n-2}}{2} \\ &=n + n(n-1) \frac{1}{2} = \frac{n(n+1)}{2}. \end{aligned} $$

Což je opět správný výsledek.

Další souvislosti a poznámky

Na závěr uveďme několik doplňujících poznámek.

Árjabhata a součty trojúhelníkových čísel

Indický matematik a astronom Árjabhata (narozen 476) uvádí ve svém díle Árjabhatíja z roku 499 vztah mezi součtem třetích mocnin a trojúhelníkovými čísly, $$ \sum_{k=1}^n k^3 = \left(\sum_{k=1}^n k\right)^2 = T_n^2. $$ Árjabhatovi je připisován i vzorec pro součet prvních $n$ trojúhelníkových čísel, $$ T_1 + T_2 + \cdots + T_n = \frac{n(n+1)(n+2)}{6}. $$ Důkaz obou vztahů, třeba matematickou indukcí, přenecháváme čtenáři jako cvičení.

Implementace

Z pohledu programátora je rozdíl mezi definicí a uzavřeným vzorcem zřejmý: cyklus (tj. suma) potřebuje $n$ sčítání, vzorec jen konstantní počet operací.

Naivní přepis vzorce ale skrývá past. Například pro 32bitový znaménkový typ int32_t (maximum $2^{31}-1 = 2\,147\,483\,647$) a $n = 65\,535$ se výsledek $T_n = 2\,147\,450\,880$ do typu ještě vejde, mezivýsledek $n(n+1) = 4\,294\,901\,760$ ale přeteče. V jazycích C a C++ je přetečení znaménkového typu nedefinované chování. Pomůže nejprve vydělit dvojkou ten z činitelů $n$ a $n+1$, který je sudý (jeden z nich sudý být musí):

#include <stdint.h>

int32_t T(int32_t n) {
    return (n % 2 == 0) ? (n / 2) * (n + 1)
                        : n * ((n + 1) / 2);
}
`