Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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
add comment

5 Answers

up vote 3 down vote accepted

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$.

share|improve this answer
    
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
add comment

$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}$.

enter image description here

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.

enter image description here

share|improve this answer
    
What did you use to make these pictures? –  mixedmath Jul 25 '11 at 3:08
1  
@mixedmath: MS Paint, plus some I made earlier. –  Henry Jul 25 '11 at 3:41
2  
+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
add comment

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.$$

share|improve this answer
    
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
2  
@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
1  
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.