MATH 631: Solution to Homework 1, Problem 1
September 15, 1999

Let n and m be positive integers. Let A be the $n\times n$ matrix with 1's on and above the diagonal, and zeroes below the diagonal. Thus a_ij=1 if $i\le j$and a_ij=0 if i>j. We can express this differently as follows.

If $a,b\in\mathbb{Z}$, we define the binomial coefficient $\binom{a}{b}$ to be 0 if b<0 or b>a. If $0\le b\le a$, then $\binom{a}{b}=\dfrac{a!}{b!(a-b)!}$, as usual (where 0!=1). With this notation, we can write $a_{ij}=\binom{j-i}{j-i}$.

There is an extremely important identity we will need below.

$$\binom{a+1}{b}=\binom{a}{b}+\binom{a}{b-1}\qquad \text{for all }a,b\in\mathbb{Z}.$$

Answer: Let m be a positive integer and set B=A^m. Then $${b_{ij}=\binom{m-1+j-i}{j-i}}$$. Note that this formula tells us that B is an upper triangular matrix with 1's on the diagonal, so it is at least part right! Also note that the formula does not depend on n, which is a bit of a surprise.

Proof: We will prove the formula by induction on m. The formula is correct for m=1, as we noted above.

Set C=A^m+1=BA. Then
$$\begin{align*} c_{ij} &= \sum_{k=1}^m b_{ik}a_{kj} = \sum_{k=1}^j b_{ik} = \sum_... ...}\quad \binom{m+r}{r} - \binom{m-1}{-1} = \binom{(m+1)-1+j-i}{j-i)},\end{align*}$$
as required.