Compute $\sum\limits_{k+l=0}^{97}\binom{100}{k}\binom{100-k}{l}\binom{100-k-l}{97-k-l}$

Compute $$\sum\limits_{k+l=0}^{97}\binom{100}{k}\binom{100-k}{l}\binom{100-k-l}{97-k-l}$$

My Attempts

We already khow that $\quad k+l=0 \quad$ and $\quad l=-k \quad$ so we can say that this expression actually is $$\sum_{k+l}^{97}\dbinom{100}{k}\dbinom{100+l}{l}\dbinom{100}{97}$$ luckily we can factor out $\dbinom{100}{97}$ from the sum and $$\dbinom{100}{97}\left(\sum_{k+l=0}^{97}\dbinom{100}{k}\dbinom{100+l}{l}\right)$$ my problem is about calculating this sum, do we say that $k+l=0$ always?

Or do we say that oh Ok! $k+l=0$ and now its $k+l=1$ and now $k+l=2 \cdots$

Which one is true?

And if $k+l=0$ always then how come $k,l \in \mathbb{Z}^+$ and if they are not how can I use negative bases in binom?

• $l$ is not equal to $-k$. $k+l$ is the value that increases – MCCCS Sep 18 '17 at 15:19
• I see thanks:) Now how can I simplify this expression and how can I calculate it most importantly? – Deniz Tuna Yalçın Sep 18 '17 at 15:22
• @MCCCS I actually was wondering about that. So it's all pairs of values of $k,l \geq 0$ that add up to something less than $98$? – John Sep 18 '17 at 15:22
• @John Yep. So one can assume $k=0$ and solve the problem easier by just incrementing $l$. – MCCCS Sep 18 '17 at 15:27
• @MCCCS And the result of this wouldn't change if we keep one variable fixed like $k=0$ (fixed)? – Deniz Tuna Yalçın Sep 18 '17 at 15:29

You are counting the ways of how to paint an arbitrary number $k$ of $100$ balls red, an arbitrary number $l$ of the remaining $100-k$ balls blue, and $97-k-l$ of the remaining $100-k-l$ balls green.

In the end you have simply left $3$ balls uncoloured and assigned arbitrary colours from the three available colours to all other balls. Therefore $$\sum_{k+l=0}^{97}{100\choose k}{100-k\choose l}{100-k-l\choose 97-k-l}={100\choose 3}\cdot 3^{97}.$$

• This is one incredible solution, thank you:) – Deniz Tuna Yalçın Sep 18 '17 at 15:32

Hint:

Assume $k=0$ and increment $l$

$$\sum_{l=0}^{97}\dbinom{100}{0}\dbinom{100}{l}\dbinom{100-l}{97-l}$$

$$\sum_{l=0}^{97}\dbinom{100}{l}\dbinom{100-l}{97-l}$$

$$\sum_{l=0}^{97}\frac{100!}{l!(100-l!)}\dbinom{100-l}{97-l}$$

$$\sum_{l=0}^{97}\frac{100!}{l!(100-l!)}\frac{(100-l)!}{6(97-l)!}$$

$$\sum_{l=0}^{97}\frac{100!}{l!}\frac{1}{6(97-l)!}$$

$$\frac{100!}{6}\sum_{l=0}^{97}\frac{1}{(97-l)!l!}$$

• Hello @MCCCS It makes a lot of sense but I failed to find something like $3^x.\dbinom{100}{\text{something}}$ what did you get doing these calculations? – Deniz Tuna Yalçın Sep 19 '17 at 5:01
• @DenizTunaYalçın Yes, you're right, I got stuck at $\frac{100!}{6}\sum_{l=0}^{97}\frac{1}{(97-l)!l!}$ – MCCCS Sep 19 '17 at 15:20
• I think before assuming $k=0$ if we say $\dbinom{100}{k+l}\dbinom{k+l}{l}\dbinom{100}{3}$ for the existing expression this explains $\dbinom{100}{3}.\cdots$ however I still can't get a power of $3$. – Deniz Tuna Yalçın Sep 19 '17 at 15:24