2
$\begingroup$

We use Iverson symbol ( [expr] is $1$ when expr is true else $0$), and $n\%6$ for $n$ modulo $6$. .

For any $n >= 2 $.

Let $ F(n) := \sum_{j>=1} (-1)^j {\binom {n-j-2} j } $

Prove that $F(n) = [n\%6 \in \{0,5\}] - [n\%6 \in \{2,3\}]$

In other words:

IF $n$ modulo $6$ is $0$ or $5$ then $F(n) = 1$

IF $n$ modulo $6$ is $2$ or $3$ then $F(n) =-1$

IF $n$ modulo $6$ is $1$ or $4$ then $F(n) =0$

It is true up to $n=15$ by hand, $40$ would be safe

Yet to what kind of identities does this belong? .And how to prove this?

Can we replace $-2$ by another constant and still have the same behaviour ( finite set of value with periodic recurrence.

Note : The motivation is to calculate

$ F(n) = \sum (-1)^k[a_1a_2a_3 \dots a_k=2^n] $. Where any $a_i$ is >= 3.

$\endgroup$
4
  • $\begingroup$ generating functions? $\endgroup$ Aug 18, 2018 at 22:26
  • 2
    $\begingroup$ This is essentially Corollary 7.63 in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, Version of 26 April 2018. (Well, my sum begins at $j = 0$, not at $j = 1$, and I use $n$ instead of $n-2$, but this boils down to subtracting a $1$ and substituting $n-2$ for $n$.) It's a fairly known result. $\endgroup$ Aug 18, 2018 at 22:33
  • 1
    $\begingroup$ Corollary 7.63, not Section 7.63. The corollary is on page 507, and relies on pages 500--507. $\endgroup$ Aug 19, 2018 at 1:08
  • $\begingroup$ OK thank you so much, this is much better with reference your page 120 and then to LeeSchi cluster algebra ... . I saw you are not yet an aficionados of Iverson Bracket, please check the one line note added at the end of the question which I hope will convince you of its many virtues. $\endgroup$ Aug 19, 2018 at 13:48

1 Answer 1

1
$\begingroup$

Working with the following sum

$$\sum_{q=0}^n (-1)^q {n-q\choose q}$$

we have

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

Now we get zero contribution when $2q\gt n$ hence we may write

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

This is

$$\mathrm{Res}_{z=0} \frac{1}{z^{n+1}} (1+z)^{n+1} \frac{1}{1+z+z^2}.$$

With the substitution $z/(1+z)=w$ or $z=w/(1-w)$ we have $dz = 1/(1-w)^2 \; dw$ and we obtain

$$\mathrm{Res}_{w=0} \frac{1}{w^{n+1}} \frac{1}{1+w/(1-w)+w^2/(1-w)^2} \frac{1}{(1-w)^2} \\ = \mathrm{Res}_{w=0} \frac{1}{w^{n+1}} \frac{1}{(1-w)^2+w(1-w)+w^2} \\ = \mathrm{Res}_{w=0} \frac{1}{w^{n+1}} \frac{1}{1-w+w^2} = [w^n] \frac{1}{1-w+w^2}.$$

Starting from

$$G(w) = \frac{1}{1-w+w^2}$$

we have $$(1-w+w^2) G(w) = 1$$

so that

$$[w^0] (1-w+w^2) G(w) = G_0 = [w^0] 1 = 1$$

and furthermore

$$[w^1] (1-w+w^2) G(w) = G_1-G_0 = [w^1] 1 = 0$$

This establishes the initial values $G_0=1$ and $G_1=1.$

Moreover for $n\ge 2$ we find

$$[w^n] (1-w+w^2) G(w) = G_n - G_{n-1} + G_{n-2} = [w^n] 1 = 0$$

producing the recurrence

$$G_n = G_{n-1} - G_{n-2}.$$

This means $G_n$ only depends on the preceding two values. Starting from $1,1$ we obtain by applying the recurrence

$$1,1,0,-1,-1,0,1,1,\ldots$$

We have reached the period (intial pair appears), thus proving the claim.

We may also compute the generating function by snake oil method. Start with

$$G(w) = \sum_{n\ge 0} w^n \sum_{q=0}^n (-1)^q {n-q\choose q} = \sum_{q\ge 0} (-1)^q \sum_{n\ge q} w^n {n-q\choose q} \\ = \sum_{q\ge 0} (-1)^q w^q \sum_{n\ge 0} w^n {n\choose q} = \sum_{q\ge 0} (-1)^q w^q \sum_{n\ge q} w^n {n\choose q} \\ = \sum_{q\ge 0} (-1)^q w^{2q} \sum_{n\ge 0} w^n {n+q\choose q} = \sum_{q\ge 0} (-1)^q w^{2q} \frac{1}{(1-w)^{q+1}} \\ = \frac{1}{1-w} \frac{1}{1+w^2/(1-w)} = \frac{1}{1-w+w^2}.$$

$\endgroup$
1
  • $\begingroup$ Very good , the snake oil version is pretty clear. Yet the reason for a period is not so clear. Say if we have say $n-\lambda q$ instead of $n-q$ in the binomial do we have a period? $\endgroup$ Aug 20, 2018 at 21:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .