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)

2
votes
1answer
88 views

Simple problem on restricted partition

When finding number of ways to partition n distinct chocolates among m children such that each child has at most $$\left\{\begin{matrix} \left \lfloor \frac{n}{m} \right \rfloor & \text{if} \ \ ...
2
votes
0answers
125 views

Eliminating negative binomial coefficients

I have a sum $$\sum_{m=0}^{n}\sum_{j=0}^{k}(-1)^j{k \choose j}{n-mj \choose k}$$ that comes up when counting compositions. Now the trouble is, if I would interpret it literally and for $n<mj$ ...
1
vote
2answers
51 views

How to evaluate binomial coefficients when $k=0$ and $1\geq|n|\geq0$

So I am doing some taylor series which boil down to the geometric series, for which I then need to evaluate various binomial coefficients. I have always used $n\choose k$ $=\frac{n!}{(n-k)!k!}$ to do ...
3
votes
3answers
230 views

Stirling Binomial Polynomial

Let $\{\cdot\}$ denote Stirling Numbers of the second kind. Let $(\cdot)$ denote the usual binomial coefficients. It is known that $$\sum_{j=k}^n {n\choose j} \left\{\begin{matrix} j \\ k ...
4
votes
6answers
102 views

Is $\sum_{i=1}^{n-1}i=\binom{n}{2}$?

How can I show that $$ \sum_{i=1}^{n-1}i=\binom{n}{2}? $$ This is what I have tried, but I do not know if it is correct: Proof. Let $n=2$. Then, $$ \begin{align} \sum_{i=1}^{1}i&=1\text{, ...
5
votes
2answers
240 views

Show that the $k$th forward difference of $x^n$ is divisible by $k!$

Define the forward difference operator $$\Delta f(x) = f(x+1) - f(x)$$ I believe that if $f(x)$ is a polynomial with integer coefficients, $\Delta^k f(x)$ is divisible by k!. By linearity it suffices ...
3
votes
3answers
120 views

Find the coefficient using binomial theorem.

What is the coefficient of $x^{20}$ in the expression: $$(x+1)^{10}.(x^2 -1)^8$$
1
vote
1answer
108 views

Inverting an infinite sequence transformation

Consider a sequence $\{b_k\}$ define via: $$ b_k = \sum_{n=0}^\infty \frac{(n+k)!}{n!}a_n. $$ I would like to invert this transform. That is, I would like to know the coefficients $c_{nk}$ such that ...
5
votes
3answers
393 views

Dividing factorials is always integer

Is there a simple way to show that $$n!\over r!(n-r)!$$ is always an integer?
1
vote
2answers
2k views

Binomial Expansion Word Problem (Creating a Equation)

I was working on my math textbook (Nelson Functions 11) and came across the following word problem. This question is shown in the "Pascal's Triangle and Binomial Expansions" section of the book. ...
2
votes
2answers
40 views

Finding the correct statements about $(5+2\sqrt{6})^{2n+1} = S + t$ with $S$ integer and $0 \leq t < 1$

Problem: If $n$ is a positive integer and $(5+2\sqrt{6})^{2n+1} = S + t$, where $S$ is an integer and $0 \leq t < 1$, then (a) $S$ is an odd integer (b) $S + 1$ is not divisible by ...
3
votes
5answers
174 views

Can $\frac{n!}{(n-r)!r!}$ be simplified?

I'm trying to calculate in a program the number of possible unique subsets of a set of unique numbers, given the subset size, using the following formula: $\dfrac{n!}{(n-r)!r!}$ The trouble is, on ...
2
votes
1answer
131 views

What should be proved in the binomial theorem?

I'm following Cambrige mathematics syllabus, from the list of contents of what should be learned: Induction as a method of proof, including a proof of the binomial theorem with non-negative ...
4
votes
4answers
139 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}$.
11
votes
3answers
797 views

How to get ${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$

I found this in my test book, any hints? Given $${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$$ Then find the value of x and y in n. According to the answer ...
6
votes
4answers
1k views

Proving that ${n}\choose{k}$ $=$ ${n}\choose{n-k}$

I'm reading Lang's Undergraduate Analysis: Let ${n}\choose{k}$ denote the binomial coefficient, $${n\choose k}=\frac{n!}{k!(n-k)!}$$ where $n,k$ are integers $\geq0,0\leq k\leq n$, and ...
14
votes
1answer
424 views

Proof of $\sum_{n=1}^\infty \frac{1}{n^4 \binom{2n}{n}}=\frac{17\pi^4}{3240}$

Recently, I was able to prove that $$\sum_{n=1}^\infty \frac{1}{n \binom{2n}{n}}= \frac{\pi}{3\sqrt{3}}$$ $$\sum_{n=1}^\infty \frac{1}{n^2 \binom{2n}{n}}= \frac{\pi^2}{18}$$ But does anybody know ...
4
votes
0answers
92 views

Binomial coefficient sum over top index

I am trying to evaluate a sum over binomial coefficients which is giving me some problems. Specifically I want to calculate: $$\sum_{r=0}^{c-1}\binom{r+n}{n}\frac{1}{c-r}$$ My main thought was to ...
3
votes
4answers
192 views

Is $\sum\limits_{k=1}^{n-1}\binom{n}{k}x^{n-k}y^k$ always even?

Is $$ f(n,x,y)=\sum^{n-1}_{k=1}{n\choose k}x^{n-k}y^k,\qquad\qquad\forall~n>0~\text{and}~x,y\in\mathbb{Z}$$ always divisible by $2$?
3
votes
0answers
222 views

Proving identity involving sum

I'm stuck trying to prove the following identity: $$\displaystyle\sum_{i=j}^k\frac{(-1)^{i+j}{k+1 \choose i}{i \choose j}(4S-i-k-3)!(4S-2i-1)}{(4S-i-j-1)!} $$ $$=\frac{(-1)^{j+k}(4S-2k-3)!{k+1 ...
1
vote
2answers
82 views

Binomial coefficient series

I'm practicing for my maths term test mainly on binomial coefficients. I can't seem to find out how to prove the following identity. Any advice? $$ \sum\limits_{k=1}^n (-1)^{k+1} k{{n}\choose k} = 0 ...
5
votes
4answers
297 views

Proving $\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$

Prove that $$\sum_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$$ by computing the coefficient of $z^M$ in the identity $$(1 + z + z^2 + \cdots ) \cdot \frac{1}{(1-z)^{k+1}} = \frac1{(1-z)^{k+2}}.$$ I ...
1
vote
4answers
1k views

Evaluate a sum involving n choose r

Evaluate: $\sum_{k=0}^6 (-1)^k \binom{6}{k}$ where $\binom{n}{r}= \frac{n!}{r!(n-r)!}$. I'm unsure how to compute the part with $\binom{6}{k}$, it should be something along the lines of ...
4
votes
1answer
106 views

On a sum related to alternating sign matrices

I'm trying to prove that $$A_{n,k} = \binom{n+k-2}{k-1}\frac{(2n-k-1)!}{(n-k)!}\prod_{j=0}^{n-2}\frac{(3j+1)!}{(n+j)!}$$ implies $$A_n = \sum_{k=1}^nA_{n,k}=\prod_{j=0}^{n-1}\frac{(3j+1)!}{(n+j)!}.$$ ...
0
votes
1answer
86 views

Binomial sum of derivatives

I would like to know the result of the following sum: $$\sum_{p=0}^m \binom{m}{p}(-1)^{p-1}\frac{\partial^{p-1}}{\partial x^{p-1}}f(x)\cdot(-1)^{m-p-1}\frac{\partial^{m-p-1}}{\partial ...
3
votes
1answer
63 views

An equality involving binomial coefitients

I am wondering why formula $$\sum_{j=k}^n\binom{n}{j}(-1)^j = (-1)^k\binom{n-1}{k-1} $$ is correct only for $1<k<n+1$. Could it be extended to $0<k<n+1$? I found this formula here.
10
votes
6answers
207 views

A limit on binomial coefficients

Let $$x_n=\frac{1}{n^2}\sum_{k=0}^n \ln\left(n\atop k\right).$$ Find the limit of $x_n$. What I can do is just use Stolz formula. But I could not proceed.
0
votes
2answers
595 views

Some algebraic inequalities with the binomial theorem.

I am working on proving the following limits. 1), $\lim_{n \to \infty} \sqrt[n]{n} = 1$ 2), If $p >0$ and $\alpha \in \Bbb R$, then $\lim_{n \to \infty} {n^{\alpha}\over{(1+p)^n}} =0$ ...
1
vote
2answers
92 views

What is the function given by $\sum_{n=0}^\infty \binom{b+2n}{b+n} x^n$, where $b\ge 0$, $|x| <1$

For a nonnegative integer $b$, and $|x|<1$, what is the function given by the power series $$ \sum_{n=0}^\infty \binom{b+2n}{b+n} x^n. $$ For $b=0$, this post shows $$ \sum_{n=0}^\infty ...
5
votes
2answers
333 views

What's the intuition behind this equality involving combinatorics? [duplicate]

What is the intuition behind $$ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} $$ ? I can't grasp why picking a group of $k$ out of $n$ bijects to first picking a group of $k-1$ out of $n-1$ ...
4
votes
2answers
70 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 ...
0
votes
1answer
68 views

How to maximize $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?

Short Version of the Question: How do I maximize the value of $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$? Long Version of the Question: I'm currently attempting ...
0
votes
1answer
567 views

Sum of binomial probabilities

One of my friends is building a game where the player will get questions from 6 different categories. Each category has a total of 50 questions. A single game consists of answering one question from ...
8
votes
4answers
169 views

A binomial identity from Mathematical Reflections

Here is the problem: Let $m,n$ be positive integers with $n>m$. Prove that $\displaystyle\sum_{k=0}^{\lfloor\frac{n+m}2\rfloor} (-1)^{k}\binom{n}{k}\binom{m+n-2k}{n-1}=\binom{n}{m+1}$ This ...
3
votes
2answers
165 views

Distribution of $n$ balls to 10 cells; Inclusion-exclusion problem

So I got another ( :[ ) problem I got stuck with. So before I get going with that, I would like to know if you know any places where I can learn the principles of these subjects (compositions, ...
1
vote
3answers
156 views

Proof that $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1} = \frac{2^{m+1}-1}{m+1}$ [duplicate]

Recently I needed to compute $E[\frac{1}{X+1}]$ where $X\sim Bin(m, \frac 1 2)$. While expanding, I came across the sum $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1}$, which I was unable to solve. Plugging ...
7
votes
4answers
341 views

Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$

I just found this identity but without any proof, could you just give me an hint how I could prove it? $$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$ I know that $$2^n = ...
4
votes
3answers
533 views

Counting the numbers between $1$ and $1,000,000$ whose digits sum to $30$

What's the number of numbers between $1$ and $1,000,000$ whose digits sum is $30$? So I thought of this as a stars and sticks problem, so in the case you have $35\choose 5$ numbers whose sum is ...
13
votes
3answers
2k views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
2
votes
1answer
529 views

Proving an identity with a combinatorial proof

For any integers $n$, $k$, $r$ where $n\geq k\geq r \geq 0$, give a combinatorial proof of the following identity: $$\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$$ The problem is that I ...
6
votes
2answers
354 views

Binomial probability with summation

Show that $$\sum_{k=0}^{m} \frac{m!(n-k)!}{n!(m-k)!} = \frac{n+1}{n-m+1}$$ Attempt: It becomes: $$\sum_{k=0}^{m } \frac{\binom{m}{k}}{\binom{n}{k}}$$ Telescoping, pairing, binomial theorem don't ...
4
votes
3answers
662 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$$ ...
9
votes
3answers
225 views

A sum with binomial coefficients

Show that $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-2k)^{n+2}=\frac{2^{n}n(n+2)!}{6}.$$
2
votes
3answers
178 views

Factorial Equality Problem

I'm stuck on this problem, any help would be appreciated. Find all $n \in \mathbb{Z}$ which satisfy the following equation: $${12 \choose n} = \binom{12}{n-2}$$ I have tried to put each of them ...
1
vote
0answers
98 views

Binomial Expansion problem error

I tried solving this question but failed. a) Expand $(1+2x)^{1/4}$ in ascending powers of $x$ up to and including the term in $x^3$, simplifying each term as far as possible. b) By substituting ...
4
votes
1answer
93 views

Binomial theorem for prime exponent

Could you explain to me why for prime $p$ we have the following? $$(x+y)^p - (x^p + y^p)= x^p + \binom{p}{1}x^{p-1}y + \binom{p}{2}x^{p-2}y^2 + \binom{p}{p-1}xy^{p-1} + y^p.$$ I found it here: ...
2
votes
0answers
328 views

Prime numbers with binomial coefficients

Let $p$ be an odd prime and $n$ a positive integer. Prove that $p+1$ divides $n$ if and only if $$\sum_{k\equiv j\pmod{p-1}}^n\binom{n}{k}(-1)^{\frac{(k-j)}{p-1}}\equiv 0 \mod p$$ for every $$j\in ...
5
votes
1answer
115 views

Prime numbers with binomial coefficients

Question: Prove that for any prime $p>3$, the number $\binom{2p-1}{p-1}-1$ is divisible by $p^{3}$. Attempt: Since every integer that is relatively prime to p has a multiplicative inverse modulo ...
2
votes
2answers
70 views

Prove that a sum converges to a trigonometric expression

$$2^n \cos \left (\frac{n \pi}{2} \right )=\sum_{k=0}^{n} (-1)^k \binom{2n}{2k}$$ I expanded the LHS and got $$\binom{2n}{0}-\binom{2n}{2}+\binom{2n}{4}-\binom{2n}{6}+\cdots+(-1)^{n}\binom{2n}{2n}$$ ...
2
votes
1answer
83 views

When are the binomial coefficients equal to a generalization involving the Gamma function?

Let $\Gamma$ be the Gamma function and abbreviate $x!:=\Gamma(x+1)$, $x>-1$. For $\alpha>0$ let us generalize the binomial coefficients in the following way: ...