Rigorous or not?

Question

I want to prove $$T(n,k)=\frac{n}{\left\lfloor\frac{n+k+1}{2}\right\rfloor}(T(n-1,k)+T(n-1,k-1))=\binom{n}{k}\binom{n-k}{\left\lfloor\frac{n-k}{2}\right\rfloor}$$ First we know only that $$T(n,k)=0, n<k$$ $$T(n,k)=0, n<0, k<0$$ $$T(0,0)=1$$ so obviously $$T(n,0)=\frac{n}{\left\lfloor\frac{n+1}{2}\right\rfloor}T(n-1,0)=\binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}$$ next we may notice (for $n\geqslant k$) $$T(n,k)=\frac{n}{\left\lfloor\frac{n+k+1}{2}\right\rfloor}(\frac{\left\lfloor\frac{n-k+1}{2}\right\rfloor}{n}T(n,k)+\frac{k}{n}T(n,k))$$ then $$T(n,k)=\frac{n}{k}T(n-1,k-1)=\binom{n}{k}T(n-k,0)=\binom{n}{k}\binom{n-k}{\left\lfloor\frac{n-k}{2}\right\rfloor}$$ which agrees with $$T(n,k)=\frac{n}{\left\lfloor\frac{n-k+1}{2}\right\rfloor}T(n-1,k)$$ Can we say that all steps looks clear? Is there another way to prove it?

Answer 1

I can see good ideas, but there are also some aspects which have to be considered to make this approach rigorous.

What is given/what is to prove?

The first section introduces a part of a recurrence relation equated with a binomial expression. The weak point here is, it is not clearly stated what is given and what is to prove.

Proposal:

Let $n,k$ be non-negative integer. Given a recurrence relation \begin{align*} T(n,k)&=\frac{n}{\left\lfloor\frac{n+k+1}{2}\right\rfloor}(T(n-1,k)+T(n-1,k-1))\qquad n,k\geq 1\\ T(0,0)&=1\\ T(n,0)&=0\qquad n\geq 1\\ T(0,k)&=0\qquad k\geq 1 \end{align*} the following is valid \begin{align*} T(n,k)=\binom{n}{k}\binom{n-k}{\left\lfloor\frac{n-k}{2}\right\rfloor}\qquad 0\leq k\leq n\tag{1} \end{align*}

Here we clearly state what is given, namely a recurrence relation, and what is to prove, namely the representation of $T(n,k)$ as product of binomial coefficients. Note, that a recurrence relation needs a specification of all initial conditions in order to be fully specified.

A step in the proof:

The derivation $T(n,k)=\frac{n}{k}T(n-1,k-1)$ and a possible connection with the representation $T(n,k)=\frac{n}{\left\lfloor\frac{n+k+1}{2}\right\rfloor}(\frac{\left\lfloor\frac{n-k+1}{2}\right\rfloor}{n}T(n,k)+\frac{k}{n}T(n,k))$ is not clear to me. This should be justified.

Answer 2

Although there is already a good answer, let me present a different approach.

We can better restate the problem as $$ \left\{ \matrix{ T(n,k) = 0\quad \left| {\;n < 0\; \vee \;k < 0} \right. \hfill \cr T(n,k) = \binom{n}{k} \binom{n-k}{\left\lfloor {{{n - k} \over 2}} \right\rfloor} = \hfill \cr = \left[ {0 = n} \right]\left[ {0 = k} \right] + \left[ {1 \le n} \right]{n \over {\left\lfloor {{{n + k + 1} \over 2}} \right\rfloor }} \left( {T(n - 1,k) + T(n - 1,k - 1)} \right) \hfill \cr} \right. $$ where $[condition]$ denotes the Iverson bracket

Let's recall some useful properties of the floor and ceil functions. We have that, for integer $m$ $$ \eqalign{ & m = \left\lfloor {{m \over 2}} \right\rfloor + \left\lceil {{m \over 2}} \right\rceil \cr & \left\lceil {{m \over 2}} \right\rceil = \left\lfloor {{{m + 1} \over 2}} \right\rfloor \cr} $$

Calling $B(n,k)$ the binomial expression, we can write it as $$ B(n,k) = \binom{n}{k} \binom{n-k}{\left\lfloor {{{n - k} \over 2}} \right\rfloor} = \left[ {0 \le k \le n} \right]{{n!} \over {k!}}{1 \over {\left\lfloor {{{n - k} \over 2}} \right\rfloor !\left\lceil {{{n - k} \over 2}} \right\rceil !}} $$

Then we have $$ \eqalign{ & {{B(n - 1,k)} \over {B(n,k)}} = \cr & = \left[ {0 \le k \le n - 1} \right]{{\left( {n - 1} \right)!k!\left\lfloor {{{n - k} \over 2}} \right\rfloor !\left\lceil {{{n - k} \over 2}} \right\rceil !} \over {k!\left\lfloor {{{n - 1 - k} \over 2}} \right\rfloor !\left\lceil {{{n - 1 - k} \over 2}} \right\rceil !n!}} = \cr & = \left[ {0 \le k \le n - 1} \right]{1 \over n}{{\left\lfloor {{{n + 1 - k} \over 2}} \right\rfloor !} \over {\left\lfloor {{{n - 1 - k} \over 2}} \right\rfloor !}} = \cr & = \left[ {0 \le k \le n - 1} \right]{1 \over n}\left\lfloor {{{n + 1 - k} \over 2}} \right\rfloor \cr} $$

and $$ \eqalign{ & {{B(n - 1,k - 1)} \over {B(n,k)}} = \cr & = \left[ {1 \le k \le n} \right]{{\left( {n - 1} \right)!k!\left\lfloor {{{n - k} \over 2}} \right\rfloor !\left\lceil {{{n - k} \over 2}} \right\rceil !} \over {\left( {k - 1} \right)!\left\lfloor {{{n - k} \over 2}} \right\rfloor !\left\lceil {{{n - k} \over 2}} \right\rceil !n!}} = \cr & = \left[ {1 \le k \le n} \right]{k \over n} \cr} $$

So we conclude that $$ \eqalign{ & {{B(n - 1,k) + B(n - 1,k - 1)} \over {B(n,k)}} = \cr & = \left[ {0 \le k \le n - 1} \right]{1 \over n}\left\lfloor {{{n + 1 - k} \over 2}} \right\rfloor + \left[ {1 \le k \le n} \right]{k \over n} = \cr & = \left[ {0 \le k} \right]\left[ {1 \le n} \right]\left[ {k\left( { \le n - 1} \right) \le n} \right]{1 \over n}\left\lfloor {{{n + 1 - k} \over 2}} \right\rfloor + \left[ {0 \le \left( {1 \le } \right)k} \right]\left[ {1 \le n} \right]\left[ {k \le n} \right]{k \over n} = \cr & = \left[ {0 \le k} \right]\left[ {1 \le n} \right]\left[ {k \le n} \right]{1 \over n}\left( {\left\lfloor {{{n + 1 - k} \over 2}} \right\rfloor + k} \right) = \cr & = \left[ {0 \le k} \right]\left[ {1 \le n} \right]\left[ {k \le n} \right]\;{{\left\lfloor {{{n + 1 + k} \over 2}} \right\rfloor } \over n} \cr} $$

and the thesis is demonstrated.