I need to find a formula expressed in binomial coefficients of the following triangle:
$$D_n^k=\begin{cases}
n \quad\quad\quad\quad\quad\text{ if } n=k \text{ or } k=0 \\
D_{n-1}^k+D_{n-1}^{k-1} \text{ otherwise}
\end{cases}$$
This triangle is the same as the Pascal's triangle, except for the base value ($n$ instead of $1$).
Best Answer
We derive a formula with the help of generating functions for \begin{align*} D_n^k&=D_{n-1}^{k}+D_{n-1}^{k-1}\qquad\ \ n\geq 1,k\geq 1\tag{1}\\ D_0^k&=k\qquad\qquad\qquad\qquad k\geq 1\\ D_n^0&=n\qquad\qquad\qquad\qquad n\geq 1 \end{align*}
Comment:
In (2) we split the sum in order to apply the recurrence relation (1).
In (3) we apply the recurrence relation (1).
In (4) we use $\sum_{n=1}^\infty nz^n=z\sum_{n=1}^\infty nz^{n-1}=z\frac{d}{dz}\frac{1}{1-z}=\frac{z}{(1-z)^2}$. We also shift the index $n$ by one.
In (5) we split the double sum and shift the index $k$ by one at the right-most sum.
We derive a formula for $D_n^k$ from the generating function (6). It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.
Comment:
In (7) we do a geometric series expansion multiple times.
In (8) we apply the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$. We also set the upper indices to $n$ since values $j>n$ do not contribute.
In (9) we select the coefficient of $x^{n-j}$.
In (10) we apply the finite geometric summation formula.
In (11) we do some simplifications.
In (12) we select the coefficients accordingly.