7
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – David Peterson Dec 1 '14 at 5:32
  • $\begingroup$ @DavidPeterson ah I see ! :-) $\endgroup$ – r9m Dec 1 '14 at 6:10
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is very nice ! Thank you ! :-) instead of up/right moves I was using two colors, essentially same recursion but this interpretation makes visualization of the bijective correspondence a lot easier !! :D $\endgroup$ – r9m Nov 30 '14 at 22:10

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.