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)

1
vote
3answers
79 views

Is there an expression for the sum of $\binom nr^2$ for each $n$? [duplicate]

Is there a standard expression for $$\sum_{r=0}^{n}\binom nr^2$$
6
votes
2answers
212 views

summation of a binomial expression that doesn't start from 0

I have the following expression: $$ \sum_{k=9}^{17}\binom{17}{k} $$ and I need to show that it's equal to: $$ 2^{16} $$ now I know that if 'k' was starting from zero and not from 9 , like this: $$ ...
0
votes
1answer
56 views

Evaluation of all positive integer ordered pair $(n,r)$ for which $\displaystyle \binom{n}{r} = 2016$

$(1)$ Evaluation of all positive integer ordered pair $(n,r)$ for which $\displaystyle \binom{n}{r} = 120$ $(2)$ Evaluation of all positive integer ordered pair $(n,r)$ for which ...
2
votes
0answers
29 views

Simplify binomial coefficients sum [duplicate]

Exercise requires to simplify this sum: $$\sum_{k=0}^{20} \binom{50}{k}\binom{50}{20-k}$$ Tried to figure this out with no success. I have only final answer, which is $\binom{100}{20}$. Please help ...
0
votes
2answers
45 views

Simplify the sum of binomial coefficients

The exercise requires to simplify the following expression: $$\sum_{k=0}^{25} \binom{50}{2k}$$ By finally looking at someone's answer, I know that the result should be $2^{49}$, but the following ...
1
vote
1answer
28 views

Binomial distribution, explanation formula

I have a really simple question. I can't figure out the meaning of the binomial coefficient in the case of a binomial distribution formula. I know what the formula means, and how to use it for the ...
3
votes
3answers
58 views

how to come up with this identity $\sum\limits_{i=r}^{n-k+r}{i \choose r}{{n-i} \choose {k-r}}={{n+1} \choose {k+1}}$

This identity is used in an exercise. Could you help me understand how I should reason to come up with it? Ideally, from a combinatorial point of view.
2
votes
1answer
49 views

Prove that $\frac{(2n)!}{(n!)^2}-1$ is divisible by $(2n+1)$

Prove that $$\frac{(2n)!}{(n!)^2}-1$$ is divisible by $(2n+1)\;,$ Where $n\in \mathbb{N}$ and $n>1$ $\bf{My\; Try::}$ Let $$S = \frac{(2n)!}{n!^2}-1 = \frac{2^n(2n-1)(2n-3)\cdot \cdot ...
0
votes
1answer
51 views

Binominal expression simplification

I need to simplify the expression $$\sum_{k = 1}^{10} k\binom{10}{k}\binom{20}{10 - k}$$ Thank you.
4
votes
3answers
76 views

Find the sum of the $\sum_{m=k}^{+\infty}\binom{m}{k}(1-p)^k\cdot p^{m-k}$

Let $0<p<1$,Find the sum $$\sum_{m=k}^{+\infty}\binom{m}{k}(1-p)^k\cdot p^{m-k}$$
5
votes
1answer
119 views

How do you find the probability of A winning if the probability of getting a favourable outcome in the $r^{th}$ turn is a function of $r$?

Problem: Two players A and B are playing snake and ladder. A is at 99 and he needs 1 to win in rolling of a dice. However, he is always allowed to re-throw the dice if 6 appears. What is the ...
0
votes
1answer
29 views

A Binomial coefficient sequence

If 'n' is a positive integer and $C_k=^nC_k$, then find the value of: $[\sum\limits_{k=1}^n\frac{k^3}{n(n+1)^2.(n+2)}(\frac{C_k}{C_{k-1}})^2]^{-1}$ [![enter image description here][1]][1] I have ...
1
vote
0answers
39 views

Does the property ${n\choose r}={n\choose n-r}$ have a name?

Due to the relation between Pascal's Triangle and the choose function in probability theory, we can deduce that $${n\choose r}={n\choose n-r}$$ because Pascal's Triangle is symmetric. This can also be ...
0
votes
1answer
67 views

Closed form for a binomial identity [closed]

$\textrm {How do I find a closed form for } \sum_{j=0}^n{} j\displaystyle\binom{j}{r} = ?$ Is this some kind of upper index summation? Any previous papers? Thank you
0
votes
4answers
147 views

How many numbers are there of 2n digits that the sum of the digits in the first half equals the sum of the digits in the second half

The question is how many number of a given number of digits 2n where the sum of the first half of the digits equals the sum of the digits in the second half. So this is for a programming problem and ...
2
votes
0answers
33 views

Can someone expain to me what's going on (binomial coefficient)?

I'm watching this proof for $\zeta(2n)$ on YouTube. This is what I can understand so far: $${s\over e^{s} -1} = \sum^{\infty}_{n=0} {\beta_n\over n!} s^n$$ Where $\sum^{\infty}_{n=0} {\beta_n\over ...
1
vote
2answers
27 views

Induction with binomial coefficient

Is mathematical Induction possible with this sigma sign? $A(k) =\sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j} = \binom{m+n}{k}$ $A(k+1) = \sum_{j=0}^{k+1} \binom{m}{j}\binom{n}{(k+1)-j} = ...
1
vote
2answers
54 views

Bound on sum of combinations

I came across the following inequality $\sum_{i=0}^D \binom N i \le N^D+1$. I am not sure how to prove this. I tried to do it by induction on $D$, and started with observing the values of sum for ...
1
vote
1answer
78 views

Gaussian polynomial identities

I'd appreciate any hints for showing that these identities are true for Gaussian polynomials. I've tried to approach the problem using basic algebra but it gets messy very quickly and I've gotten ...
2
votes
1answer
81 views

Simplifying my sum which contains binomials

While dealing with compositions (ordered partitions) of integers, I found the following formula for the shifted $m$-generalized Fibonacci numbers (Wikipedia: Generalizations of Fibonacci numbers): ...
-1
votes
3answers
44 views

Reducing this binomial expression [closed]

I need help for showing that: $$\sum\limits_{k=2}^{50} = k \cdot(k-1)\binom{50}{k}$$ is equal to: $$50\cdot 49\cdot 2^{48}$$ please help , thank you.
0
votes
1answer
76 views

Prove that $\binom{n}{0}\cdot \binom{2n}{n}-\binom{n}{1}\cdot \binom{2n-2}{n}+\binom{n}{2}\cdot \binom{2n-4}{n}+… = 2^n$

Prove that $$\binom{n}{0}\cdot \binom{2n}{n}-\binom{n}{1}\cdot \binom{2n-2}{n}+\binom{n}{2}\cdot \binom{2n-4}{n}+........... = 2^n$$ $\bf{My\; Try::}$ Coefficient of $x^n$ in ...
11
votes
3answers
305 views

Dealing with a difficult sum of binomial coefficients, $\sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j} $

I am interested in finding an upper bound for the sum $$F(n)= \sum_{l=0}^{n}\binom{n}{l}^{2}\;\sum_{j=0}^{2l-n}\binom{l}{j}$$ Ideally it should be possible to evaluate it exactly using some ...
2
votes
2answers
68 views

What is the coefficient of $x^4$ in the expansion of $\sqrt[3]{1+x}$

Here's what I tried: $$\sum_{n \ge0} {\frac{1}{3} \choose n} x^n= \sum_{n \ge0} = \frac{\frac{1}{3}!}{n!(n-\frac{1}{3})!}x^n=\sum_{n \ge0} \frac{(\frac{1}{3}-1)(\frac{1}{3}-2)\cdot ...
2
votes
2answers
78 views

Show that $a_n=\frac{n+1}{2n}a_{n-1}+1$

Show that $a_n=\frac{n+1}{2n}a_{n-1}+1$ given that: $a_n=1/{{n}\choose{0}}+1/{{n}\choose{1}}+...+1/{{n}\choose{n}}$ The hint says to consider when $n$ is even and odd. When $n=2k$ I get: ...
1
vote
1answer
60 views

Proof of product summation of binomial coefficients

when I try to proof the sum of two independent negative binomial distribution to be negative binomial, I end up with how to proof the following identity. I try the induction but after I rearrange the ...
1
vote
2answers
92 views

In how many ways can I split 151 different objects into 3 categories?

In how many ways can I split 151 different objects into 3 categories such that no category gets absolute majority? I figured that the answer should be: ...
0
votes
1answer
28 views

Negative binomial coefficient

For $r \geq 1$, $k \geq 0$ both integers, I wish to show that $$\binom{-r}{k}^{*}(-1)^{k} = \binom{r+k-1}{k}$$ (the negative binomial coefficient is the left one). By definition, ...
1
vote
1answer
45 views

Show that $\sum_{i=\lceil\alpha n\rceil}^n {n\choose i}\le 2^{nH(\alpha)}, \alpha\in(1/2,1]$

For $1/2<\alpha\le 1$ show that $$\sum_{i=\lceil\alpha n\rceil}^n {n\choose i}\le 2^{nH(\alpha)}$$ where $H(\alpha)=-\alpha\log_{2}\alpha - (1-\alpha)\log_2 (1-\alpha)$ is the entropy. ...
1
vote
2answers
43 views

Equality of two binomial coefficient containing expressions

Why is $$ \begin{align} &\sum_{k=0}^n(-1)^k\left[\binom{n-k-1}{k}+\binom{n-k-1}{k-1}\right]2^{n-2k}\\ ...
0
votes
2answers
66 views

What is the multiplication of two sigmas?

Say we have two sigmas $\sum_{i=0}^n\dbinom{n}{i}x^i$ and $\sum_{i=0}^m\dbinom{m}{i}x^i$, what would be the resultant of the above? How do you, in general, multiply two sigmas?
11
votes
2answers
134 views

What are the “numerator” and “denominator” of binomial coefficients called?

Do the numbers $n$ and $k$ in the binomial coefficient $\binom nk$ have a name? For the fraction $\frac nk$ we would use numerator and denominator. But I have not seen some terminology for binomial ...
1
vote
3answers
56 views

prove that $ \binom{n-1}{0} +\binom{n}{1}+\binom{n+1}{2}+\cdots+\binom{n+k}{k+1}=\binom{n+k+1}{k+1}$

I am asked to prove that $$ \dbinom{n-1}{0} +\dbinom{n}{1}+\dbinom{n+1}{2}+\cdots+\dbinom{n+k}{k+1}=\dbinom{n+k+1}{k+1}$$ So far what I've tried ,without looking to much at the sum I've to prove ,is ...
0
votes
0answers
47 views

Simplify sum with binomials

An algorithm finds prefixes of given length k from given word with length n. It is required to find the time complexity of given algorithm. It is easy when no nodes get cut off in its recursion tree ...
2
votes
3answers
190 views

Evaluating $\int_{-\pi}^{\pi} (e^{ix} + e^{-ix})^n dx $

In an exercise following identity is used: $$ \int_{-\pi}^{\pi} (e^{ix} + e^{-ix})^n dx = \begin{cases} 0, \hspace{2.1cm} n = 2m+1 \\ 2\pi {2m \choose m}, \hspace{1cm} n=2m. \end{cases}, $$ Does ...
3
votes
3answers
114 views

Proof that $\sum_{i=0}^n {n\choose i}2^{i}=3^{n}$ [duplicate]

The following sum came up in a combinatorial argument. I know what it equals thanks to Wolfram Alpha, but I'm not sure how to show it $$\sum_{i=0}^n {n\choose i}2^{i}=3^{n}$$
1
vote
3answers
99 views

Is there any way to calculate the simple product of binomial coefficients

Given the sum $$ \sum_{k=0}^{m} {n \choose k} {m \choose k}, $$ where $ n > m$. Could it be somehow calculated into a shorter an nicer expression which doesn't contain the sum? Thanks in advance!
0
votes
2answers
143 views

Determine the coefficient of $x^ay^b$ in the expansion of $(1+x+y)^n$

Let $n$ be a positive integer, and let $a, b$ be integers greater than or equal to 0 such that $a+b\le n$. Determine the coefficient of $x^ay^b$ in the expansion of $(1+x+y)^n$. Give a counting ...
1
vote
1answer
43 views

Factorials/Binomial Coefficients (Finding Integer Solutions)

Question There are many integer solutions to the equation $\begin{pmatrix}n\\r\\ \end{pmatrix} = \begin{pmatrix}n+1\\r-1\\ \end{pmatrix}$ including $n = r = 1$. Find an ...
5
votes
1answer
71 views

A combinatorial expression is equal to a binomial coefficient squared

Problem: Prove for all natural numbers the following identity: $$\sum_{r=0}^{n}\frac{(2n)!}{(r!)^2((n-r)!)^2}=\dbinom{2n}{n}^2$$ I have just been successful in interpreting the LHS of the above as ...
1
vote
1answer
79 views

How can I evaluate $\sum_{i=0}^\infty \frac{1}{k^i} \binom{2i}{i}$

Evaluate $$\sum_{i=0}^\infty \left(\frac{\binom{2i}{i}}{k^i}\right),$$ where $k$ is a whole number. I can't figure out how to approach this question, as no binomial series has such coefficients.
0
votes
1answer
86 views

Upper bound for partial sum of binomial coefficients

I am familiar with the proof of the upper bound $\sum_{i=0}^k \binom{n}{i} \le (ne/k)^k$, but I was told that the worse bound $$\sum_{i=0}^k \binom{n}{i} \le (n+1)^k$$ has a simple combinatorial ...
0
votes
1answer
18 views

Retrieve position from binary number ordered by number of ones

I have binary numbers of length s. They are ordered by numbers of ones, and they can have at most j zeros. That is: first are ordered all numbers containing (s; 0) possible subsets of s numbers, next ...
0
votes
1answer
28 views

Probability: Relationship between Multinomial expansion and Combinations

I have the following problem: Place $K$: where $35\%$ of students live Place $N$: where $45\%$ of students live Place $H$: where $20\%$ of students live $4$ students are randomly selected What is ...
0
votes
0answers
23 views

Bounding simple series involving binomial coefficient

Let $r \ge 1$. What is a simple argument to show the following two inequalities: \begin{align*} \sum_{m=1}^n 2^m \binom{n}{m}^2 \Big( \frac{en}{m}\Big)^{-5rm} &\le n^{-r} \\ \sum_{m=1}^n ...
1
vote
4answers
44 views

How can I find the coefficient of x when the power is greater than the powers of 2 brackets using binomial expansion?

I have been given this question: Find the coefficient of $x^{13}$ in the expansion of $(1 + 2x)^4(2 + x)^{10}$. I know how I would find $x^4$ or lower degrees, but I am unsure how to approach this, ...
9
votes
2answers
102 views

How to prove $\sum_{i=1}^ki^k(-1)^{k-i}\binom {k+1}{i} =(k+1)^k$

How to prove $\sum_{i=1}^ki^k(-1)^{k-i}\binom {k+1}{i} =(k+1)^k$ where k is a positive integer. Any hints can help.
7
votes
3answers
118 views

Prove the identity $\binom{2n+1}{0} + \binom{2n+1}{1} + \cdots + \binom{2n+1}{n} = 4^n$

I've worked out a proof, but I was wondering about alternate, possibly more elegant ways to prove the statement. This is my (hopefully correct) proof: Starting from the identity $2^m = \sum_{k=0}^m ...
1
vote
0answers
44 views

Problem with induction of binomial coefficiency

(Sorry for making up math language, I am roughly translating math terms here) This is part of some of the induction exercises in the book "Otto Forster: Analysis 1" (1.2): ...
0
votes
1answer
40 views

Can this be proved using definite integrals [duplicate]

It's a problem from a high school math book that I've been unable to solve: Prove using definite integrals that, $${n \choose 1}-\frac{1}{2}{n \choose 2}+\frac{1}{3}{n \choose ...