# Combinatorial Interpretation of a Binomial Identity

The original post due to David Peterson is here.

How to establish the following Binomal identity combinatorially:

$$\displaystyle \sum\limits_{k = 0}^{[n/2]}\binom{n-k}{k}2^k = \frac{2^{n+1}+(-1)^n}{3} \tag{1}$$

Attempted tiling $n \times 1$ rectangle with dominoes ($2\times 1$) of two colors and squares ($1 \times 1$) of a single color. Fixing $k$ for te number of dominoes, we can count among the $n-k$ positions on the board which one is a dominoe and a square and color the dominoes in 2 ways in $\displaystyle \binom{n-k}{k}2^k$ ways.

As for the right side I am facing problems. Am I to interpret it as $\displaystyle \frac{2^{n+1}-(-1)^{n+1}}{2-(-1)} = \sum\limits_{k=0}^{n}2^k(-1)^{n-k}$ and argue with some I.E.P. or is it possible to argue by establishing a bijection among three partitions of $2^{n+1}+(-1)^n$ configurations ? I can't figure out which way.

Note: On the other hand we can argue combinatorially that L.H.S. of $(1)$ (dominoe coloring) satisfies a linear recursion which can be proved by induction or otherwise to be the R.H.S. (but I'm not looking for that either).

• Your tiling example is identical to the problem that motivated my original question (I was helping someone on another forum). It was: How many strings from $\{x,y,z,w\}$ of length $n$ are there if $y,z,w$ only occur in the string as $yz$ or $yw$. – David Peterson Dec 1 '14 at 5:32
• @DavidPeterson ah I see ! :-) – r9m Dec 1 '14 at 6:10

I used another combinatorial insight for the L.H.S. (denote it $f(n)$). I haven't proved the formula explicitely by bijection but I can show $f(n)=2^n-f(n-1)$. It may be the "unwanted" linear recursion but it is quite close to the formula $\sum_{k=0}^n 2^k(-1)^{n-k}$ although it is not directly I.E.P. (well I.E.P. also is not such obvious, is it?)
$n-k\choose k$ counts the number of paths from the point $[0,0]$ to the point $[n-2k, k]$ using (up/right)ward steps (its length is allways $n-k$). $2^k$ counts the number of paths of the length $k$ (with arbitrary endpoint). Composing these paths you get a path of the length $n$ passing through the point $[n-2k, k]$.
A path can't pass through different points of the form $[n-2k,k]$ so $f(n)$ counts such paths of the length $n$ which passes through any. Let's count the complement -- which paths does not pass any of such points? Exactly such that go to a point of the form $[n-2k-1,k]$ and then upwards to the point $[n-2k-1, k+1]$. Discarding this upward step we get a path of the length $n-1$ passing through a point of the form $[(n-1)-2k, k]$ i.e. an object counted by $f(n-1)$.
Edit: I realized that it actually describes a bijection between paths of the length $n, n-2, \ldots$ and paths of the length $n-1, n-3, \ldots$ with paths counted by $f(n)$. The algorithm is: Take a path of length $l$. If it passes a point of the form $[l-2k, k]$ insert an upward step here. Otherwise discard an upward step between points $[l-2k-1,k]$ and $[l-2k-1, k+1]$. The only exception is when you should extend a path of the length $n$ -- then leave it unchanged.