4
$\begingroup$

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

\begin{equation} \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]. \end{equation}

  • 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?

  • 0
    The number of moves to the right and the number of moves down must both equal $n-1$2012-12-27

3 Answers 3

3

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$

2

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.

2

Marvis and Haskell Curry have given you the closed formula.

You also asked for the generating function, which is $\frac{1}{\sqrt{1-4x}}.$