8
$\begingroup$

Consider the combinatorial identity by Gould, Table III, page 25, equation (6.13):

$$\sum_{k=0}^{[\frac{n}{r}]}{n \choose rk}=\frac{2^n}{r}\sum_{j=1}^{r}\left(\cos{\frac{\pi j}{r}}\right)^n\cos{\frac{n \pi j}{r}} \tag{6.13}$$

and replace $n$ with $rn$ to get:

$$\sum_{k=0}^{n}{rn \choose rk}=\frac{2^{rn}}{r}\sum_{j=1}^{r}\left(\cos{\frac{\pi j}{r}}\right)^{rn}\cos{n \pi j} \tag{6.13M}$$

For cases $r=3$ and $r=4$ it is shown that this formula simplifies to (6.15) and (6.17) respectively, for example:

$$\sum_{k=0}^{n}{3n \choose 3k}=\frac{1}{3}\left(2^{3n}+2(-1)^n\right)\tag{6.15}$$

Do you think it is possible to generalize (6.15) and (6.17) for any natural $r$ (or $r$ of some form), obtaining an expression with all integers, and if yes how?

Note that this question is related to this other question.

$\endgroup$
4
  • 1
    $\begingroup$ the cosine makes it difficult to evaluate when your $r$ is not $2,3,4$ or $6$ as evaluation of the cosine function is simple at "nice" angles. $\endgroup$
    – Lalaloopsy
    Aug 22, 2018 at 21:28
  • $\begingroup$ Some observations from data: It seems that for fixed $r$ it is always possible to write $a_n=\sum_{k=0}^{n}\binom{rn}{rk}$ as a recurrence of order $\lceil r/2\rceil$ with integer coefficients. For example for $r=3$ we have $a_n=7a_{n-1}+8a_{n-2}$, for $r=4$ it is $a_n=12a_{n-1}+64a_{n-2}$, etc. Coefficients at $a_{n-1}$ in such recurrence seem to be $2^{r-2}+r-1$. Being able to spot patterns in other coefficients, one might write recurrence formula for $a_{n}$ in integers only.... $\endgroup$
    – Sil
    Aug 22, 2018 at 22:39
  • $\begingroup$ Consult OEIS A070782 where already square roots appear in the closed form for $\sum_{k=0}^n {5n\choose 5k}$. We may cancel these similar to Fibonacci numbers. This yields a sum and not a closed form, however. $\endgroup$
    – Marko Riedel
    Aug 23, 2018 at 13:03
  • $\begingroup$ Identity (6.11) in Gould is easier to work with than (6.13). For example, one can use it in a finite field to show divisibility by p in the linked question. It can be also used to write the sequence in @Sil's comment as a linear recurrence with integer coefficients. $\endgroup$
    – Peter McNamara
    Aug 24, 2018 at 4:28

0

Reset to default

You must log in to answer this question.