Solving a floored input linear recurrence relation

Question

Need help solving:

$$T(n) = T(n-1) + \binom{n-1}{\lfloor\frac{n-1}{2}\rfloor + 1}$$

for $n \geq 3$ and $T(1) = 1$, $T(2) = 2$

I believe the answer is $T(n) = \binom{n}{\lfloor\frac{n}{2}\rfloor}$, but do not know how to show this algebraically.

Answer 1

We unroll the recursion to get

$$T(n) = 1+ \sum_{k=0}^{n-1} {k\choose \lfloor k/2\rfloor + 1}.$$

Induction is the method of choice here. The claim $T(n) = {n\choose \lfloor n/2\rfloor}$ holds for $n=1$ by inspection. Supposing it holds for $n-1$ we get for $T(n):$

$${n-1\choose \lfloor (n-1)/2\rfloor} + {n-1\choose \lfloor (n-1)/2\rfloor + 1} = {n \choose \lfloor (n-1)/2\rfloor + 1}.$$

Now when $n=2q$ this is

$${2q\choose q-1+1} = {2q\choose q} = {n\choose \lfloor n/2 \rfloor}.$$

On the other hand when $n=2q+1$ it becomes

$${2q+1\choose q+1} = {2q+1\choose q} = {n\choose \lfloor n/2 \rfloor}.$$

This concludes the proof by induction. We present an additional proof using formal power series, by way of enrichment.

Starting from the closed form we have $$1 + \sum_{k=0}^{\lfloor (n-1)/2\rfloor} {2k\choose k + 1} + \sum_{k=0}^{\lfloor n/2\rfloor-1} {2k+1\choose k + 1}.$$

Evaluating the first sum we obtain

$$\sum_{k=0}^m {2k\choose k + 1} = \sum_{k=1}^m {2k\choose k - 1} = \sum_{k=0}^{m-1} {2m -2k \choose m-k - 1} = \sum_{k=0}^{m-1} [z^{m-1-k}] (1+z)^{2m-2k} \\ = [z^{m-1}] (1+z)^{2m} \sum_{k=0}^{m-1} z^k (1+z)^{-2k} = [z^{m-1}] (1+z)^{2m} \sum_{k\ge 0} z^k (1+z)^{-2k} \\ = [z^{m-1}] (1+z)^{2m} \frac{1}{1-z/(1+z)^2} \\ = [z^{m-1}] (1+z)^{2m+2} \frac{1}{1+z+z^2}.$$

By a very similar calculation we find

$$\sum_{k=0}^m {2k+1\choose k + 1} = \sum_{k=0}^m {2m -2k +1 \choose m-k + 1} = \sum_{k=0}^m [z^{m+1-k}] (1+z)^{2m-2k+1} \\ = [z^{m+1}] (1+z)^{2m+1} \sum_{k=0}^m z^k (1+z)^{-2k} = -1 + [z^{m+1}] (1+z)^{2m+1} \sum_{k=0}^{m+1} z^k (1+z)^{-2k} \\ = -1 + [z^{m+1}] (1+z)^{2m+1} \sum_{k\ge 0} z^k (1+z)^{-2k} \\ = -1 + [z^{m+1}] (1+z)^{2m+1} \frac{1}{1-z/(1+z)^2} \\ = -1 + [z^{m+1}] (1+z)^{2m+3} \frac{1}{1+z+z^2}.$$

Collecting the three pieces from the closed form of $T(n)$ we have cancelation of the minus one term. There are two cases. When $n=2q$ we get for the upper limits $q-1$ and $q-1$ for a contribution of

$$[z^{q-2}] (1+z)^{2q} \frac{1}{1+z+z^2} + [z^q] (1+z)^{2q+1} \frac{1}{1+z+z^2} \\ = [z^q] (1+z)^{2q} \frac{z^2}{1+z+z^2} + [z^q] (1+z)^{2q} \frac{1+z}{1+z+z^2} \\ = [z^q] (1+z)^{2q} = {2q\choose q}.$$

This is the desired value. When $n=2q+1$ the upper limits become $q$ and $q-1$ and we obtain

$$[z^{q-1}] (1+z)^{2q+2} \frac{1}{1+z+z^2} + [z^q] (1+z)^{2q+1} \frac{1}{1+z+z^2} \\ = [z^q] (1+z)^{2q+1} \frac{z+z^2}{1+z+z^2} + [z^q] (1+z)^{2q+1} \frac{1}{1+z+z^2} \\ = [z^q] (1+z)^{2q+1} = {2q+1\choose q}.$$

We have shown the closed form

$$\bbox[5px,border:2px solid #00A000]{ {n\choose \lfloor n/2 \rfloor}.}$$

This may illustrate certain aspects of the formal power series technique.