2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – IV_ Jan 30 '16 at 16:11
  • $\begingroup$ 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}$. $\endgroup$ – IV_ Jan 30 '16 at 16:12
  • $\begingroup$ 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? $\endgroup$ – IV_ Jan 30 '16 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.