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
4answers
163 views

Evaluating Sums Algebraically or Combinatorially

Consider (1) $$\sum_{k=0}^{n}\binom{n}{k}2^{k-n}$$ (2) $$\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}$$ These sums appear too difficult (in my mind) to evaluate combinatorially. What are some ...
4
votes
3answers
291 views

matrix representations and polynomials

I just investigated the following matrix and some of its lower powers: $${\bf M} = \left[\begin{array}{cccc} 1&0&0&0\\ 1&1&0&0\\ 1&1&1&0\\ 1&1&1&1 \end{...
4
votes
5answers
294 views

Binomial coefficients in Geometric summation

Guys please help me find the sum given below. $$\sum_{k=j}^i\binom{i}{k}\binom{k}{j}\cdot 2^{k-j}$$ (NOTE):The two coefficients are multiplied by 2 power (k-j) I am using the formula: $\binom{r}{m}\...
4
votes
2answers
323 views

maybe this sum have approximation $\sum_{k=0}^{n}\binom{n}{k}^3\approx\frac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty$

prove or disprove this $$\sum_{k=0}^{n}\binom{n}{k}^3\approx\dfrac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty?$$ this problem is from when Find this limit $$\lim_{n\to\infty}\dfrac{\displaystyle\sum_{k=...
4
votes
2answers
12k views

Proving by induction that $ \sum_{k=0}^n{n \choose k} = 2^n$

Prove by induction that for all $n \ge 0$: $${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$ In the inductive step, use Pascal’s identity, which is: $${n+1 \choose k} = {n \choose k-1} ...
4
votes
4answers
175 views

Math nomenclature

I kinda feel ashamed about asking this, but could someone explain me what this means? $$ \binom{k}{i} $$ That should indicate the number of nodes at a certain depth in a binomial heap..but I can't ...
4
votes
4answers
87 views

Verify that $\sum^{8564}_{i=82} \binom{8564}{i} < 2^{8564}$

I have to tell if the following inequality is true: $$\sum^{8564}_{i=82} \binom{8564}{i} < 2^{8564}$$ but how do I tackle that? I reckon the standard formula for calculate the value of the ...
4
votes
3answers
181 views

Proving a binomial coefficient identity [duplicate]

I'm having some trouble with the following proof: $$\sum^k_{a=0} {{n}\choose{a}}{{m}\choose{k-a}} = {{n+m}\choose{k}}$$ I'm trying to prove this to learn a couple of things about the Pascal's ...
4
votes
2answers
125 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 \sum_{n=0}^\infty\frac{(m+1)!(n+1)!}{(m+...
4
votes
2answers
721 views

Why does $\sum\limits_{i=0}^k {k\choose i}=2^k$ [duplicate]

Possible Duplicate: Proving a special case of the binomial theorem Can anyone explain to me why $$\sum\limits_{i=0}^k {k\choose i}=2^k\,?$$ Thanks in advance
4
votes
4answers
194 views

How do I show that $\sum_{k = 0}^n \binom nk^2 = \binom {2n}n$? [duplicate]

$$\sum_{k = 0}^n \binom nk^2 = \binom {2n}n$$ I know how to "prove" it by interpretation (using the definition of binomial coefficients), but how do I actually prove it?
4
votes
3answers
155 views

Find the limit of $4^n\cdot\binom{2n}{n}/\binom{4n}{2n}$

I am trying to prove that $$f(n)=4^n\frac{\dbinom{2n}{n}}{\dbinom{4n}{2n}}$$ converges as $n\rightarrow\infty$. I have already tried to use the fact that, if $n, k \in\mathbb{N}, n\geq k\geq1,$ then $...
4
votes
2answers
71 views

Binomial Coefficients Combinatorics

For a positive integers n, prove that $$\displaystyle\sum\limits_{v=0}^n \frac{(2n)!}{(v!)^2 ((n-v)!)^2} = \binom{2n}{n}^2.$$ If somebody could please help me with this question, I would greatly ...
4
votes
4answers
397 views

${10 \choose 4}+{11 \choose 4}+{12 \choose 4}+\cdots+{20 \choose 4}$ can be simplified as which of the following?

${10 \choose 4}+{11 \choose 4}+{12 \choose 4}+\cdots+{20 \choose 4}$ can be simplified as ? A. ${21 \choose 5}$ B. ${20 \choose 5}-{11 \choose 4}$ C. ${21 \choose 5}-{10 \choose 5}$ D. ${20 \...
4
votes
3answers
106 views

What is the sum $\sum_{k=0}^{n}k^2\binom{n}{k}$? [duplicate]

What should be the strategy to find $$\sum_{k=0}^{n}k^2\binom{n}{k}$$ Can this be done by making a series of $x$ and integrating?
4
votes
2answers
1k views

Prove by Combinatorial Argument that $\binom{n}{k}= \frac{n}{k} \binom{n-1}{k-1}$

This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides ...
4
votes
3answers
158 views

Property of a polynomial $f\in\mathbb{Q}[X]$ such that $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$?

We can always view $\binom{x}{k}$ as a polynomial in $x$ of degree $k$. With this in mind, why is it so that a polynomial $f\in\mathbb{Q}[x]$ is such that $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$ ...
4
votes
3answers
248 views

Combinatorial proof of $\binom{n}{k} = \binom{n}{n-k}$

How do I prove this combinatorially? $$\displaystyle \binom{n}{k} = \binom{n}{n-k}$$
4
votes
3answers
79 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}$$
4
votes
5answers
278 views

Curious Binomial Coefficient Identity

Consider the following set of identities: ${m+1\choose 1}={m\choose 1}+1$, ${m+1\choose 2}=2\binom m 2 - {m-1\choose 2}+1$, ${m+1\choose 3}=3\binom m3-3{m-1\choose 3}+{m-2\choose 3}+1$, ... This set ...
4
votes
4answers
112 views

Solve for $n$, where $n$ is a positive integer

I have $$ {n \choose 2} = 21 $$ and as the title mentions I have to solve for $n$, but so far all I have managed to get to is $$n^2 -n =42 $$ and from there I'm completely lost. Any hints would ...
4
votes
1answer
241 views

Binomial Summation

The sum $$ 1 + {n \choose 1}\cos \theta + {n \choose 2}\cos 2\theta + \cdots+ {n \choose n}\cos n\theta $$ is? I try to write this as the real part of $(1 + \cos \theta + i\sin \theta)^n$ but then I'...
4
votes
3answers
149 views

Find a simple formula for

$$\binom{n}{0}\binom{n}{1}+\binom{n}{1}\binom{n}{2}+...+\binom{n}{n-1}\binom{n}{n}$$ All I could think of so far is to turn this expression into a sum. But that does not necessarily simplify the ...
4
votes
2answers
3k views

Choosing a 5 member team out of 12 girls and 10 boys

We must choose a 5-member team from 12 girls and 10 boys. How many ways are there to make the choice so that there are no more than 3 boys on the team? The correct answer is $\binom{22}{5} - \binom{...
4
votes
2answers
343 views

Combinatorial Proof for a $ p\mid\binom{p}{k} \ \ \ \ \ 0<k<p$ .

I'm looking for a combinatorial proof to the following statement: $$ p\mid\binom{p}{k} \ \ \ , \ \ 0<k<p \ \ \ \ \ \ \text{and} \ \ p \ \text{is prime}.$$ Thank you.
4
votes
2answers
1k views

Factorial division using Pascal's triangle.

I want to get values of factorial divisions such as 100!/(2!5!60!)(the numbers in the denominator will all be smaller than the numerator, and the sum of the ...
4
votes
2answers
42 views

Trouble understanding how this identity is derived: $\sum_{j=0}^{\infty}\binom{a+j}{j}x^j=(1-x)^{-a-1}$

$$\sum_{j=0}^{\infty}\binom{a+j}{j}x^j=(1-x)^{-a-1}$$ The $-a-1$ is throwing me off. Can anyone help me understand this identity. I have tried letting $m=-a-1$ and then applying the binomial theorem,...
4
votes
3answers
135 views

Showing ${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}$

Prove that for integers $n \geq 0$ and $a \geq 1$, $${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}.$$ I figured I'd post this question, ...
4
votes
2answers
142 views

What does $\lim \limits_{n\rightarrow \infty }\sum \limits_{k=0}^{n} {n \choose k}^{-1}$ converge to (if it converges)? [duplicate]

How we can show if the sum of $$\lim_{n\rightarrow \infty }\sum_{k=0}^{n} \frac{1}{{n \choose k}}$$ converges and then find the result of the sum if it converges? Thanks for any help.
4
votes
4answers
142 views

A binomial inequality with factorial fractions

Prove that $$\left(1+\frac{1}{n}\right)^n<\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+...+\frac{1}{n!}$$ for $n>1 , n \in \mathbb{N}$.
4
votes
3answers
698 views

No closed form for the partial sum of ${n\choose k}$ for $k \le K$?

In Concrete Mathematics, the authors state that there is no closed form for $$\sum_{k\le K}{n\choose k}.$$ This is stated shortly after the statement of (5.17) in section 5.1 (2nd edition of the book)....
4
votes
3answers
448 views

Combinatorial proof for $\binom{n}{a}\binom{a}{k}\binom{n-a}{b-k} = \binom{n}{b}\binom{b}{k}\binom{n-b}{a-k}$?

I have to prove the following using a combinatorial proof: $\binom{n}{a}\binom{a}{k}\binom{n-a}{b-k} = \binom{n}{b}\binom{b}{k}\binom{n-b}{a-k}$ Ok, so here is what I have worked out so far: We ...
4
votes
3answers
2k views

Combination problem with constraints

You have four containers and one pitcher of water that holds 100L. Each container has different capacities with maximums of, say...70L, 45L, 33L and 11L levels respectively. What is the formula that ...
4
votes
2answers
6k views

Number of even and odd subsets [duplicate]

Suppose we have the following two identities: $\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$ $\displaystyle \sum_{k=0}^{n} (-1)^{k} \binom{n}{k} = 0$ The first says that the number of subsets ...
4
votes
2answers
39 views

Let $f(n)=\sum_{r=0}^{n}\sum_{k=r}^{n}\binom{k}{r}$.If $f(n)=2047,$ then find the value of $n.$

Let $f(n)=\sum_{r=0}^{n}\sum_{k=r}^{n}\binom{k}{r}$.If $f(n)=2047,$ then find the value of $n.$ $f(n)=\sum_{r=0}^{n}\sum_{k=r}^{n}\binom{k}{r}=\sum_{k=0}^{n}\binom{k}{0}+\sum_{k=1}^{n}\binom{k}{1}+\...
4
votes
3answers
86 views

How to derive this binomial identity?

I believe the following is an identity (I've tested with a few random $m$ and $n$ values, could be wrong though): $$\sum_{k= 0}^{\infty}{m \choose k}{n \choose k}k=n\binom{m+n-1}{m-1}$$ but I'm not ...
4
votes
2answers
139 views

Roots of a polynomial whose coefficients are ratios of binomial coefficients

Prove that $\left\{\cot^2\left(\dfrac{k\pi}{2n+1}\right)\right\}_{k=1}^{n}$ are the roots of the equation $$x^n-\dfrac{\dbinom{2n+1}{3}}{\dbinom{2n+1}{1}}x^{n-1} + \dfrac{\dbinom{2n+1}{5}}{\...
4
votes
4answers
201 views

What is the story behind ${n+1 \choose k} = {n \choose k} + {n \choose k-1}$? [duplicate]

By exploring the inductive proof from this question I came to the point where I did not understand this step: $${n+1 \choose k} = {n \choose k} + {n \choose k-1}$$ There is a wikipedia article but ...
4
votes
4answers
84 views

Proof $\displaystyle \binom{p-1}{k}\equiv (-1)^k \mod{p}$

Proof that if $p$ is a prime odd and $k$ is a integer such that $1≤k≤p-1$ , then the binomial coefficient $$\displaystyle \binom{p-1}{k}\equiv (-1)^k \mod p$$ This exercise was on a test and I could ...
4
votes
3answers
718 views

Integral with binomial coefficient

Is it possible to evaluate this integral without using the gamma function $$ \int_0^1 {a \choose b}x^b(1-x)^{a-b} dx$$ It looks a little like part of binomial theorem, but I don't have an idea how to ...
4
votes
4answers
127 views

How can I find $\sum\limits_{n=i+1}^\infty \binom{n-1}{i}\left (\frac{1}{3}\right)^{n}$?

In a probability proof I've arrived at the sum $\sum\limits_{n=i+1}^\infty \binom{n-1}{i} \left(\frac{1}{3}\right)^{n}$ where $i$ is constant. WolframAlpha gives a simple expression for this sum, but ...
4
votes
3answers
525 views

General Leibniz rule for triple products

I have a question regarding the General Leibniz rule which is the rule for the $n^{th}$ derivative of a product and reads: $$ (f g)^{(n)}=\sum_{k=0}^{n} {n \choose k} \,f^{(k)} g^{(n-k)}. $$ However,...
4
votes
3answers
713 views

Evaluate a sum with binomial coefficients: $\sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$

$$\text{Find} \ \ \sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$$ I expanded the binomial coefficients within the sum and got $$\binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \dots + \binom{n}{n}^2$$ ...
4
votes
2answers
142 views

Expression for power of a natural number in terms of binomial coefficients

Is there a general expression for the pth power of a natural number k in terms of binomial coefficients? I found this identity in a high-school text, which was obtained by simply equating ...
4
votes
3answers
572 views

Give the combinatorial proof of the identity $\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Given the identity $$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$ Need to give a combinatorial proof a) in terms of subsets b) by interpreting the parts in terms of compositions of ...
4
votes
2answers
205 views

Why does $\binom{10}{7} = \frac{10!}{(10-7)!7!}$

We just learned that: $\dbinom{10}{7}= \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4}{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}$, so that: If you throw a dice 10 ...
4
votes
2answers
480 views

lacunary sum of binomial coefficients

I am sure there must be a known estimate for sums of the form: $$ S_d(n)=\sum_{j=0}^n \binom{dn}{dj} $$ where $d\ge 1$. For $d=1$, the answer is obvious. For $d=2$, the answer is here: Sum with ...
4
votes
2answers
112 views

Binomials in associative algebras

Given any associative algebra $A$ over a field of characteristic zero, $x\in A$ and $k\in \mathbb Z_+$, set $\binom{x}{k} = \frac{x(x-1)\cdots(x-k+1)}{k!}$. It is not hard to see that is is still in $...
4
votes
3answers
134 views

$N^L$ vs. ${N+L\choose N}$

Any ideas on finding a good estimate/approximation for $A/B$ where $A = N^L$ and $B = {N+L\choose N}$?
4
votes
1answer
77 views

Prove that $\sum_{j=0}^{n}H_j{n\choose j}^2={2n\choose n}\left(2H_n-H_{2n}\right)$

Let $H_n$ the $n$th Harmonic numbers and $H_0=0.$ Prove that $$\sum_{j=0}^{n}H_j{n\choose j}^2={2n\choose n}\left(2H_n-H_{2n}\right)$$ I encounter this problem since 2012 and have verify ...