Tagged Questions

Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

50 views

Sum over binomial coefficients

Define $$f_c(n)=\sum_{k=0}^{\lfloor cn\rfloor}{n\choose k}$$ for some fixed constant $c$ (say, $0<c<1/2$). What are the asymptotics of $f_c(n)$ as $n\to\infty$? It seems that this should be ...
29 views

71 views

Why does ${3 \choose 1}$ equal to the coefficient of $x^1$ in the function $(1+x)^3$?

There are three containers, each one can hold exactly one element. Thus there are exactly ${3 \choose 1}$ combinations without repetition to put 1 element into those three containers. This coincides ...
30 views

37 views

Transforming and identity for $n \choose k$ with the “committee and chair” trick

I am not sure if this equality has a more formal name, but it is informally called the "committee and chair" trick from Ross. It is: $$k {m \choose k} = m {m-1 \choose k-1}$$ I saw it applied in the ...
110 views

How to use the method of undetermined coefficients to get complex version of binomial expansion?

Show that if $|z|<1$, and $\alpha\in\mathbb{C}$, then $(1+z)^{\alpha}=\sum\limits_{n=0}^\infty {\alpha\choose n}z^n$, where $${\alpha\choose n}=\frac{\alpha(\alpha-1)\cdots(\alpha-n+1)}{n!}$$ I ...
39 views

35 views

59 views

Recurrence relationships and a “weighted Pascal's triangle”

I was thinking about this problem a few days ago and in the process I came up with what I can best describe as a two-dimensional recurrence relationship. It seemed obvious to me that this was ...
112 views

A sum including binomial coefficients

I would like to prove the following equality: $$\sum_k (-1)^{n-1}(-2)^k\binom{n}{k+1}\binom{n+k-1}{k}=\sum_{k=0}^{n-2}\binom{2n-k-2}{n-1}\binom{n-2}{k}$$ but the power over two and the switch on the ...
1k views

Proof of the Hockey-Stick Identity: $\sum_{t=0}^n \binom tk = \binom{n+1}{k+1}$

After reading this question, the most popular answer use the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$ What's the name of this identity? Is it the identity of the Pascal's triangle ...
102 views

Find the value of $\sum_0^n \binom{n}{k} (-1)^k \frac{1}{k+1}$

Find the value of $\sum_0^n \binom{n}{k} (-1)^k \frac{1}{k+1}$. Writing out several terms, I think the answer is $1/(n+1)$, but I'm struggling to prove this. I would greatly appreciate it if someone ...
103 views

Prove by induction $\sum _{i=1}^n\left(-1\right)^{i+1}\:\binom{n}{i}\:\frac{1}{i}=1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}$ [duplicate]

$$\sum _{i=1}^n\left(-1\right)^{i+1}\:\binom{n}{i}\:\frac{1}{i}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$$ Can someone give me a hint on how to give the proof, I am stuck when I am proving it for p(n+...
40 views

Prove that sum of product of binomial coefficients is equal to 0 [duplicate]

Show that $\sum\limits_{k = 0}^{n} (-1)^k C_n^k C_{3n-k-1}^{2n-k} = 0$ for any $n > 0$. I've tried to prove it by induction, but it turns out to be not so easy. I bet there is some natural ...
66 views

Sum of Binomials Coefficients multiplied by the harmonic numbers

I am interested in solve the next sum: $\sum_{i=1}^{N} {N \choose i} i^{-G}$ for $G \geq 1$. Some ideas? Thank you in advance by your help!
35 views

Function involving combinations and conditions: {1, 2} → {1, 2, 3}

Can someone help me understand this problem? Apparently the total number of functions is 6. $$={2 + 3 -1 \choose 2}$$ $$={4 \choose 2}$$ $$=6$$ I'm pretty confused so any detail of the problem ...
23 views

33 views

For $n\in \mathbb Z$ and $n\ge 0$, prove that: $$\frac{2\sqrt{\pi}\,\Gamma(\frac{1}{2}+n)}{\Gamma(n+1)}=\frac{\pi}{2^{2n-1}}\binom{2n}{n}$$ I started to prove. We now that $\Gamma(\frac{1}{2})=\... 1answer 75 views Proving binomial summation identity using generating functions An exercise for class requires me to prove the following identity using generating functions: $$\sum_{k=0}^{m/2} (-1)^k {n \choose k} {n+m-2k-1 \choose n-1} = {n \choose m}$$ for all$m \leq n$and$m$... 2answers 66 views If$a + b + c + d = 45$, how many combinations are there of$a,b,c$, and$d$if$a \le 5$and$b \le 3\$?

I'm stumped on binomial coefficients and counting problems in discrete math. To be clear, this is not the same problem I'm having to do for homework. I changed the numbers around, but had to include ...