Finding a formula for a triangle similar to Pascal's.

Question

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

Answer 1

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

Answer 2

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.