What could I use to show that triangular numbers should grow quadratically?

Question

I'm learning to work with polynomials, specifically right now I'm working with progressions like triangular/tetrahedral/pyramid numbers etc.

I know there are different ways to show the nth triangular number ( T(n) ) is

$$ T(n)= \frac{n(n+1)}{2} $$

Say I wanted to prove this by, first, showing that any formula for the nth triangular must be quadratic. Then I could prove that formula is correct using a Lagrange fit to $(1,1)$, $(2,3)$, $(3,6)$ (which should be unique).

I want to know if there's a way to show that this formula must be a polynomial, and that it must be 2nd degree, before actually finding that formula. Probably overkill for this particular proof, but maybe there's some other problem where that might be useful.

Answer 1

Welcome to MSE!

First, let me say that your idea to show an identity by showing it's a polynomial and doing some finite check is really clever! There's an entire book dedicated to these kinds of arguments, and I think it's fantastic that you're playing with these ideas. You're right that it's overkill for this problem, and you're also right that there are lots of interesting problems for which it is not overkill! If you want to read more about this and similar techniques, you should definitely check out A=B by Petkovsek, Wilf, and Zeilberger. A pdf is freely available at that link, if you're interested.

Now, to your question.

I'm not sure of a way to see that it must be a polynomial (without using some high powered tools). But here is one way we can modify your approach provided we're willing to guess that it's a polynomial:

First, we know that $\sum \approx \int$ (this is made precise with the euler-maclaurin formula¹). So since we're interested in $\sum_{x=0}^n x$, we might expect it to be approximately $\int_{x=0}^n x = \frac{n^2}{2}$. This tells us we should expect $T$ to be a quadratic polynomial.

Now we can follow your suggestion and use lagrange interpolation to compute $p(n) = \frac{n(n+1)}{2}$ is the unique quadratic agreeing with $T$ on $3$ points. Superficially this seems right, as we even get the constant factor of $\frac{1}{2}$ that we would expect from our informal comparison with integration.

But how do we really show that $T(n) = p(n)$?

The quickest way that I can see is via recurrences. Notice

• $T(0) = 0$
• $T(n+1) = (n+1) + T(n)$

uniquely defines $T(n)$².

So if we can show your polynomial satisfies these equations, then it must agree with $T$ everywhere (do you see why?).

Now we're basically done! There's one more finite check to do:

• $p(0) = \frac{0(0+1)}{2} = 0$
• $p(n+1) = n+1 + p(n)$

This particular finite check is basically the inductive proof that $p(n)$ is the right formula. But that makes sense -- in a simple problem like this, there's only so many genuinely unique ways to prove that the formula is right. If you wanted to, we could also check the inductive case by showing $p(n+1) - (n+1+p(n))$ is $0$ on three different inputs. Since it's a polynomial of degree $\leq 2$, that means it must be $0$ everywhere. That's perhaps more in the spirit of your idea (and it's what is done in A=B).

---

¹: In fact, the euler-maclaurin formula guarantees that $T(n)$ must be a polynomial (see here, for instance) but that felt too high powered to use. As is mentioned in the comments, we could also quote a result about linear recurrences, but that felt too high powered as well (though substantially less high powered than euler-maclaurin).

²: Moreover, when you have a sum, it can often be a good idea to turn it into a recurrence relation in this way! This is a nice trick to have in your back pocket, as often we have extra tools (generating functions, etc.) for handling recurrence relations.

---

I hope this helps ^_^

Answer 2

From their definition, the triangular numbers follow the recurrence

$$T(n)-T(n-1)=n$$ such that the RHS is a linear polynomial.

Now for any polynomial $T$, $T(x)-T(x-1)$ is a polynomial one degree lower (when expanding the powers of $x-1$, the leading terms $t_dx^d$ cancel out, and the term $dt_dx^{d-1}$ appears). Hence if $T$ is a polynomial, it must be quadratic.

Next, as $T$ coincides with the summation for infinitely many values of $n$, it is the unique polynomial that fits.

---

Note that $f(x)=\dfrac{x(x+1)}2$ is not the only function that coincides with $T(n)$ for every $x=n$. But for every function $g(x)$ that does so, the difference

$$h(n)=g(n)-f(n)=0$$ and this "perturbation term" is unimportant.

Example of a non-polynomial function (in blue):