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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Marvis and Haskell Curry have given you the closed formula.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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