Finding a formula for a triangle similar to Pascal's. 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$).
 A: 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*}

We obtain
  \begin{align*}
D(x,y)&=\sum_{n=1}^\infty\sum_{k=0}^nD_n^kx^ny^k\\
&=\sum_{n=1}^\infty  D_n^0x^n+\sum_{n=1}^\infty D_n^nx^ny^n+\sum_{n=2}^\infty\sum_{k=1}^{n-1}D_n^kx^ny^k\tag{2}\\
&=\sum_{n=1}^\infty nx^n+\sum_{n=1}^\infty nx^ny^n+\sum_{n=2}^\infty\sum_{k=1}^{n-1}\left(D_{n-1}^k+D_{n-1}^{k-1}\right)x^ny^k\tag{3}\\
&=\frac{x}{(1-x)^2}+\frac{xy}{(1-xy)^2}+x\sum_{n=1}^\infty\sum_{k=1}^{n}\left(D_n^k+D_n^{k-1}\right)x^ny^k\tag{4}\\
&=\frac{x}{(1-x)^2}+\frac{xy}{(1-xy)^2}+x\sum_{n=1}^\infty\sum_{k=1}^{n}D_n^kx^ny^k\\
&\qquad+xy\sum_{n=1}^\infty\sum_{k=0}^{n-1}D_n^kx^ny^k\tag{5}\\
&=\frac{x}{(1-x)^2}+\frac{xy}{(1-xy)^2}+x\left(D(x,y)-\sum_{n=1}^\infty nx^n\right)\\
&\qquad+xy\left(D(x,y)-\sum_{n=1}^\infty nx^ny^n\right)\\
&=\frac{x}{1-x}+\frac{xy}{1-xy}+x(1+y)D(x,y)\\
\color{blue}{D(x,y)}&\color{blue}{=\frac{1}{1-x(1+y)}\left(\frac{x}{1-x}+\frac{xy}{1-xy}\right)}\tag{6}
\end{align*}
Note the relationship of $D(x,y)$ with a generating function for the binomial coefficients $\binom{n}{k}$. We have for $ n,k\geq 0$:
  \begin{align*}
\frac{1}{1-x(1+y)}=\sum_{n=0}^\infty x^n(1+y)^n=\sum_{n=0}^\infty\sum_{k=0}^n\color{blue}{\binom{n}{k}}x^ny^k
\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.

We obtain from (6) for $n\geq 1$ and $0\leq k\leq n$:
  \begin{align*}
\color{blue}{D_n^k}&=[x^ny^k]\frac{1}{1-x(1+y)}\left(\frac{x}{1-x}+\frac{xy}{1-xy}\right)\\
&=[x^ny^k]\sum_{j=0}^\infty x^j(1+y)^j\sum_{q=1}^\infty x^q\\
&\qquad+[x^ny^k]\sum_{j=0}^\infty x^j(1+y)^j\sum_{q=1}^\infty x^qy^q\tag{7}\\
&=[y^k]\sum_{j=0}^n[x^{n-j}](1+y)^j\sum_{q=1}^\infty x^q\\
&\qquad+[y^k]\sum_{j=0}^n[x^{n-j}](1+y)^j\sum_{q=1}^\infty x^qy^q\tag{8}\\
&=[y^k]\sum_{j=0}^{n-1}(1+y)^j+[y^k]\sum_{j=0}^{n-1}(1+y)^jy^{n-j}\tag{9}\\
&=[y^k]\frac{(1+y)^n-1}{(1+y)-1}+[y^k]y^n\frac{\left(\frac{1+y}{y}\right)^n-1}{\left(\frac{1+y}{y}\right)-1}\tag{10}\\
&=[y^{k+1}]\left((1+y)^n-1\right)+[y^{k-1}]\left((1+y)^n-y^n\right)\tag{11}\\
&\,\,\color{blue}{=\binom{n}{k+1}+\binom{n}{k-1}}\tag{12}
\end{align*}
Note in (12) we use for integers $p,q$, with $p$  non-negative, the convention $\binom{p}{q}=0$ if $q<0$ or $p<q$. See for instance formula (5.1) in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik.

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.
A: As darij grinberg has pointed out, the formula is $$D_n^k=\binom{n+2}{k+1}-2\binom{n}{k}$$ Here is a simple proof that it fits the definition:
$$D_n^n=\binom{n+2}{n+1}-2\binom{n}{n}=n+2-2=n$$
$$D_n^0=\binom{n+2}{1}-2\binom{n}{0}=n+2-2=n$$
$$D_n^k=\binom{n+2}{k+1}-2\binom{n}{k}\stackrel{(*)}{=}\binom{n+1}{k+1}+\binom{n+1}{k}-2(\binom{n-1}{k}+\binom{n-1}{k-1})\\=\binom{n+1}{k+1}-2\binom{n-1}{k}+\binom{n+1}{k}-2\binom{n-1}{k-1}=D_{n-1}^k+D_{n-1}^{k-1}$$
