0
$\begingroup$

We are given the expression: $$\binom{98}{30}+2\binom{97}{30}+3\binom{96}{30}+...+68\binom{31}{30}+69\binom{30}{30}=\binom{100}{q}$$

where $q$ is a positive integer $\leq 50$ and we need to find the value of $q$.

I tried evaluating the expression by writing it as a general term and trying to use summation but this presents a problem as it is not like other binomial based sums that I've calculated which were within bounds like $r=0$ to $n$.

The general term that I came up with was $$\sum_{i=1}^{69}i\binom{99-i}{30}$$

But this didn't strike me as anything impressive as I still couldn't figure out how to proceed because the series doesn't seem to simplify out to a form where I can use telescoping or other techniques.

Any help would be appreciated.

$\endgroup$
4
  • 4
    $\begingroup$ hint ${(1+x)}^{-31}$=1+$\binom{31}{1}$$x$+$\binom{32}{2}$ $x^2$ so on $\endgroup$ Aug 9, 2020 at 8:50
  • $\begingroup$ @HariRamakrishnanSudhakar shouldn't it be 1-x, or -1^n in RHS $\endgroup$ Aug 9, 2020 at 10:20
  • $\begingroup$ And i don't understand what's the relation of hint given by you $\endgroup$ Aug 9, 2020 at 10:25
  • 2
    $\begingroup$ @AnindyaPrithvi it should be -x, my mistake ! coming to your next question :this sum can be written as the coefficient of $x^{68}$ in exp. ${(1-x)}^{-31}$${(1-x)}^{-2}$ or coefficient of $x^{68}$ in ${(1-x)}^{-33}$ which is $\binom{100}{68}$ $\endgroup$ Aug 9, 2020 at 15:35

3 Answers 3

3
$\begingroup$

Let $[x^p]~f(x)$ mean the co-efficient of $x^{p}$ in $f(x)$.

$$S=\sum_{i=0}^{n} i {m-i \choose p} =[x^p] \sum_{i=0}^{n} i (1+x)^{m-i}$$ The above series is AGP, using its summation, we get $$S=[x^p]~(1+x)^{m-n}\left(\frac{-1-x+nx+(1+x)^n+x(1+x)^n}{x^2}\right)$$ $$\implies [x^{p+2}]~(1+x)^{m-n}(-1-x+nx+(1+x)^n+x(1+x)^n)$$ $$\implies S=-{m-n \choose p+2}+(n-1) {m-n \choose p+1}+{m \choose p+2}+{m \choose p+1}$$ $$S=-{m-n+1 \choose p+2}+n{m-n \choose p+1}+{m+1 \choose p+2}$$ For the given problem $m=99, n=69, p=30$, then the first twp coefficirnt disappear and we get $$S={100 \choose 32}.$$ Finally, $q=32$.

$\endgroup$
2
$\begingroup$

Essentially, your expression $$\sum_{i=1}^{69}{i\choose 1}\binom{99-i}{30}$$

is saying that, we have $99$ balls in a row and a stick. First we place the stick after the first ball and choose $1$ from the left set, $30$ from the right set. Next we place the stick after the second ball and choose $1$ from the left set, $30$ from the right set and so on. We do this until the right set is only $30$ balls and add all of them up.

For a simpler explanation jump to the last line.

This is exactly same as the number of ways where we first select the "to-be-picked-up" $31$ balls and then place the stick in anywhere between the first and the second leftmost selected ball.

We will break this into two cases:

(1) The stick is immediately after the leftmost ball. Then the number of ways is ${99\choose 31}$.

(2) The stick is at least one ball after the leftmost ball. Then this problem is the same as if "the ball immediately right to the leftmost ball does not exist". Or in other words, the number of ways is same as if we only had $98$ balls to start with.

We will again break the case (2) into two similar cases and continue the similar analysis, which resulted in a chain

$${99\choose 31} + {98\choose 31} + {97\choose 31} + ... + {31\choose 31}$$

Note that case (2) becomes empty at the last step so the analysis won't continue forever.

Now evaluation time, note that

$${31\choose 31}+{32\choose 31}=33={33\choose 32}$$

$${33\choose 32}+{33\choose 31}={34\choose 32}$$

$${34\choose 32}+{34\choose 31} = {35\choose 32}$$

$$...$$

So at last this becomes $${99\choose 32}+{99\choose 31}={100\choose 32}$$

There is actually a even simpler explanation:

This is exactly same as the number of ways where we have $100$ balls to start with and we select $32$ balls and convert the second leftmost selected ball into a stick.

$\endgroup$
1
  • $\begingroup$ Accepted this because I prefer P&C based approaches although the AGP method was also good. $\endgroup$ Aug 9, 2020 at 15:22
0
$\begingroup$

Hint:

$$(99-n)\binom n{30}=100\binom n{30}-31\cdot\dfrac{(n+1)\cdot n!}{(n+1-31)!\cdot(31)!}=100\binom n{30}-31\binom{n+1}{31}$$

Now $\displaystyle\sum_{n=30}^{98}\binom n{30}$ is the coefficient of $x^{30}$ in $$\sum_{n=30}^{98}(1+x)^n=\dfrac{(1+x)^{99}-(1+x)^{31}}{1+x-1}$$

which is $$=\binom{99}{31}-\binom{31}{31}$$

$\endgroup$
6
  • $\begingroup$ did not understand, can you solve a bit more $\endgroup$ Aug 9, 2020 at 10:23
  • $\begingroup$ @AnindyaPrithvi, Observe that $$\sum_{n=30}^{98}(1+x)^n$$ is in Geometric Progression with common ratio $=?$ $\endgroup$ Aug 9, 2020 at 10:24
  • $\begingroup$ not this, the very first step $\endgroup$ Aug 9, 2020 at 10:26
  • $\begingroup$ @AnindyaPrithvi, Put $n=30,31,\cdots,96,97,98$ $\endgroup$ Aug 9, 2020 at 10:32
  • $\begingroup$ I still don't get it, why $(99-n) {n \choose 30}$ instead of $n {{99-n} \choose 30}$ $\endgroup$ Aug 9, 2020 at 10:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .