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)

0
votes
2answers
50 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
120 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
43 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
184 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
97 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
96 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
72 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
39 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
66 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
77 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
40 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
13 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
24 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
21 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
36 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
99 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
95 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
42 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
30 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 ...
1
vote
1answer
39 views

How to show $\phantom{d}_d C_0+\phantom{d}_d C_4 + \cdots = 2^{d-2} + 2^{\frac{d}{2}-1} \cos(\frac{d \pi}{4}) $?

I want to show following identities \begin{align} &\phantom{d}_d C_0+\phantom{d}_d C_4 + \cdots = 2^{d-2} + 2^{\frac{d}{2}-1} \cos(\frac{d \pi}{4}) \\ &\phantom{d}_d C_1+\phantom{d}_d C_5 ...
2
votes
2answers
29 views

Find $\lim_{n\to\infty}(\frac{\sideset{^{3n}}{_n} C}{\sideset{^{2n}}{_n} C})^{\frac{1}{n}}$

Find $\lim_{n\to\infty}(\frac{\sideset{^{3n}}{_n} C}{\sideset{^{2n}}{_n} C})^{\frac{1}{n}}$ Let $L=\lim_{n\to\infty}(\frac{\sideset{^{3n}}{_n} C}{\sideset{^{2n}}{_n} C})^{\frac{1}{n}}$ $\log ...
2
votes
2answers
44 views

Binomial Coefficient Inequality

I don't know how to prove this inequality $$ \binom{n}{0} < \binom{n}{1} < \binom{n}{2}< ... <\binom{n}{\left \lfloor {\frac{n}{2}}\right \rfloor} $$ Knowing that $$ ...
1
vote
1answer
36 views

Cardinality of the set $\{(X_1,X_2,\cdots,X_p)\in \mathcal{P}(E)^p \mid X_1\subset\cdots\subset X_p \}$

If $|E|=n$ is a set, what is the cardinality of the set $$\{(X_1,X_2,\cdots,X_p)\in \mathcal{P}(E)^p \mid X_1\subset\cdots\subset X_p \}$$ My thoughts The giving of p-tuplets ...
6
votes
3answers
78 views

The greatest integer less than or equal to the number $R=(8+3\sqrt{7})^{20}$

Given $$R=(8+3\sqrt{7})^{20}, $$ if $\lfloor R \rfloor$ is Greatest integer less than or equal to $R$, then which of the following option(s) is/are true? $\lfloor R \rfloor$ is an even ...
2
votes
2answers
59 views

What is the $x^8$ term in $(x+\frac{1}{\sqrt[3]{x}})^5(2x - \frac{1}{x^2})^7$?

What is the $x^8$ term in $$(x+\frac{1}{\sqrt[3]{x}})^5(2x - \frac{1}{x^2})^7$$? I know how to expand $(a+b)^n$ via Newtons binome, but I can't find an elegant way of determining the $x^8$ term ...
2
votes
1answer
49 views

Sum of Series of Binomial Coefficients.

Find the sum of $\binom{200k}{0}+\binom{200k}{100}+\binom{200k}{200}+...+\binom{200k}{200k}$ and $\binom{200k}{1}+\binom{200k}{101}+\binom{200k}{201}+...+\binom{200k}{200k-99}$ in terms of $k$. I've ...
1
vote
0answers
32 views

For what values of $n$ do more than two thirds of subsets of $[n]$ have size beteen $\frac{n}{3}$ and $\frac{2n}{3}$

My actual problem is slightly different. For what values of $n$ do we have: $2\sum_{i=1}^{\lfloor n/3 \rfloor}\binom{n}{i}\geq \sum\limits_{i=\lfloor n/3 \rfloor+1}^{\lceil n/2 \rceil-1} ...
4
votes
2answers
96 views

Finding the infinite series: $\sum_{m=0}^\infty\sum_{n=0}^\infty\frac{m!\:n!}{(m+n+2)!}$

Evaluating $$\sum_{m=0}^\infty \sum_{n=0}^\infty\frac{m!n!}{(m+n+2)!}$$ involving binomial coefficients. My attempt: $$\frac{1}{(m+1)(n+1)}\sum_{m=0}^\infty ...
2
votes
1answer
54 views

Supercongruence for Binomial Coefficients

$${p^{e+1} \choose p\cdot k } \equiv {p^{e} \choose k } \mod p^{e+1} $$ $p$ is prime, $e$ and $k$ are non negative integers. I am struggling with a proof of the above proposition, in the ...
0
votes
1answer
64 views

Proving Singmaster's Conjecture: Can you prove there are finitely many solutions of $\binom{n+x-1}{n}=y$?

$n,x,y \in\mathbb{N}, \binom{n+x-1}{n}=y$ I am completely out of my depth. What I am really asking is how can you prove there is an upper bound on the number of pairs (n, x) to satisfy an arbitrary ...
6
votes
1answer
83 views

Binomial sum gives $4^n$

I was looking at this question:Swapping the $i$th largest card between $2$ hands of cards and WolframAlpha gave me this result. Why is it so? $$\sum_{k=0}^n{2k\choose k}{2n-2k\choose n-k}=4^n?$$
0
votes
0answers
27 views

Is there a name for this discrete version of Jensen, specifically when applied to binomial coefficients?

We have $2k$ integers greater than or equal to $j\geq0$ $a_1+a_2+\dots + a_k=n$ and $b_1+b_2+\dots + b_k=n$. If for all $1\leq i\leq k$ we have $|n/k-a_i|\leq|n/k-b_i|$. Then ...
1
vote
4answers
98 views

Find the minimal $n$ between $1$ and $2015$ such that $\binom{2015}{n}$ is even

I would appreciate if somebody could help me with the following problem Q: Find minimum $n(n\in \{1,2,3,4,\cdots,2015\})$, following holds $$\binom{2015}{n}: \text{is even number}$$
2
votes
2answers
42 views

Sum of binomial coefficients $\sum_{n=0}^6 \binom{6}{n} = 2^6$

I assume this is a rather simple result, but I am not sure how to arrive at it. Apparently: $$\sum_{n=0}^6 \binom{6}{n} = 2^6$$ I can sum over all the binomial coefficients and verify this of ...
0
votes
1answer
32 views

Proof of Binomial Coefficients Comparison Inequality

Please help to prove the inequality $$ \binom{a}{b}\leq\binom{a+j}{b+i}$$ For $i\leq j$ Using the basic identity $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ I have proceeded to $$ 1 \leq ...
1
vote
1answer
32 views

Hockey-Stick Theorem for Multinomial Coefficients

Pascal's triangle has this famous hockey stick identity. $$ \binom{n+k+1}{k}=\sum_{j=0}^k \binom{n+j}{j}$$ Wonder what would be the form for multinomial coefficients?
4
votes
0answers
54 views

Proof of inequality involving binomial coefficients

Proving things is not my forte. Stumbled upon following identity: $$\binom{n+k+1}{k}>\sum_{i=1}^k \binom{\alpha_i}{i}$$ For $\alpha_i<\alpha_j $ for $i<j$ $0\leq \alpha_i \leq n+k$ Also ...
3
votes
0answers
38 views

Is there a closed form for $n^k$ in terms of $\Delta n^{k+1},\Delta n^k$, …?

Let $\Delta$ be a sort of difference operator on a function $f(n)$ such that $$\Delta f(n)=f(n+1)-f(n)$$ Take the basic power function $f(n)=n^k$, $k\in\mathbb{N}\cup\{0\}$. Then we get ...
1
vote
0answers
25 views

Asymptotic behaviour of generalized binomial coefficient $\frac{an(an-1)…(an-n+1)}{n!}$

Let $a\in(0,1)$. What is the asymptotic behaviour of $\frac{an(an-1)...(an-n+1)}{n!}$ as $n\rightarrow\infty$? It looks like it might be possible to express this in terms of gamma functions and use ...
11
votes
1answer
170 views

Curious combinatorial summation

Let $\gamma$ denote a grid walk from the upper left corner $(1,k)$ to the lower right corner $(\ell,1)$ of the $k\times\ell$ rectangle $\{1,..,k\}\times\{1,..,\ell\}$. There are ...
4
votes
0answers
46 views

Product of two binomial coefficients in terms of linear combinations of binomial coefficients [duplicate]

For $n,a,b$ natural numbers with $a+b \leq n$, can we find positive rational numbers $c_1, \ldots, c_{a+b}$ such that $$ {n \choose a}{n \choose b} = \sum_{k=1}^{a+b}c_k{n \choose k}? $$ Is there a ...
5
votes
5answers
91 views

Prove that $\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m+k}{r}=0$

It is well-known that $\sum_{k=0}^n(-1)^k\binom{n}{k}=(1-1)^n=0$. It is seems like that $$\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{m+k}{r}=0$$ for any $m,r\in\mathbb{N}$, $r\leq m$. How to prove or ...
5
votes
1answer
57 views

Infinite summation of reciprocal of Binomial coefficients [duplicate]

When I was playing with Binomial coefficients. I got an interesting problem. It is very nice formula. The problem is $$\large \sum_{n=0}^{\infty} \dfrac{1}{\binom{2n}{n}}$$ where $\binom{2n}{n}$ ...
1
vote
3answers
51 views

Prove that : $\sqrt C_1+\sqrt C_2 +\sqrt C_3 \ … +\sqrt C_n \leq \sqrt{n(2^n-1)}$

If $ C_0, C_1 , C_2, ... , C_n$ are the combinatorial coefficients in the expansion of $(1 +x)^n$, $n\in N$, then prove the following :$$\sqrt C_1+\sqrt C_2 +\sqrt C_3 \ ... +\sqrt C_n \leq ...
0
votes
3answers
101 views

A sum related to binomial theorem

If $\dfrac{x^2+x+1}{1-x} = a_0+a_1x+a_2x^2+\cdots$ then $\displaystyle\sum_{\gamma = 1}^{50}a_{\gamma} = ??$ Original Image This is a sum related to evaluating a series, from the chapter ...
6
votes
0answers
97 views

A combinatorial identity involving generalized harmonic numbers

The $n$-th harmonic number is defined as $$ H_n=\sum_{k=1}^{n}\frac{1}{k}, $$ and the generalized harmonic numbers are defined by $$ H_{n}^{(r)}=\sum_{k=1}^{n}\frac{1}{k^r}. $$ Recently, I have found ...
1
vote
1answer
62 views

How do you evaluate this summation: $S=\sum\limits_{r=0}^{15} (-1)^r \frac{\binom{15}{r}}{\binom{r+3}{r}}$

Find S: $$S=\sum_{r=0}^{15} (-1)^r \frac{\binom{15}{r}}{\binom{r+3}{r}}$$ My attempt: I tried writing the summation as: $$S=3!(15!)\sum_{r=0}^{15} (-1)^r \frac{1}{(15-r)!(r+3)!}$$ and tried to ...
8
votes
5answers
355 views

An interesting Sum involving Binomial Coefficients

How would you evaluate $$\sum _{ k=1 }^{ n } k\left( \begin{matrix} 2n \\ n+k \end{matrix} \right) $$ I tried using Vandermonde identity but I can't seem to nail it down.
1
vote
1answer
63 views

generalized binomial coefficient

I know that the coefficient $$-\frac{1}{2} \choose k$$ can be simplified by multiplying both the nominator and the denominator by $$2^k$$ and then represented as $$ (-\frac{1}{4})^k {2k\choose k}$$ ...