1
$\begingroup$

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)?

$\endgroup$
4
  • 1
    $\begingroup$ Yes, use induction. $\endgroup$ Jul 21, 2014 at 17:30
  • $\begingroup$ @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? $\endgroup$
    – josep
    Jul 21, 2014 at 18:53
  • $\begingroup$ Maple 18 confirms this identity. $\endgroup$ Jul 21, 2014 at 20:24
  • 5
    $\begingroup$ 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*} $\endgroup$
    – Ira Gessel
    Jul 21, 2014 at 23:40

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.