Evaluate:$S_{n}=\binom{n}{0}-\binom{n-1}{1}+\binom{n-2}{n-3}-\binom{n-3}{n-6}+.......$

Question

If$$S_{n}=\binom{n}{0}-\binom{n-1}{1}+\binom{n-2}{n-3}-\binom{n-3}{n-6}+.......$$ Does $S_{n}$ have a closed form.

My Attempt

$$S_{n}=\binom{n}{0}-\binom{n-1}{n-2}+\binom{n-2}{2}-\binom{n-3}{3}+.......$$

$$S_{n}=\binom{n}{n}-\binom{n-1}{1}+\binom{n-2}{2}-\binom{n-3}{3}+.......$$

$=$coefficient of $x^n$ in $\left\{(1+x)^n-x^2(1+x)^{n-1}+x^4(1+x)^{n-2}-x^6(1+x)^{n-3}+....\right\}$

After this not able to proceed

Answer 1

If $S_{n} = \sum_{j\geq 0} (-1)^{j}\binom{n-j}{j}$, then \begin{align} S_{n+1} &= \sum_{j\geq 0} (-1)^{j} \binom{n+1-j}{j} \\ &= \sum_{j\geq 0} (-1)^{j} \left[\binom{n-j}{j} + \binom{n-j}{j-1}\right] \\ &= \sum_{j\geq 0} (-1)^{j} \binom{n-j}{j} - \sum_{j\geq 1} (-1)^{j-1}\binom{n-1-(j-1)}{j-1} \\ &= S_{n} - S_{n-1} \end{align} and $S_{1} = 1, S_{2} = 0$, so $S_{n}$ is $$ 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, 1, \dots $$ which is a periodic sequence.

Answer 2

Here is a combinatorial solution.

Consider tilings of an $n\times 1$ rectangle with squares and dominos. There are $\binom{n-k}{k}$ such tilings which use exactly $k$ dominos. Your sum counts all such tilings, where those with an even number of dominos are counted positively, and those with an odd number of dominos are counted negatively.

Let’s divide these tilings into pairs where one tiling in each pair is even and the other is odd. These pairs cancel themselves, so can be ignored. (This pairing is also known as a sign reversing involution).

• If the leftmost tile is a domino, pair it with the tiling formed by replacing this domino with two squares.

• If the leftmost two tiles are squares, pair it with tiling formed by replacing these two squares with a domino.

• Otherwise, the tiling begins with a square followed by a domino. Ignore these, and apply the same procedure to the remaining $n-3$ tiles. Repeat until a domino or pair of squares if found; if none are found, the tiling is not paired with anything.

This procedure will pair up all but at most one of the tilings; namely, a tiling which starts with a square and thereafter alternates between dominos and squares will be unpaired. Whether this exceptional tiling exists, and whether it is even or odd, depends on the remainder of $n$ modulo $6$.