# Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$

\begin{array}{cccccccccc} 1 & = & K_{1}\tbinom{n+1}{0}\\ 1 & = & K_{1}\tbinom{n+2}{1} & +K_{2}\tbinom{n+2}{0}\\ 1 & = & K_{1}\tbinom{n+3}{2} & +K_{2}\tbinom{n+3}{1} & +K_{3}\tbinom{n+3}{0}\\ 1 & = & K_{1}\tbinom{n+4}{3} & +K_{2}\tbinom{n+4}{2} & +K_{3}\tbinom{n+4}{1} & +K_{4}\tbinom{n+4}{0}\\ & \vdots\\ 1 & = & K_{1}\tbinom{n+j}{j-1} & +K_{2}\tbinom{n+j}{j-2} & +K_{3}\tbinom{n+j}{j-3} & +K_{4}\tbinom{n+j}{j-4} & +\cdots & +K_{j-2}\tbinom{n+j}{2} & +K_{j-1}\tbinom{n+j}{1} & +K_{j}\tbinom{n+j}{0} \end{array}

That is, the convolution

$$1=\sum_{i=1}^{j}K_{i}\binom{n+j}{j-i}$$

or said otherwise, if we consider the sequence of coefficients, $K_{1},K_{2},K_{3},\ldots$ the j th term is given by the recurrence

$$K_{j}=1-\sum_{i=1}^{j-1}K_{i}\binom{n+j}{j-i}$$

A direct calculation gives the following solutions

\begin{array}{cccc} K_{1}= & +1 & = & +1\\ K_{2}= & -{n+1 \choose 1} & = & -\left({n+1 \choose 1}\right)\\ K_{3}= & +{n+2 \choose 2} & = & +\left({n+1 \choose 2}\right)\\ K_{4}= & -{n+3 \choose 3} & = & -\left({n+1 \choose 3}\right)\\ K_{5}= & +{n+4 \choose 4} & = & +\left({n+1 \choose 4}\right)\\ \vdots & \vdots & & \vdots\\ K_{j}= & (-1)^{j-1}{n+j-1 \choose j-1} & = & (-1)^{j-1}\left({n+1 \choose j-1}\right) \end{array}

where ${n \choose i}=\frac{n(n-1)\cdots(n-i+1)}{i!}$ and $\left({N \choose i}\right)=\frac{n(n+1)\cdots(n+i-1)}{i!}$

However, this proves nothing.

Is it possible to derive a solution from the initial recurrence (convolution)?

• Yes, use induction. – Zack Wolske Jul 21 '14 at 17:30
• @Zack Wolske, I think that the fact that this is a recurrence of degree as high as the position of the coefficient doesn't make induction such a straightaway procedure: (1)The base of induction is ok (2) Suppose it is correct for an arbitrary value $K_{j}$ , then $$K_{j+1}=1-\sum_{i=1}^{j}(-1)^{i-1}{n+i-1 \choose i-1}\binom{n+j+1}{j+1-i}$$ at this point I dont see an useful analytic simplification, unless this is a known identity which gives back $K_{j+1}=(-1)^{j}{n+j \choose j}$ . Is it? Am I missing something? – josep Jul 21 '14 at 18:53
• Maple 18 confirms this identity. – Robert Israel Jul 21 '14 at 20:24
• The identity is just a special case of Vandermonde's theorem: \begin{align*}\sum_{i=1}^{j+1} (-1)^{i-1}\binom{n+i-1}{i-1}\binom{n+j+1}{j+1-i} & = \sum_{i=1}^{j+1} \binom{-n-1}{i-1}\binom{n+j+1}{j+1-i}\\ & = \binom{j}{j}=1. \end{align*} – Ira Gessel Jul 21 '14 at 23:40