Solving ${98 \choose 30}+2{97 \choose 30}+3 {96 \choose 30}+...+68{31 \choose 30}={100 \choose q}$ for $q$

Question

${98 \choose 30}+2{97 \choose 30}+3 {96 \choose 30}+...+68{31 \choose 30}={100 \choose q}$

Find the value of $q$?

Could someone give me hint as how to solve this question?

Answer 1

This may be helpful: $\displaystyle\sum\limits_{j=r}^n\,(n+1-j)\,\binom{j}{r}=\binom{n+2}{r+2}$. Because of this identity, I think your sum may be missing the term $69\binom{30}{30}$.

Here is an algebraic proof.

$$\begin{align}\sum_{j=r}^n\,(n+1-j)\,\binom{j}{r}&=(n+2)\,\sum_{j=r}^n\,\binom{j}{r}-\sum_{j=r}^n\,(j+1)\,\binom{j}{r}\\&=(n+2)\,\binom{n+1}{r+1}-(r+1)\,\sum_{j=r}^n\,\binom{j+1}{r+1}\\&=(n+2)\,\binom{n+1}{r+1}-(r+1)\,\binom{n+2}{r+2}\\&=(r+2)\,\binom{n+2}{r+2}-(r+1)\,\binom{n+2}{r+2}\\&=\binom{n+2}{r+2}\,.\end{align}$$

There is also a combinatorial proof of this identity.

There are $\displaystyle\binom{n+2}{r+2}$ subsets $S$ of $\{0,1,2,\ldots,n+1\}$ of size $r+2$. Now, we count the number of such subsets $S$ in a different way. Let $j\in\{r,r+1,r+2,\ldots,n\}$. The number of such subsets $S$ with the property that $j$ is the second largest element of $S$ is given by $\displaystyle(n+1-j)\,\binom{j}{r}$. Consequently, $$\sum\limits_{j=r}^n\,(n+1-j)\,\binom{j}{r}=\binom{n+2}{r+2}\,.$$

This is an analytic proof.

From $$\begin{align}\sum_{k\geq 0}\,\binom{k+r+2}{r+2}\,x^k&=(1-x)^{-(r+3)}=(1-x)^{-2}\,(1-x)^{-(r+1)}\\&=\left(\sum_{k\geq 0}\,(k+1)\,x^k\right)\,\left(\sum_{k\geq 0}\,\binom{k+r}{r}\,x^k\right)\\&=\sum_{k\geq 0}\,\left(\sum_{j=0}^k\,(k+1-j)\,\binom{j+r}{r}\right)\,x^k\,,\end{align}$$ the coefficient of $x^{n-r}$ in $(1-x)^{-(r+3)}$ is thus $$\binom{n+2}{r+2}=\sum\limits_{j=0}^{n-r}\,\big((n-r)+1-j\big)\,\binom{j+r}{r}=\sum\limits_{j=r}^n\,(n+1-j)\,\binom{j}{r}\,.$$

---

In general, $\displaystyle\sum\limits_{j=r}^n\,\binom{n+k-1-j}{k-1}\,\binom{j}{r}=\binom{n+k}{r+k}$. Below is an inductive proof of this identity, although you can use a combinatorial or analytic argument to verify it quite easily.

Let $\displaystyle T_{n,r,k}:=\sum\limits_{j=r}^n\,\binom{n+k-1-j}{k-1}\,\binom{j}{r}$ for nonnegative integers $n,r,k$ (where $\binom{m}{-1}:=0$ for all nonnegative integers $m$, and $\binom{-1}{-1}:=1$). We shall first prove that $T_{n,r,k}=T_{n-1,r-1,k+1}$ for all integers $n\geq 1$, $r\geq 1$, and $k\geq 0$.
Note that $\binom{j}{r}=\sum\limits_{i=r-1}^{j-1}\,\binom{i}{r-1}$ for all integers $r\geq 0$ and $j\geq r$. Hence, $$\begin{align}T_{n,r,k}&=\sum\limits_{j=r}^n\,\binom{n+k-1-j}{k-1}\,\binom{j}{r}\\&=\sum\limits_{j=r}^n\,\binom{n+k-1-j}{k-1}\,\sum\limits_{i=r-1}^{j-1}\,\binom{i}{r-1}\\&=\sum_{i=r-1}^{n-1}\,\binom{i}{r-1}\,\sum_{j=i+1}^n\,\binom{n+k-1-j}{k-1}\\&=\sum_{i=r-1}^{n-1}\,\binom{i}{r-1}\,\sum_{j=k-1}^{n+k-2-i}\,\binom{j}{k-1}\\&=\sum_{i=r-1}^{n-1}\,\binom{i}{r-1}\,\binom{n+k-1-i}{k}\\&=\sum_{i=r-1}^{n-1}\,\binom{(n-1)+(k+1)-1-i}{(k+1)-1}\,\binom{i}{r-1}\\&=T_{n-1,r-1,k+1}\,.\end{align}$$
Since $\displaystyle T_{n,r,k}=\binom{n+k}{r+k}$ for $k=0$ and $k=1$, it follows from $T_{n,r,k}=T_{n-1,r-1,k+1}$ that $\displaystyle T_{n,r,k}=\binom{n+k}{r+k}$ for any nonnegative integer $k$. The proof is now complete.

Answer 2

You want $N =\sum_{k=1}^{68} k\binom{99-k}{30} $.

According to Wolfy this is $ 143012501349174257560226706 $.

Again, according to Wolfy, $\binom{100}{32}= 143012501349174257560226775 $.

These differ by $69$.

So, unless Wolfy made an error, there is no such $q$, but $q=32$ comes very close.