Problems with combinatorial thinking.

Question

While I can solve the problems algebraically, I have trouble thinking of these problems in a combinatorial way, like: "Let's say we choose $ k$ people from a group of $n$ such that $r$ people satisfy the conditions..."

How should I approach such problems in that way? I'd appreciate any tips or hints.

1. Prove that $ \sum_{k=r}^{n} {n \choose k } {k \choose r } 2^k = {n \choose r } 2^r 3^{n-r} $, where $ n \ge r \ge 1 $ are natural numbers.

2. Describe "combinatoricly" $ \sum_{s=0}^{n} {n \choose s } {s \choose k-s } $ , where $ n, k$ are naturals.

Answer 1

For the first one, suppose there are $n$ players who appear for the team tryouts. You can shortlist $k$ players from these $n$ and then, make a starting lineup consisting of $r$ players. Meanwhile, any no. of players in the shortlist can also be given new equipment. This can be counted in precisely $\sum\limits_{k=r}^n \binom n r \binom k r 2^k$ ways.

Alternatively, to achieve the same effect, you can just choose the $r$ starters from the $n$ players in the tryouts, decide which players in the starting lineup get new equipment, and then, categorise the remaining players into three groups.

$1$. Not on the shortlist,

$2$. On the shortlist not given new equipment,

$3$. On the shortlist given new equipment.

This can be done in $\binom{n}{r}2^r3^{n-r}$ ways.

Therefore, these must be equal.

Answer 2

Since Umesh Shankar has already provided a brilliant answer to the first question, I will focus on the second one.
First note that $$\sum_{s=0}^{n} {n \choose s } {s \choose k-s } = \sum_{s = \lfloor (k+1)/2 \rfloor}^{\min(n,k)} {n \choose s } {s \choose k-s }$$ Suppose your team of $n$ players has won a tournament. You decide to give the best performers new boots (you can choose any no. of performers). But, let's say you had a budget of $\$10k$ which you had decided to spend fully. Since each pair of boots costs $\$10$, you still have $\$10(k-s)$, so you decide to give a treat to the best $k-s$ players from among the $s$, which costs $\$10$ per person.