# Simplifying my sum which contains binomials

While dealing with compositions (ordered partitions) of integers, I found the following formula for the shifted $m$-generalized Fibonacci numbers (Wikipedia: Generalizations of Fibonacci numbers): $$F(m;n+m-1)=\sum_{k=0}^{n}\sum_{i=0}^{k}(-1)^{i}\binom{k}{i}\binom{n-im-1}{k-1},$$ where $$\binom{n}{k}=\begin{cases}\frac{n!}{k!(n-k)!} & 0\leq k \leq n\\0 & otherwise\end{cases}.$$ Is it possible to simplify this formula to a formula with only one sum sign or with only one binomial?

I already found that, for $m=2$, we have the shifted Fibonacci numbers: $$F(2;n+1)=\sum_{k=0}^{n}\sum_{i=0}^{k}(-1)^{i}\binom{k}{i}\binom{n-2i-1}{k-1}=\sum_{k=0}^{n}\binom{n-k}{k}.$$ Is such a nice short formula possible for arbitrary $m\geq 2$?

Suppose we seek to evaluate the following sum (with a condition on the binomial coefficient)

$$G(n,m) = \sum_{k=0}^n \sum_{q=0}^k (-1)^q {k\choose q} {n-1-qm\choose k-1}.$$

Now when $n-1-qm \lt 0$ we usually get a non-zero value for the binomial coefficient but this is not wanted here. Therefore we have

$$G(n,m) = \sum_{k=0}^n \sum_{q=0}^{\lfloor (n-k)/m \rfloor} (-1)^q {k\choose q} {n-1-qm\choose k-1}.$$

If we have lost any values for $q$ above $\lfloor (n-k)/m \rfloor$ these would render the second binomial coefficient zero. If we have added in any values for $q$ above $k$ the first binomial coefficient is zero there.

Now with the integral

$${n-1-qm\choose k-1} = {n-1-qm\choose n-k-qm} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1-qm}}{z^{n-k-qm+1}} \; dz$$

we get range control because the pole vanishes when $q\gt (n-k)/m$ and we may extend $q$ to infinity.

We thus obtain for the inner sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z^{n-k+1}} \sum_{q\ge 0} (-1)^q {k\choose q} \frac{z^{qm}}{(1+z)^{qm}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z^{n-k+1}} \left(1-\frac{z^m}{(1+z)^m}\right)^k \; dz$$

This yields for the outer sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z^{n+1}} \left(1-z\left(1-\frac{z^m}{(1+z)^m}\right)\right)^{-1} \\ \times \left(1 - z^{n+1} \left(1-\frac{z^m}{(1+z)^m}\right)^{n+1}\right) \; dz$$

which is $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+m-1}}{z^{n+1}} \left((1-z)(1+z)^m + z^{m+1}\right)^{-1} \\ \times \left(1 - z^{n+1} \left(1-\frac{z^m}{(1+z)^m}\right)^{n+1}\right) \; dz$$

Extracting the second component from the difference we get

$$-\frac{1}{2\pi i} \int_{|z|=\epsilon} (1+z)^{n+m-1} \left((1-z)(1+z)^m + z^{m+1}\right)^{-1} \left(1-\frac{z^m}{(1+z)^m}\right)^{n+1} \; dz$$

The pole at zero has vanished. We now have non-zero poles at $z=-1$ and from the inverted term. These depend on $m$ and we can certainly choose $\epsilon$ small enough so that none of them are inside the contour. Therefore this term does not contribute, leaving only

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+m-1}}{z^{n+1}} \frac{1}{(1-z)(1+z)^m + z^{m+1}} \; dz.$$

The generating function $f(w)$ of these numbers is thus given by

$$f(w) = \sum_{n\ge 0} w^n \sum_{q=0}^n {n+m-1\choose n-q} [z^q] \frac{1}{(1-z)(1+z)^m + z^{m+1}}.$$

This is

$$\sum_{q\ge 0} [z^q] \frac{1}{(1-z)(1+z)^m + z^{m+1}} \sum_{n\ge q} w^n {n+m-1\choose n-q} \\ = \sum_{q\ge 0} w^q [z^q] \frac{1}{(1-z)(1+z)^m + z^{m+1}} \sum_{n\ge 0} w^n {n+m-1 + q\choose n} \\ = \frac{1}{(1-w)^m} \sum_{q\ge 0} \frac{w^q}{(1-w)^q} [z^q] \frac{1}{(1-z)(1+z)^m + z^{m+1}}.$$

What we have here is an annihilated coefficient extractor that simplifies to

$$f(w) = \frac{1}{(1-w)^m} \frac{1}{(1-w/(1-w))(1+w/(1-w))^m + (w/(1-w))^{m+1}} \\ = \frac{1}{(1-w)^m} \frac{1}{(1-2w)/(1-w)/(1-w)^m + w^{m+1}/(1-w)^{m+1}} \\ = \frac{1-w}{1- 2 w + w^{m+1}}.$$

Now observe that $$1-2w+w^{m+1} = (1-w) (1-w-w^2-\cdots- w^{m-1} - w^m)$$

so we finally have

$$f(w) = \left(1-\sum_{q=1}^m w^q\right)^{-1} = \frac{1}{1-w-w^2-\cdots-w^m}.$$

We see that by the basic theory of linear recurrences what we have here is a Fibonacci, Tribonacci, Tetranacci etc. recurrence. The question is what are the initial values.

Observe however that $[w^0] f(w) = 1$ and for $1\le q\le m$ we have $$[w^q] \frac{1-w}{1-2w+w^{m+1}} = [w^q] \frac{1}{1-2w+w^{m+1}} - [w^{q-1}] \frac{1}{1-2w+w^{m+1}}.$$

But $$\frac{1}{1-2w+w^{m+1}} = \frac{1}{1-2w(1-w^{m}/2)} = \sum_{n\ge 0} 2^n w^n (1-w^m/2)^n$$

With the condition on $q$ and $n\ge 1$ only the constant term from the term $(1-w^m/2)^n$ contributes because the degree would be more than $m$ otherwise. This produces just one matching term with coefficient $2^q.$

This yields for $f(w)$ $$[w^q] f(w) = 2^{q} - 2^{q-1} = 2^{q-1}.$$

Therefore we get for the intial terms starting at $q=0$ $$1, 1, 2, 4, 8, 16, \ldots, 2^{m-1} \quad\text{with recurrence}\quad f_n = \sum_{q=1}^m f_{n-q}.$$

This recurrence also shows (by subtraction) that the sequence may be produced starting from $m-1$ zero terms followed by one.

The OEIS has the Fibonacci numbers, OEIS A000045 $$1, 2, 3, 5, 8, 13, 21, 34, 55, 89,\ldots$$

and the Tribonacci numbers, OEIS A000073 $$1, 2, 4, 7, 13, 24, 44, 81, 149, 274,\ldots$$

and the Tetranacci numbers, OEIS A000078 $$1, 2, 4, 8, 15, 29, 56, 108, 208, 401,\ldots$$

and more.

There are several more examples of the technique of annihilated coefficient extractors at this MSE link I and at this MSE link II and also here at this MSE link III.

• I asked for simplifying the expression $\sum_{k=0}^{n}\sum_{i=0}^{k}(-1)^{i}\binom{k}{i}\binom{n-im-1}{k-1}$ to an expression with only one sum sign or only one binomial. Using the Chu-Vandermonde identity, it is possible to include the term $(-1)^i$ in one of the two binomials. But I personally cannot come further here. – IV_ Jan 30 '16 at 16:11
• I used now the already previously well-known generating function and took your form of it: $\frac{1-w}{1-2w+w^{m+1}}=\left(\sum_{n=0}^{\infty}2^{n}w^{n}\left(1-\frac{w^{m}}{2}\right)^{n}\right)-\left(\sum_{n=0}^{\infty}2^{n}w^{n}w\left(1-\frac{w^{m}}{2}\right)^{n}\right)$. $\left(a\right)_{n}$ be the Pochhammer symbol. So I get $\sum_{k=0}^{n}\sum_{i=0}^{k}(-1)^{i}\binom{k}{i}\binom{n-im-1}{k-1}=\sum_{i=0}^{\left\lfloor\frac{n-1}{m}\right\rfloor}\frac{2^{n-(m+1)i-1}}{i!}((m-1)i-n)(mi-n+1)_{i-1}$. – IV_ Jan 30 '16 at 16:12
• Is it possible to prove this identity on a simpler way? Is it possible to simplify this expression further? Is this closed-form formula for the Fibonacci numbers of order m already known in the literature? – IV_ Jan 30 '16 at 16:13