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.

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?

share|improve this question
7  
    
The number of moves to the right and the number of moves down must both equal $n-1$ –  Host-website-on-iPage Dec 27 '12 at 3:56

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Marvis and Haskell Curry have given you the closed formula.

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

share|improve this answer

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.