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.

How to prove that $\dfrac{1}{(1-x)^3}$ is the generating function for the triangular numbers?

The $n^{\text{th}}$ triangular number is defined as $T_n = \displaystyle{n+1 \choose 2}$.

I used calculus ("cheating") and found out that $$\displaystyle\sum_{n=0}^{\infty} -{n \choose 2}x^{n-2} = \frac{1}{(1-x)^3}$$ and I know that $n - \displaystyle{n+1 \choose 2} = -{n \choose 2}$ and that $T_n = \displaystyle{n \choose 2}+n$.

Basically I'm not sure what the right way is.

share|improve this question
add comment

3 Answers

up vote 6 down vote accepted

You can start with the geometric series:

$$\frac1{1-x}=\sum_{n\ge 0}x^n\;.$$

Now differentiate:

$$\frac1{(1-x)^2}=\sum_{n\ge 0}nx^{n-1}=\sum_{n\ge 1}nx^{n-1}=\sum_{n\ge 0}(n+1)x^n\;.$$

And differentiate again:

$$\frac2{(1-x)^3}=\sum_{n\ge 0}n(n+1)x^{n-1}=2\sum_{n\ge 0}T_nx^{n-1}=2\sum_{n\ge 1}T_nx^{n-1}=2\sum_{n\ge 0}T_{n+1}x^n\;.$$

Thus,

$$\sum_{n\ge 0}T_{n+1}x^n=\frac1{(1-x)^3}\;.$$

However, this isn’t the generating function for the triangular numbers as you’ve defined them: that would be

$$\sum_{n\ge 0}T_nx^n=\sum_{n\ge 1}T_nx^n=x\sum_{n\ge 1}T_nx^{n-1}=x\sum_{n\ge 0}T_{n+1}x^n=\frac{x}{(1-x)^3}\;.$$

share|improve this answer
1  
How do you know all this stuff? omg no one's brain works that fast –  Person Jul 1 '13 at 6:54
3  
@Person: It doesn’t have to work quite so fast when it’s been working for $65$ years: some of the old workings are pretty near the surface! :-) –  Brian M. Scott Jul 1 '13 at 6:59
    
Also note that these are in fact very standard relations that hold between "extended" binomial coefficients, those occurring in $(1-x)^{-n}$, and ordinary binomial coefficients, as I explained in my answer. They are relatively easy to memorise. –  Marc van Leeuwen Jul 1 '13 at 7:47
add comment

Here is another proof:

$$ \frac 1{(1-x)^3} = (1+x+x^2+x^3+\dotsb)^3 $$ A monomial in the expansion of this product corresponds to a choice of one summand from each of the three factors; for example, I could choose $x^2$ from the first factor, $1=x^0$ from the second factor and $x^7$ from the third factor to get a monomial $x^9$ in the product. In other words, a monomial in the product corresponds to a vector $(n_1,n_2,n_3)$ in non-negative integers. The resulting monomial is $x^n$ if $n=n_1+n_2+n_3$.

Thus, the coefficient of $x^n$ in this product is the number of vectors $(n_1,n_2,n_3)$ in non-negative integers such that $n_1+n_2+n_3=n$. It is then a fairly standard combinatorial exercise to see that this is the same as $\binom{n+2}2$.

The first step of this proof may seem a bit fishy (introducing infinite sums), but can be justified using either analytic functions, or formal power series.

You can also generalize this proof to $(1-x)^{-k}$ for any $k\geq 1$.

share|improve this answer
add comment

These things are easier if you try to use combinatorial interpretations of coefficients, rather than such things as computing Taylor series (I am guessing that is what you mean by using analysis).

The triangular numbers as you defined them form column$~2$ of Pascal's triangle (which I'm thinking of as having its left edge vertical), with indexing starting such that $T_0$ is the entry $\binom12=0$ just above the right edge. For finding the coefficients of $(1-x)^{-3}$, it is useful to use the convention of extending the definition of binomial coefficients to arbitrary upper indices by setting $$ \binom ak=\frac{a(a-1)\ldots(a-k+1)}{k!}, $$ which is motivated in large part by the fact that the binomial formula generalises as (formal) power series: $$ (1+X)^a=\sum_{k=0}^\infty\binom akX^k \qquad\text{for all $a$.} $$ For $a=-3$ on gets the coefficients of $(1-x)^{-3}$ as $(-1)^k\binom{-3}k$ for $k\geq0$. Now from the definition above one gets $$ (-1)^k\binom{-n}k=(-1)^k\frac{(-n)(-n-1)\ldots(-n-k+1)}{k!} =\frac{n(n+1)\ldots(n+k-1)}{k!}=\binom{n+k-1}k $$ which explains why negative binomial powers are usually written for $1-x$ rather than for $1+x$: the binomial coefficients with negative upper index have alternating signs, which the $(-1)^k$ nicely cancels out. If the upper index $-n$ was a negative integer, then it is possible and often useful to apply symmetry of binomial coefficients to the final expression above, giving $$ (-1)^k\binom{-n}k=\binom{n+k-1}k=\binom{n+k-1}{n-1} $$ so that row$~-n$ of Pascal's "triangle", after throwing out the alternating signs, becomes column$~n-1$, starting from the entry $\binom{n-1}{n-1}$ on the right edge of the triangle.

[Please be warned that the symmetry law applied only holds for the non-extended binomial coefficients, those with non-negative integer indices; whence the restriction to $-n$ being a negative integer, so that one has $n+k-1\in\mathbf N$ for all $k\in\mathbf N$, and symmetry applies.]

All this is general, and often useful. In the case of the coefficients of $(1-x)^{-3}$ it gives then as $$ (-1)^k\binom{-3}k = \binom{3+k-1}{3-1} = \binom{k+2}2=T_{k+1}. $$

The above indicates that you can also get the coefficients of $(1-x)^{-4}$ as the tetrahedral numbers $\binom{k+3}3$, which are sums $\sum_{i=2}^{k+2}\binom i2$ of triangular numbers, and so forth.

I'll add a final remark. For $n=1$ the binomial power series gives $(1-X)^{-1}=\sum_{i\geq0}X^i$ . One can therefore interpret the coefficient $(-1)^k\binom{-n}k$ of $X^k$ in $(1-X)^{-n}$ as the coefficient of $X^k$ in $(\sum_{i\geq0}X^i)^n$. Combinatorially, this is the number of ways to write $k=i_1+\cdots+i_n$ as a sum of $n$ non-negative integers (which pick out the powers of $X$ in each factor to obtain a term $X^k$ in the product). The fact that this number equals $\binom{n+k-1}{n-1}$ can be understood by imagining writing down $n+k-1$ vertical strokes and choosing any $n-1$ of them which are turned into "$+$" signs; this gives such a sum by interpreting the remaining $k$ vertical strokes as tally marks each contributing to one of the $i_j$. An equivalent interpretation is to see it as the number of ways to choose $k$ items out of a set of $n$ options, with repetitions allowed: the items are the units (tally marks) in the sum, and the options are the $n$ terms $i_1,\ldots,i_n$ that they can contribute to. In this setting the argument that shows that the number is a binomial coefficient is sometimes referred to as "stars and bars".

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.