# How can I represent the sequence of triangle numbers as a formula

Given the sequence:

$$\begin{gather*} 1^2 \\\ 2^2 - 1^2 \\\ 3^2 - 2^2 + 1^2\\\ 4^2 - 3^2 + 2^2 - 1^2\\\ 5^2 - 4^2 + 3^2 - 2^2 + 1^2\\\ \vdots \end{gather*}$$

It's clear that the pattern results in the triangular number sequence $(1,3,6,10,15,\ldots)$ but I'm having trouble putting it into a formula in terms of $n$. Any tips are appreciated!

-
Perhaps you have seen the Wikipedia page on triangular numbers? Or is your question asking how to prove that $$\sum_{k=1}^n (-1)^{n-k}k^2=T_n$$ where $T_n$ is the $n$th triangular number? –  Zev Chonoles Jul 24 '11 at 22:10
sorry, have been trying to figure out latex formatting since the moment I posted this. –  David Jul 24 '11 at 22:11
@Zev - I have that page open, and read it before posting my question, but don't see that representation of the sequence in there. But you answered my question. Thanks! Also, thanks for the formatting. I'll figure that out before I post again. –  David Jul 24 '11 at 22:18

I'm not sure I answered your question; I was only making sure I understood what you are asking. However, I will post a hint: A good way to prove something like $$\sum_{k=1}^n (-1)^{n-k}k^2=T_n$$ is via induction on $n$. If you can prove the above statement is true when $n=1$, and you can prove that, whenever it is true for $n=a$, it will also be true for $n=a+1$, then it will be true for all $n$.

-
You did actually; I was asking how to show the sequence as a formula in terms of n. Proving that it holds for all n (via induction) is up next for this problem and I'm pretty comfortable with that piece of it (I think - at least I have been on previous problems). I've done a lot of proofs by induction, but not many where I've had to first formulate the sequence myself. –  David Jul 24 '11 at 22:33
Ah, I see! I'm glad to have helped! –  Zev Chonoles Jul 24 '11 at 22:34

$T_n = \frac{n(n+1)}{2}$ and $T_{n-1} = \frac{n(n-1)}{2}$ so $T_n+T_{n-1} = n^2$, i.e. $T_n= n^2- T_{n-1}$.

So knowing $T_1=1$, you can use induction to show your result.

Another way of looking at the question is to see the triangle number as the sum of L-shaped strips and each L-shape as the difference between consecutive squares.

-
What did you use to make these pictures? –  mixedmath Jul 25 '11 at 3:08
@mixedmath: MS Paint, plus some I made earlier. –  Henry Jul 25 '11 at 3:41
+1! In "A Brief History of Time", Hawking says that he did not use formulas in his book because "the number of readers is inversely proportional to the number of formulas", or something along that line. :) –  Bruno Joyal Jul 25 '11 at 5:05

Yet another way to prove it is by first showing that $$n^2=\binom{n+1}{2}+\binom{n}2,$$ and then using a form of telescoping: $$\binom {n+1}2+\binom n2-\binom n2-\binom{n-1}2+\cdots+(-1)^n\binom 22-(-1)^n\binom 22=\binom{n+1}2.$$

-
Hi - can you explain the notation you are using with n+1 over 2 inside parens? Sorry for what's probably a basic question, I'm rusty and trying to get my feet under me. –  David Jul 24 '11 at 23:57
@David: $\displaystyle{n \choose k} = \dfrac{n!}{k!(n-k)!}$ is the binomial coefficient (number of ways to choose $k$ things out of a set of $n$). The case $k = 2$ of interest here is very simple: $\displaystyle{n \choose 2} = \dfrac{n(n-1)}{2}$. –  t.b. Jul 25 '11 at 2:56
In mathematical work, $\dbinom{n}{r}$ denotes the number of ways of choosing $r$ objects from $n$ objects. On my scientific calculator, and in high school, the same number is denoted by ${}_n{\rm}C_r$. Sometimes it is written as ${\rm C}(n,r)$. For details, look in Wikipedia for binomial coefficient. You will soon need these! –  André Nicolas Jul 25 '11 at 2:57
Thanks to both of you! –  David Jul 25 '11 at 3:13

For $n=1,2,3,\dots$, let $T_n$ be the $n$-th triangular number, and let $U_n$ be the $n$-th element of our sequence.

We can use the following principle, which we deliberately state a little vaguely. If two sequences begin in the same way, and satisfy the same recurrence, then the sequences are the same. (If the recurrence is second-order, as in the Fibonacci recurrence, "start in the same way" means that the first two terms agree.)

What recurrence shall we use? Note that $U_1=T_1$, so the two sequences start in the same way. It is obvious that $U_{n-1}+U_n=n^2$, or equivalently $U_n=n^2-T_{n-1}$. So if we can show that $T_n=n^2-T_{n-1}$, we will be finished.

In this case, we know an explicit formula for the $n$-th triangular number, since, essentially from the definition of $T_n$, we know that $T_n=1+2+\cdots+n$, and the sum of this arithmetic series is well-known, it is $n(n+1)/2$. Thus $$T_n+T_{n-1}=\frac{(n)(n+1)}{2}+\frac{(n-1)(n)}{2}=n^2,$$ and therefore the sequence $(T_n)$ satisfies the recurrence $T_n=n^2-T_{n-1}$. This completes the proof.

The general idea is quite useful, since in combinatorics, explicit formulas are (after a while) relatively uncommon, but recurrences are quite common.

-

For each pair of squares:

$(n+1)^2-n^2=2n+1=(n+1)+n$

From which the result follows for an even number of terms. For an odd number of terms add $-0^2$ to the end of the sequence, to get an even number of terms with the same sum.

-