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)

3
votes
1answer
478 views

Three problems with binomial coefficients

I found three difficult problems for me, involving binomial coefficients. They are extremely interesting I think, but I don't know if I have enough knowledge to manage. Seem really hard, can you help ...
5
votes
4answers
943 views

Alternating sum of binomial coefficients

Calculate the sum: $$ \sum_{k=0}^n (-1)^k {n+1\choose k+1} $$ I don't know if I'm so tired or what, but I can't calculate this sum. The result is supposed to be $1$ but I always get ...
3
votes
0answers
174 views

Prove: $\frac{(2px)!}{((px)!)^2}\equiv\frac{(2x)!}{((x)!)^2}\pmod{p^2}$

How can I prove the following, where $p$ is a prime and $x$ a positive integer? $$\dfrac{(2px)!}{((px)!)^2}\equiv\dfrac{(2x)!}{((x)!)^2}\pmod{p^2}$$ I'm not sure if it is actually true, but I tested ...
2
votes
2answers
367 views

Does this qualify as a proof? (Spivak's 'Calculus')

I'm working through Spivak's 'Calculus' at the moment, and a question about series confused me a bit. I think I have the solution, but I'm not sure if my "proof" holds. The question is: Prove ...
2
votes
1answer
343 views

Going from binomial distribution to Poisson distribution

Why does the Poisson distribution $$\!f(k; \lambda)= \Pr(X=k)= \frac{\lambda^k \exp{(-\lambda})}{k!}$$ contain the exponential function $\exp$, while its relation to the binomial distribution would ...
0
votes
1answer
589 views

Multi binomial theorem application

If i have the polynomial expression $(a_1x+b_1y+c_1)^p. (a_2x+a_2y+c_2)^d$, and with assumptions $a_1+b_1<<c_1$ , $a_2+b_2<<c_2$, can i expand this as a product of binomials using the ...
12
votes
2answers
339 views

A binomial identity

I was wandering if someone knows an elementary proof of the following identity: $$ \frac{(a)_n (b)_n}{(n!)^2} = \sum_{k=0}^n (-1)^k {1-a-b \choose k} \frac{(1-a)_{n-k}(1-b)_{n-k}}{((n-k)!)^2}\ , $$ ...
3
votes
4answers
279 views

Computing a sum of binomial coefficients

Does anyone know a better expression than the current one for this sum? $$ \sum_{i=0}^m \binom{N-i}{m-i}, \quad 0 \le m \le N. $$ It would help me compute a lot of things and make equations a lot ...
2
votes
0answers
193 views

Ways to think about the binomial coefficient

Just to sharpen my intuition in combinatorics, I ask you of ways to think about interesting combinatorical quantities and expressions like the binomial coefficient, for example, for the binomial ...
7
votes
1answer
436 views

Combinatorial Interpretation of Fractional Binomial Coefficients

My question is a bit imprecise - but I hope you like it. I even strongly think it has a proper answer. The binomial coefficient $\binom{\frac{1}{2}}{n}$ is strongly related to Catalan numbers - the ...
2
votes
2answers
151 views

How to prove this combinatorial summation?

How to prove this combinatorial summation? I expanded $C(m, i)$ and $C(n-1, n-i)$ and clubbed them together but it didn't yield anything useful. Please show me the approach only. Is this the ...
19
votes
1answer
2k views

A proof of Wolstenholme's theorem

This was inspired by this question. I tried to use the identity $${2n \choose n}=\sum_{k=0}^n {n \choose k}^2$$ (see this question) to prove that $$\binom{2p}p\equiv2\pmod{p^3}$$ if $p\gt3$ is ...
4
votes
0answers
163 views

How to transform series of series into series

I need to prove this equation. $$ \sum_{k=0}^{i-2} \left( e \space α(k+1)\space\frac{(-1)^{i+k+2}}{(i-k-2)!} \right) = \sum_{k=0}^{i-2} \frac{(i-k)^k}{k!} \space e^{i-k} (-1)^k\space where,\space α(i) ...
0
votes
1answer
278 views

Fibonacci sequence, strings without 00, and binomial coefficient sums [duplicate]

Refer to the sequence $S$ where $S_n$ denotes the number of n-bit strings that do not contain the pattern 00. By considering the number of n-bit strings with exactly i 0's, show that $\displaystyle ...
6
votes
4answers
913 views

Fractional Binomial Coefficients

I recently examined the binomial coefficient $\binom{\frac{1}{2}}{k}$ and found that the denominator was always a power of two. The same is true of $\binom{\frac{1}{3}}{k}$, where the denominator is ...
2
votes
0answers
270 views

Sum involving integer compositions and binomial coefficients

I came across an interesting identity involving binomial coefficients. I'm not sure if I'm looking at the identity the wrong way but I am not aware if this identity is known and if there is an (easy) ...
1
vote
1answer
74 views

Does $k$-th power of $p$ divide ${}_n\!C_r$ if the previous divides $n$?

Does $p^k$ divide ${}_n\!C_r$ for all integer r if $p^k|n$ where $0\leq r \leq n$ and $p$ is prime?
1
vote
1answer
146 views

Help with binomial theorem related proof

I'm currently working through Spivak on my own. I'm stuck on this proof, and the answer key is extremely vague on this problem. I think I'm missing a manipulation involving sums. Prove that ...
5
votes
3answers
357 views

Fraction of two binomial coefficients

In an exercise I was asked to simplify a term containing the following fraction: $${\binom{m}{k}\over\binom{n}{k}}$$ The solution does assume the following is true in the first step, without ...
7
votes
2answers
225 views

Find the sum of this series :$ \frac{1}{{1!2009!}} + \frac{1}{{3!2007!}} + \cdots + \frac{1}{{1!2009!}}$

Find the sum of this series : $$\sum\limits_{\scriptstyle 1 \leqslant x \leqslant 2009 \atop {\scriptstyle x+y=2010 \atop \scriptstyle {\text{ }}x,y{\text{ odd}} }} {\frac{1}{{x!y!}}} = ...
4
votes
4answers
326 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 ...
2
votes
3answers
55 views

combinatorics counting sets with a one element having values in another set

counting the number of ordered subsets in a n-set is easy, it's $ 2 ^n -1 $ (assuming we don"t want the empty subset, it's the sum of $ n \choose i $ , i>0 now imagine I have a set s=(a, b, x), where ...
5
votes
1answer
705 views

Prove that Pascals triangle contains only natural numbers, using induction.

I'm currently working my way through Spivak, and I'm stuck on the following. Prove that Pascals triangle only contains natural numbers using induction and the following relation: $\left( ...
2
votes
1answer
309 views

Using the Multinomial Theorem to Calculate a Finite Sum raised to an exponent

I know it's a simple question, but I keep getting different general formulas for the coefficients when I am trying to use the multinomial theorem for the following: $$ ...
3
votes
1answer
1k views

Multiplication of Two Infinite Series

This question has been deleted. How to prove that $$\displaystyle \left( \sum_{k=0}^{\infty }\frac{\left( -a\right) ^{k}y^{2k}}{k!}\right) \left( \sum_{k=0}^{\infty }\frac{a^{k}y^{2k+1}}{\left( ...
1
vote
1answer
448 views

Using binomial theorem find general formula for the coefficients

Using binomial thaorem (http://en.wikipedia.org/wiki/Binomial_theorem) find the general formula for the coefficients of the expantion: $$ ...
3
votes
0answers
258 views

Sums of rows in the Pascal triangle

Assume for simplicity that when $k>n$ we have ${n\choose k}=0$. It is well-known that $\sum_k {n\choose 2k}=\sum_k {n\choose 2k+1}=2^{n-1}$ , i.e. the sum of the odd places in each row in Pascal's ...
20
votes
0answers
752 views

$f(x)=\sum_{t}{x \choose t}{n-x \choose k-t}$ - even or odd?

The following function popped in my research: $$f(x)=\sum_{\array{0\le t\le k \\ t\equiv_p a}}{x \choose t}{n-x \choose k-t}$$ Where: $n,k$ are natural numbers and $k\le n$. $t$ is taken over all ...
3
votes
1answer
91 views

is the approximation of the sum true?

Someone commented under my question Calculation of the moments using Hypergeometric distribution that $$ \sum_{k=0}^l\frac{{l \choose k}{2n-l \choose n-k}(2k-l)^q}{{2n\choose n}}\sim \sum_{k=0}^l ...
4
votes
2answers
459 views

Algebraic proof of a binomial sum identity.

I came across this identity when working with energy partitions of Einstein solids. I have a combinatorial proof, but I'm wondering if there exists an algebraic proof. $$\sum_{q=0}^N\binom{m + q - ...
4
votes
2answers
487 views

Proving ${p-1 \choose k}\equiv (-1)^{k}\pmod{p}: p \in \mathbb{P}$ [duplicate]

Possible Duplicate: Prove $\binom{p-1}{k} \equiv (-1)^k\pmod p$ The question is as follows: Let $p$ be prime. Show that ${p \choose k}\bmod{p}=0$, for $0 \lt k \lt p,\space ...
3
votes
2answers
374 views

how to visualize binomial theorem geometrically?

How does $ \binom{n}{k} $ 'n choose k' get involved with coefficient of $ (a+b)^n $. Is there any intuitive geometrical picture (interpretation) that it seems ...
8
votes
3answers
234 views

Putting ${n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ in a closed form

As the title says, I'm trying to transform $\displaystyle{n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ into a closed form. My work: $\displaystyle\left(1 + ...
11
votes
3answers
342 views

Computing: $\lim\limits_{n\to\infty}\left(\prod\limits_{k=1}^{n} \binom{n}{k}\right)^\frac{1}{n}$

I try to compute the following limit: $$\lim_{n\to\infty}\left(\prod_{k=1}^{n} \binom{n}{k}\right)^\frac{1}{n}$$ I'm interested in finding some reasonable ways of solving the limit. I don't find any ...
7
votes
1answer
331 views

Asymptotics for sum of binomial coefficients from Concrete Mathematics

Concrete Mathematics EXERCISE 9.25: Supposing \[ S_n = \sum_{k=0}^n \binom{3n}k \] Prove that \[ S_n = \binom{3n}{n}\left(2-\frac4n+O\left(\frac1{n^2}\right)\right) \] This sequence also ...
2
votes
1answer
328 views

Proving a function satisfies the binomial recurrence relation and that it equals $\binom{n-k+1}{k}$

I have the recurrence relation $g(n,k)=g(n-2,k-1) + g(n-1,k)$ for all $k\geq1$ with the boundary conditions $g(n,k)=0$ if $n<2k-1$ and $g(2k-1,k)=1$ What I'm trying to do is define a new function ...
1
vote
0answers
63 views

calculation of the sum using idea of one answer

I am wondering if the sum (the $q$-th moment) in my question Calculation of the moments using Hypergeometric distribution can be calculated using idea in Evaluating 'combinatorial' sum ? ...
5
votes
1answer
653 views

Calculation of the moments using Hypergeometric distribution

Let vector $a\in 2n $ is such that first $l$ of its coordinates are $1$ and the rest are $0$ ($a=(1,\ldots, 1,0, \ldots, 0)$). Let $\pi$ be $k$-th permutation of set $\{1, \ldots, 2n\}$. Define ...
15
votes
5answers
486 views

Sum with binomial coefficients: $\sum_{k=1}^m \frac{1}{k}{m \choose k} $

I got this sum, in some work related to another question: $$S_m=\sum_{k=1}^m \frac{1}{k}{m \choose k} $$ Are there any known results about this (bounds, asymptotics)?
6
votes
2answers
166 views

Binomial transform of a scaled version of the catalan numbers.

I was looking at the mathworld entry for Catalan Numbers http://mathworld.wolfram.com/CatalanNumber.html and was surprised to find formula (11) there: (1) $C_n= \sum_{k=0}^n (-1)^k ...
0
votes
2answers
103 views

Help with $1 + a + a(a-1) + a(a-1) (a-2) +\cdots+a(a-1)\cdots(a-(n-1))$

I want to rewrite the series $$1 + a + a(a-1) + a(a-1) (a-2) +\cdots+a(a-1)\cdots(a-(n-1))$$ as $(a^n-1)Y$ or $(a^{n-1}-1)Y$ Short-form: $$\{1+\sum_{i=1}^{n} \prod_{j=0}^{i-1}(a-j)\}$$ as $(a^n-1)Y$ ...
11
votes
2answers
282 views

The Fermat prime 257 and binomial sum $\sum_{n=0}^\infty \frac{(-1)^n}{\binom {8n}{4n}}$?

We have, $\begin{aligned} \sum_{n=0}^\infty \frac{(-1)^n}{\binom n{n/2}} &= \frac{4}{27}(9-\pi\sqrt{3}\,)\\[2.5mm] \sum_{n=0}^\infty \frac{(-1)^n}{\binom {2n}n} &= \frac{4}{5} - ...
1
vote
2answers
55 views

Integer sequence comparison, binomials Vs power

I need to know which sequence grows faster with n: $$ f(n) = \sum_0^{floor(n/3)} {n \choose 3*i+1} $$ compared to $$ g(n) = 2^n -1 $$ it seems f(10)>5000 is greater than g(10)=1023 but I would ...
3
votes
2answers
236 views

simplify $(a_1 + a_2 +a_3+… +a_n)^m$

How to simplify this best $(a_1 + a_2 +a_3+... +a_n)^m$ for $m=n, m<n, m>n$ I could only get $\sum_{i=0}^{m}\binom{m}{i}a_i^i\sum_{j=0}^{m-i}\binom{m-i}{j}a_j ... $
1
vote
2answers
522 views

Binomial coefficients upper bound

It's trivial to show that $\binom{n}{k} \leq 2^n$. I'm trying to find a smallest constant $c$ such that $\binom{n}{k} \leq c \frac{2^n}{n}$.
3
votes
0answers
201 views

Is this formula for $\zeta(15)$ true?

Apery gave, $\begin{aligned} \zeta(3) &= \frac{5}{2}\,\sum_{k=1}^\infty \frac{(-1)^{k+1}}{k^3\,\binom {2k}k}\end{aligned}$ J. Borwein and D. Bradley found this can be generalized to ...
2
votes
2answers
669 views

Identity to simplify sum with binomial coefficient

This is the homework, and it shouldn't be difficult, but I can't find the proper identity that would help me simplify the below: $ \displaystyle \sum_{n=0}^m \frac{1}{n+1}\binom{m}{n}$. Through ...
3
votes
1answer
542 views

Binomial fraction sum to infinity

Compute the limit: $$\lim_{n\to\infty} \sum_{k=0}^n \frac {\dbinom{n}{k}}{\dbinom{2n-1}{k}}$$ Here i tried to give some k values to the sum hoping to see a possible pattern, but i didn't figure out ...
3
votes
2answers
149 views

Combinations and Gaussian function

I notice that the function $\binom{C}{x}$, where $C$ is some constant, resembles a Gaussian function; for example, here is the plot for $\binom{20}{x}$: This corresponds to the Gaussian function $a ...
0
votes
3answers
163 views

Binomial expansion and factorials

I have come across this question, the answer is simply stated as 36, and while I can see how 36 is gotten, I don't understand why? How is it meant to be known that b = 36, just looking at the ...