2
$\begingroup$

This is example 3 from Concrete Mathematics (Section 5.2 p.177 in 1995 edition). Although the proof is given in the book (based on a recurrent expression), I were trying to find an alternative solution, noticing that half of the terms are 0 (denote for simplicity $\frac{m}{2}=s$):

$ \sum_{k=0}^{m} \binom{m-k}{k} (-1)^k = \sum_{k=0}^{s}\binom{s+k}{s-k}(-1)^{s-k} $

I think it would be good to absorb the $(-1)^k$ term in the binomial coefficient but can't think of much else. Wolfram Alpha doesn't give closed expression for either this or the one in the book

  • 0
    what is $n$? In he textbook it is solved using a recurrence2012-03-21

1 Answers 1

6

For a nice proof, see Arthur T. Benjamin and Jennifer J. Quinn: Proofs that Really Count, Identity 172, pp. 85-86.

Sketch of the proof:

Clearly, $\binom{m-k}k$ counts the number of ways that you can tile a $1×m$ board with $1×2$ dominoes (denoted by $d$) and $1×1$ squares (denoted by $s$) such that the number of dominoes is $k$ (and the number of squares is $m-2k$).

Let $\mathcal E$ denote the set of $m$-tilings with an even number of dominoes, let $\mathcal O$ denote the set of $m$-tilings with an odd number of dominoes.

With these notations, we have to calculate $|\mathcal E|-|\mathcal O|$. The answer is $0$ or $\pm1$, depending on the remainder of $m$ modulo $6$ (see sigma.z.1980's answer for the details). As a proof, we will give a(n almost) bijection between $\mathcal E$ and $\mathcal O$.

Since I don't want to draw figures, I encode tilings in a sequence (from left to right), for example $sdd$ means a square followed by two dominoes. For a tiling (sequence) $S$, I denote the concatenation $S\dots S$ ($t$ times) by $S^t$, and let $S^0$ be the empty sequence. The size of a domino is $2$, the size of a square is $1$, and the size of a sequence is the sum of the sizes of its elements.

With these notations, every tiling $S$ can be uniquely written as $S=(sd)^tR$ for some $t\in\Bbb N_0$, where $R$ is a tiling such that it doesn't start with $sd$. If the size of $R$ is at least $2$, then $R$ either starts with $d$ or with $ss$. If it starts with $d$, we replace this $d$ with $ss$; if it starts with $ss$, we replace this $ss$ with $d$. Note that we defined an involution $\phi$ on the set of $m$-tilings here and $\phi$ changes the parity of the number of dominoes, so we found the required correspondence between $\mathcal E$ and $\mathcal O$.

If $m$ has the form $3l+2$, then $\phi(S)$ is defined for all tilings $S$, thus $|\mathcal E|-|\mathcal O|=0$. If $m$ has the form $6l+1$, then $\phi(S)$ is not defined for $S=(sd)^{2l}s$ (which is in $\mathcal E$), and it is defined everywhere else, thus $|\mathcal E|-|\mathcal O|=1$. The rest of the cases are analogous.

  • 0
    I added the sketch of the proof. I hope I was clear, English is not my native language.2012-05-11