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

learn more… | top users | synonyms (1)

4
votes
0answers
89 views

How to prove this indentity $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-…-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$ [duplicate]

I don't know how to prove this identity: $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-\binom{100}{3}^2+...-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$
0
votes
2answers
75 views

closed form for $\sum_{k=0}^{n-p}\binom{n}{k}\binom{n}{p+k}$

how to get closed form for $$\sum_{k=0}^{n-p}\binom{n}{k}\binom{n}{p+k}$$ I tried to write binominal in term of gamma function but I got no result what is your suggest to solve the problem ?
6
votes
2answers
227 views

What is $\lim_{n\to\infty} \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\left(4^{-k}\binom{2k}{k}\right)^{\frac{2n}{\log_2{n}}}\,?$

What is $$\lim_{n\to\infty} \displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k}\left(4^{-k}\binom{2k}{k}\right)^{\frac{2n}{\log_2{n}}}\,?$$
1
vote
1answer
61 views

What is $\lim_{n\to\infty} \sum_{k=1}^{n/2} \left(\frac{en}{2k}\right)^{2k} \frac{1}{\sqrt{\pi k}}^{\frac{3n}{\log_2{n}}}\,?$

What is $$\lim_{n\to\infty} \sum_{k=1}^{n/2} \left(\frac{en}{2k}\right)^{2k} \frac{1}{\sqrt{\pi k}}^{\frac{3n}{\log_2{n}}}\,?$$ Numerically it seems to be $0$.
5
votes
3answers
694 views

Taking Limits with Binomial Coefficients

I am interested in taking the following limit: \begin{equation} \lim_{n \to \infty}\frac{{n/2 \choose m}}{n \choose m}. \end{equation} Provided that $m$ is fixed the solution is: \begin{equation} ...
2
votes
2answers
75 views

Closed form for $\prod_{k=1}^n \binom{k^2+2k}{k^2}$

Does anybody know how I can find a closed form for the expression $$ \prod_{k=1}^n \binom{k^2+2k}{k^2}? $$ There are many ways to handle such things, but with sum instead of product. Here, I have no ...
-1
votes
2answers
649 views

Prove $k\binom nk=n \binom{k-1}{ n-1}$ algebraically.

I need to prove $k\binom nk=n \binom{k-1}{ n-1}$ where $n$ and $k$ are integers with $1\leq k\leq n$ using an algebraic proof. I solved the left side which is $\binom nk$ using the pascals identity ...
2
votes
1answer
306 views

Prove that $\displaystyle\sum_{j=m}^n\sum_{k=0}^{2m}{4j\choose 2k}{2j-k\choose 2m-k}={2n+2m+1\choose 4m+1}2^{4m-1}$

Let $n,m$ are positive integers satisfy the condition $n\ge m>0$ Prove that $\displaystyle\sum_{j=m}^n\sum_{k=0}^{2m}{4j\choose 2k}{2j-k\choose 2m-k}={2n+2m+1\choose 4m+1}2^{4m-1}$
6
votes
1answer
180 views

Limit of $ \displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} 2^{-2nk} \binom{n}{2k}\left(\binom{2k}{k}^n\right)$

I can see numerically that $$\lim_{n \to \infty} \sum_{k=0}^{\lfloor n/2 \rfloor} 2^{-2nk} \binom{n}{2k}\left(\binom{2k}{k}^n\right) = 1$$ but how can you prove this? Using Stirling's approximation ...
1
vote
1answer
61 views

Simplifying Sum of Subsets

Given sets $A$ and $R$ such that $R \subseteq A$ and a number $x \leq |A|$, I am trying to simplify the following sum: $$\begin{equation*} \sum_{R \subseteq W \subseteq A : |W| = x} \Big( \sum_{Y ...
4
votes
1answer
573 views

Probability of two independent random variables being equal

Assume that $X$ and $Y$ are two independent random variables that follow the binomial distribution of parameters $p$ (the probability of one success) and $n$ (the number of trials). I was wondering ...
3
votes
5answers
85 views

How to find the coefficient of $x^8$ in $\prod\limits_{i=1}^{10}{\left(x-i\right)}$?

How to find the coefficient of $x^8$ in $(x-1) (x-2) . . .(x-10)$. Is there any general formula to solve this kind of problems?
2
votes
1answer
69 views

Binomial coefficients inequality

It seems to me that there should be a simple way to prove that $$ \binom{n}{s+1+a} + \binom{n}{a} \leq \binom{n}{s} $$ For $s > n/2$ and $a < n-s$. However it looks like I'm missing it. Any ...
2
votes
5answers
114 views

coefficient of $x^2$, in $(1+x+x^2)^{10}$

How to find coefficient of $x^2$, in $(1+x+x^2)^{10}$, without actually expanding it? I think the fact $\dfrac{1-x^3}{1-x}=1+x+x^2$ may help. But can't use it!
2
votes
1answer
76 views

Infinite series containing binomial coefficients

I've encountered the following series: $$\sum_{t=1}^\infty {1 \over 2^{t}}\, {{\large t} \choose {\large{t + x \over 2}}}$$ Is this series even convergent? I'm really lacking knowledge on series ...
0
votes
1answer
61 views

Upper bound for ${n \choose cn}$

Is it true that for any $0<c<1/2$ and sufficiently large $n'$, there exists a $d <2$ such that ${n \choose cn} < d^n$ for all $n>n'$? Clearly we have to assume $cn$ is an integer. I ...
6
votes
2answers
129 views

The value of $\binom{50}0\binom{50}1+\binom{50}1\binom{50}2+\dots+\binom{50}{49}\binom{50}{50}$ is

The value of $\binom{50}0\binom{50}1+\binom{50}1\binom{50}2+\dots+\binom{50}{49}\binom{50}{50}$ is? I tried this: ...
0
votes
1answer
53 views

Generating functions of form $\sum_{n=0}^\infty a_n x^{kn}$

Let's consider generating function $$F(x) = (1+x)^r = \sum_{n=0} \binom{r}{n} x^n$$ And another generating function $$G(x) = (1+x^2)^r = \sum_{n=0} \binom{r}{n}x^{2n}$$ Please note those 2 functions ...
0
votes
1answer
63 views

Binomial coefficient - first two terms, proof of inequality

I've seen the following and I'm not sure whether it is true or not, and if yes, why it holds. $(1-p)^x \geq 1-p x$ for $p\in (0,1)$ and $x>0$. Do I need some additional Information to prove ...
1
vote
3answers
156 views

Calculate $\sum_{k=0}^n k \binom{n}{k} p^k (1-p)^{n-k}$

For $p \in [0,1]$ calculate $$S =\sum_{k=0}^n k \binom{n}{k} p^k (1-p)^{n-k}.$$ Since $$ (1-p)^{n-k} = \sum_{j=0}^{n-k} \binom{n-k}{j} (-p)^j, $$ then $$ S =\sum_{k=0}^n \sum_{j=0}^{n-k} k ...
1
vote
2answers
138 views

Binomial Expansion.

So I had a question: Prove that for $n \geq 1$, $${n \choose 1} + 2{n \choose 2} + 3{n \choose 3} + ...+ n{n \choose n} = n2^{n-1}$$ So my idea was to take the binomial expansion of $(1+1)^n$ which ...
2
votes
1answer
47 views

asymptotic estimate for this expression

How can I compute an asymptotic estimate for following expression? \begin{equation} A = ...
2
votes
4answers
5k views

proof by induction: sum of binomial coefficients $\sum_{k=0}^n (^n_k) = 2^n$

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
1
vote
1answer
39 views

Binomial Coefficient Recusions

Let m and j be non-negative integers. Define $S^{0}_{m} = 1$ and: $ S^{j}_{m} = \displaystyle\sum\limits_{i=1}^{m} S_{i}^{j-1}$ Show via induction: $ S_{m}^{j} = {m+j-1 \choose j} $ I can ...
1
vote
0answers
81 views

Chu-Vandermonde-like combinatorial identity

I am looking for a simple combinatorial proof of the binomial identity: $$\sum_{j=0}^n \binom{2j}{j}\binom{2n-2j}{n-j} = 4^n.\tag{1}$$ The standard way I know is to exploit the generating function: ...
1
vote
2answers
148 views

Finding the coefficient of a generating function

Given $f(x) = x^4\left(\frac{1-x^6}{1-x}\right)^4 = (x+x^2+x^3+x^4+x^5+x^6)^4$. This is the generating function $f(x)$ of $a_n$, which is the number of ways to get $n$ as the sum of the upper faces of ...
1
vote
1answer
244 views

Using the binomial expansion to solve a summation

I have to evaluate a summation from k=1 to n of k3^k(nCk) by setting x equal to the appropriate values in the binomial expansion.
1
vote
3answers
78 views

One Binomial Equation $\sum_{i=0}^{z} {n_1 \choose i}{n_2 \choose z-i} = {n_1+n_2 \choose z}$ [duplicate]

I saw one proof using this formula: $$ \sum_{i=0}^{z} {n_1 \choose i}{n_2 \choose z-i} = {n_1+n_2 \choose z}$$ Can anyone help explain it, thank you!
1
vote
1answer
112 views

Can't find an identity for proving that $ \sum_{k=0}^{i+1} \binom {i+1} k=2^{i+1}$ [duplicate]

$$ \sum_{k=0}^{i+1} \binom {i+1} k$$ I can't find an identity for this summation :( To clarify I'm trying to prove using induction that this sum is equal to $2^{i+1}$, I have my basis and ...
0
votes
1answer
71 views

Probability binomial distribution and Poisson distribution

It is found that 5% of screws in a factory are found to be defective. Use the Poisson theorum and the binomial theorum to compute the probability that two or more are found to be defective if a sample ...
21
votes
3answers
547 views

How prove this sum $\sum_{n=1}^{\infty}\binom{2n}{n}\frac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}$

show that $$\sum_{n=1}^{\infty}\binom{2n}{n}\dfrac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}=5+4\sqrt{2}\left(\log{\dfrac{2\sqrt{2}}{1+\sqrt{2}}}-1\right)$$ where ...
1
vote
1answer
74 views

Calculate sum with binomial coefficients: $\sum_{k=0}^{n} \frac{1}{k+1} \binom nk x^{k+1}$

I need help with finding the sum of $\sum \limits_{k=0}^{n} \frac{1}{k+1}{n\choose k}x^{k+1}$
0
votes
2answers
84 views

How to calculate this sum: $\sum_{k=1}^{n} \frac{k}{n^k} \binom nk$ [closed]

How do you calculate this sum $$ \sum \limits_{k=1}^{n} \frac{k}{n^k}{n\choose k} \;?$$
0
votes
2answers
116 views

MCA entrance question

In triangle $ABC$, the value of $\ \displaystyle \sum_{r=0}^n\ ^nC_ra^rb^{n-r}\cos(rB-(n-r)A)$ is equal to (a) $c^n$ (b) $b^n$ (c) $a^n$ (d) $0$ I have no idea how to start ...
8
votes
2answers
313 views

Does this really converge to 1/e? (Massaging a sum)

Short version: can we prove that $$\sum_{k=0}^n (-1)^k \binom{n}{k}^2 \frac{k!}{n^{2k}} \to \frac1e$$ as $n \to \infty$? Long version: First, consider $$a_n = \sum_{k=0}^n \frac{(-1)^k}{k!}$$ It is ...
1
vote
0answers
36 views

binomial coefficient divisibility properties

I'm looking for a (possibly large) list of divisibility properties of binomial coefficients. Does anyone know a good reference? For example, Graham, Knuth, and Patashnik, Discrete Combinatorics, ...
3
votes
2answers
43 views

show that these two equation holds by binomial theorem

I know the binomial theorem, but I have no idea how to simplify this. I tried to write it as (y+x)^n+(y+x)^n-(y+x)^0+(y+x)^n-(y+x)^1+...+(y+x)^n-(y+x)^(n-1), but it didnt work out.
1
vote
1answer
2k views

Binomial Distribution - independence

I have the following problem that I'm stuck on a few parts. ...
4
votes
2answers
127 views

Evaluate the summation involving binomials.

$\sum _{ i=0 }^{ 100 }{\binom{k}{i}}*{\binom{M-k}{100-i}*\frac{k-i}{M-100}}/{\binom{M}{100}}$ I wrote the first few terms but couldn't find any pattern and how to club the terms. Help.
0
votes
1answer
360 views

Function returning number of subsets of size $k$ of a set of size $n$.

I am looking for a function that returns the number of subsets of size $k$ of a set of size $n$. Ideally, the function is commonly used. I took a look at the binomial coefficient. However, there ...
2
votes
0answers
66 views

find the the variable that maximizes a function

I have a function that I am trying to find for what input it maximizes. $$ f(n) = {\binom{S}{2}}^{n/S}$$ I need to find the $S$ for which this function maximizes (for infinite $n$). more generally, ...
1
vote
1answer
45 views

In a lottery of $90$ numbers a man adds extra $1,2,3$

Consider a lottery where $5$ balls are chosen randomly among $90$ balls numbered from $1$ to $90$. A man cheats adding to the $90$ balls, before the draw, three more balls numbered $1,2,3$. We say ...
5
votes
3answers
820 views

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac n2 \rceil$ or $ \lfloor \frac n2\rfloor $?

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac{n}{2} \rceil $ or $ \lfloor \frac{n}{2} \rfloor$ ? This link provides a proof of sorts but it is not satisfying. From what I ...
2
votes
3answers
437 views

Prove $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$

I need to prove the following: If $n,m,k\in \mathbb{N}$ and $k\leq m \leq n$, then $$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$. I did the following steps: \begin{align} ...
3
votes
3answers
94 views

Prove $\sum\limits_{r=0}^{2n} r \binom{2n}{r}^2 = 2n \binom{4n-1}{2n}$

I expanded $(1+x)^{2n}$ = $\sum\limits_{r=0}^{2n} \binom{2n}{r} x^r $ Differentiating both sides, we get $2n(1+x)^{2n-1}$ = $0$ + $\binom{2n}{1}$ + $2\binom{2n}{2}x$ + $3\binom{2n}{3}x^2$ ..... ...
7
votes
2answers
516 views

How to count matrices with rows and columns with an odd number of ones?

I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$ by counting matrices of size $n\times m$ with entries in $\{0,1\}$ ...
3
votes
1answer
66 views

A combinatorics question on a sequence of binomial coefficents

On a past-paper of a Combinatorics exam I will be taking they ask the question: Prove that for $k$ odd and greater than 1, the sequence of numbers $\binom{k}{1}, \binom{k}{2}, ..., ...
2
votes
1answer
60 views

binomial identity involving sum of diagonal elements

It's well-known and easy to show that $\binom{k}{n} = \frac{k}{n}\binom{k-1}{n-1}$. Also, I've come across the formula $\binom{k}{n}=A\binom{k-1}{n-1}+B\binom{k-2}{n-2}$, where $A$ and $B$ are ...
3
votes
1answer
116 views

How find this sum $\sum_{k=0}^{\left[\frac{n}{2}\right]}\frac{(-1)^k\binom{n-k}{k}}{n-k}$

How find this sum $$\sum_{k=0}^{\left[\dfrac{n}{2}\right]}\dfrac{(-1)^k\binom{n-k}{k}}{n-k}$$ My try:since $$\dfrac{(-1)^k}{n-k}=\int_{-1}^{0}x^{n-k-1}dx$$ then I can't Thank you very much!
2
votes
2answers
775 views

find the coefficient of the given term when the expression is expanded by the binomial theorem

I am just trying to understand why the term is $\binom{15}8$(3p$^2$ - 2q)$^7$. I need to find the coefficient in $p^{16}q^7$ in $(3p^2 - 2q)^{15}$ So, I know that $n = 15$ and I have $a^{n - k}b^k$ ...