# What is the next number of this sequence?

Consider the sequence $(a_{n})_{n \in \mathbb{N}}$ of positive integers whose first few entries are

$2 ~~ 6 ~~ 20 ~~ 70 ~~ 252 ~~ \ldots$

Now, consider the infinite matrix

$$\left[ \begin{array}{cc} 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 2 & 3 & 4 & 5 & 6 & \cdots \\ 1 & 3 & 6 & 10 & 15 & 21 & \cdots \\ 1 & 4 & 10 & 20 & 35 & 56 & \cdots \\ 1 & 5 & 15 & 35 & 70 & 126 & \cdots \\ 1 & 6 & 21 & 56 & 126 & 252 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} \right].$$

• The $(i,j)$-entry of this matrix indicates the number of ways of traveling from the $(1,1)$-entry to the $(i,j)$-entry of an $(n \times n)$-matrix by only moving either right or down.

• The sequence $(a_{n})_{n \in \mathbb{N}}$ is formed from the diagonal elements of this matrix, starting from the $(2,2)$-entry.

Question: How does one generate the $n$-th entry of the sequence without referring to the matrix above? Is there a generating function for the sequence?

• – Amzoti Dec 27 '12 at 3:51
• The number of moves to the right and the number of moves down must both equal $n-1$ – Karthik C Dec 27 '12 at 3:56

Note that in the matrix $a(i,j) = \dbinom{i+j}i$. You are interested in the diagonal elements i.e. $$a(n,n) = \dbinom{n+n}n = \dbinom{2n}n$$
The formula is $$\forall n \in \mathbb{N}: \quad a_{n} = \binom{2n}{n}.$$ Notice that if you rotate the infinite square matrix $45^{\circ}$ clockwise, you will obtain Pascal's Triangle. This shows, heuristically, that the sequence is made up of the central binomial coefficients.
You also asked for the generating function, which is $$\frac{1}{\sqrt{1-4x}}.$$