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


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.


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.