Problem 2161

Define $S(n,r) := \frac{n+1-2r}{n+1-r} \binom{n}{r}$, for all pairs $r, n$ with $-1 \le r$ and $2r \le n+1$. In particular $S(n,r) = 0$ if $r = -1$ or if $2r = n+1$. Note that $S(1,0) = 1$. We prove that if $n \ge 2$ and $0 \le r \le n/2$ then
$$S(n,r) = S(n-1, r-1) + S(n-1, r)$$
The first statement will then follow by induction on $n$. For $n \ge 2$ we have
$$\begin{align*} & S(n-1, r-1) + S(n-1, r) \\ &= \frac{(n+2-2r)}{(n+1-r)} \frac{(n-1)!}{(r-1)!(n-r)!} + \frac{(n-2r)}{(n-r)} \frac{(n-1)!}{r!(n-1-r)!} \\ &= \frac{[r(n+2-2r) + (n-2r)(n+1-r)](n-1)!}{(n+1-r)r!(n-r)!} \\ &= \frac{[(n+1-2r)n](n-1)!}{(n+1-r)r!(n-r)!} \\ &= S(n,r) \end{align*}$$

The final statement is that $\sum_{r=0}^{\lfloor n/2 \rfloor} S(n,r) < 2^{n-2}$, for $n \ge 9$. The base case here is $n=9$, where the values of $S(9,r)$ for $r=0,1,2,3,4$ are 1, 8, 27, 48, 42, respectively. These sum to 126, which is less than $2^{9-2} = 128$. The inductive step follows from the fact that
$$\sum_{r=0}^{\lfloor n/2 \rfloor} S(n,r) = \sum_{r=0}^{\lfloor n/2 \rfloor} [S(n-1,r) + S(n-1,r-1)] \\ \le 2 \sum_{r=0}^{\lfloor(n-1)/2\rfloor} S(n-1,r) < 2 \times 2^{\lfloor(n-1)/2\rfloor} = 2^{n-2}$$
(each $S(n-1, r-1)$ with $r < n/2$ contributes twice to the sum: to $S(n, r-1)$ and $S(n, r+1)$. When $r = n/2$, $S(n-1, n/2-1)$ contributes only once: to $S(n, n/2-1)$.)

a.

Then
$$\begin{align*} S(n,r) &= \frac{n+1-r}{n+1-r} \binom{n}{r} - \frac{r}{n+1-r} \binom{n}{r} \\ &= \binom{n}{r} - \frac{rn!}{r!(n+1-r)(n-r)!} \\ &= \binom{n}{r} - \frac{n!}{(r-1)!(n+1-r)!} \\ &= \binom{n}{r} - \binom{n}{r-1}, \end{align*}$$
a difference between two successive binomial coefficients. Hence $S(n,r)$ is an integer, which is nonnegative if $2r \le n+1$. Alternatively,
$$\begin{align*} S(n,r) &= \frac{n+1}{n+1-r} \binom{n}{r} - 2 \frac{r}{n+1-r} \binom{n}{r} \\ &= \frac{(n+1)n!}{r!(n+1-r)(n-r)!} - 2 \frac{rn!}{r!(n+1-r)(n-r)!} \\ &= \frac{(n+1)!}{r!(n+1-r)!} - 2 \frac{n!}{(r-1)!(n-(r-1))!} \\ &= \binom{n+1}{r} - 2 \binom{n}{r-1}, \end{align*}$$
a difference between multiples of two binomial coefficients.

b.

Using the first representation of $S(n, r)$, we see that
$$\begin{aligned} \sum_{r=0}^{\lfloor n/2 \rfloor} \frac{n+1-2r}{n+1-r} \binom{n}{r} &= \sum_{r=0}^{\lfloor n/2 \rfloor} S(n, r) \\ &= \sum_{r=0}^{\lfloor n/2 \rfloor} \left[ \binom{n}{r} - \binom{n}{r-1} \right] \\ &= \binom{n}{\lfloor n/2 \rfloor}. \end{aligned}$$
It must now be confirmed that
$$\binom{n}{\lfloor n/2 \rfloor} < 2^{n-2}, \forall n \ge 9.$$
We'll use induction to establish this considering separately when $n$ is even and when $n$ is odd.

Case (i): Suppose $n = 2m$, $m \ge 5$. Since
$$\binom{n}{\lfloor n/2 \rfloor} = \frac{(2m)!}{(m!)^2},$$
and
$$\binom{10}{5} = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 252 < 2^8 = 2^{10-2},$$
we can start the induction at $m = 5$. So, assuming that
$$\frac{(2m)!}{(m!)^2} < 2^{2m-2}, \forall m \ge 5,$$
we see that
$$\frac{(2(m+1))!}{((m+1)!)^2} = \frac{2(m+1)(2m+1)(2m)!}{(m+1)^2(m!)^2} < \frac{2m+1}{m+1} 2^{2m-1} < 2^{2m}.$$
Hence the inequality holds if $n$ is even.

Case (ii): Suppose $n = 2m + 1$, $m \ge 4$. Since
$$\binom{n}{\lfloor n/2 \rfloor} = \binom{2m+1}{m} = \frac{(2m+1)!}{m!(m+1)!},$$
and
$$\binom{9}{4} = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} = 126 < 2^7 = 2^{9-2},$$
we can start the induction at $m = 4$. So, assuming that
$$\frac{(2m+1)!}{m!(m+1)!} < 2^{2m-1}, \forall m \ge 4,$$
we see that
$$\frac{(2m+3)!}{(m+2)!(m+1)!} = \frac{(2m+3)(2m+2)}{(m+1)(m+2)} \frac{(2m+1)!}{m!(m+1)!} < \frac{2m+3}{m+2} 2^{2m} < 2^{2m+1}.$$
Hence the inequality holds if $n$ is odd.