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

  • $\begingroup$ Why not state the result, too? It's not. Mystery to you, why should it be a mystery to us? $\endgroup$ – Thomas Andrews Mar 20 '12 at 5:00
  • 1
    $\begingroup$ I am a little confused on what is what you ought to prove. $\endgroup$ – Daniel Montealegre Mar 20 '12 at 5:00
  • $\begingroup$ The textbook gives a closed form as a cycle, $1,1,0,-1,-1,0$ $\endgroup$ – sigma.z.1980 Mar 20 '12 at 5:40
  • $\begingroup$ It will be a good starting point to find the recurrence formula for the sum, as a sequence of $n$. $\endgroup$ – Sangchul Lee Mar 20 '12 at 7:12
  • $\begingroup$ what is $n$? In he textbook it is solved using a recurrence $\endgroup$ – sigma.z.1980 Mar 21 '12 at 3:53

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.

  • 1
    $\begingroup$ Could you maybe post a short summary for those of us without a copy of the book? $\endgroup$ – J. M. is a poor mathematician May 11 '12 at 20:05
  • $\begingroup$ I added the sketch of the proof. I hope I was clear, English is not my native language. $\endgroup$ – Gábor V. Nagy May 11 '12 at 22:50

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.