Simplify a sum of binomial

Question

Is it possible to have a closed form of the following sum: $$\sum_{i=0}^n\binom{n}{i}\binom{n+t-i}{n}$$

Answer 1

After some investigation, I have found that there is no way to have a closed form of this sum.

This sum is representing a Delannoy numbers (if $n$ smaller then $t$):

• number of global alignments of two sequences $n, t$ length
• number of points in $n$ dim space that are maximum $t$ from the center

You can only simplify it by rewriting in the following form:

$$ \sum_{i=0}^{n} \binom{n}{i} \binom{m}{i} 2^i$$

or as a recurrence formula:

$$D(n, t)=\begin{cases}1 &\text{if }t=0\text{ or }n=0\\D(n-1,t) + D(n-1,t-1) + D(n,t-1)&\text{otherwise}\end{cases}$$