Find the difference between the greatest and smallest among $S(n,k,5)$ for $k=0,1,2,3,4$.

Question

$$S(n,k,m) \stackrel{\text {def}}{=} \sum_{r=0}^{\left\lfloor\frac {n-k}{m}\right\rfloor}\binom{n}{k+rm}$$

Find the difference between the greatest and smallest among $S(n,k,5)$ for $k=0,1,2,3,4$.

I observed that it's a Fibonacci sequence that follows. The n$^\text {th}$difference is basically the n-1$^\text {th}$ Fibo term. But that's an observation after plotting some values and then the rigor comes from using induction.

But I observed that it can be done using the fifth roots of unity as well (perhaps?). How to proceed with that?

Let $1,\omega, \omega^2, \omega^3, \omega^4$ be the roots, where $\omega^k=e^\frac {2k\pi i}{5}$. I can then filter out by putting the roots and multiplying $(1+x)^n$ with $1,x,x^2,x^3,x^4$ for each of $1,\omega^4, \cdots, \omega$ respectively. And thus we get $S(n,k,5)$ for each of the mentioned values of $k$. How to proceed?

Answer 1

One has $$\sum_{k=0}^4 S(n,k,5)\omega^{kr}=\sum_{k=0}^n\binom{n}{k} \omega^{kr}=(1+\omega^r)^{n}$$ for integers $r$. For a fixed integer $s$ one has $$\sum_{r=0}^4\omega^{-rs}\sum_{k=0}^4 S(n,k,5)\omega^{kr} =\sum_{r=0}^4\omega^{-rs}(1+\omega^r)^{n}$$ equivalently $$5S(n,s,5)=\sum_{r=0}^4\omega^{-rs}(1+\omega^r)^{n} =\sum_{r=0}^4\omega^{-r(s+2n)}(\omega^{2r}+\omega^{-2r})^{n}.$$ Now we have $\omega^{2r}+\omega^{-2r}=2$, $\frac12(-1+\sqrt5)$ or $\frac12(-1-\sqrt5)$ according to whether $r=0$, $r\in\{2,3\}$ or $r\in\{1,4\}$. Taking the difference of two $S(n,5)$ will give an expression of the form $A(\frac12(-1+\sqrt5))^n+B(\frac12(-1-\sqrt5))^n$ which can be written in terms of Fibonaccis using Binet's formula. Alas, I lack the patience to complete this task at the moment.