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
395 views

Manipulation of Geometric Series and Binomial Theorem

I was just hoping to confirm that the following manipulations make sense: Say I begin with $\frac{1}{(1-x)^n}$. Then we have $(1-x)^{-n} = $$\sum$ $-n\choose k$ $(-x)^k$ = $\sum$ $(-1)^k$ $n+k-1 ...
0
votes
1answer
24 views

Sum $(1-x)^n$ $\sum_{r=1}^n$ $r$ $n\choose r$ $(\frac{x}{1-x})^r$

The question is to find the value of: $n\choose 1$$x(1-x)^{n-1}$ +2.$n\choose2$$x^2(1-x)^{n-2}$ + 3$n\choose3$$x^3(1-x)^{n-3}$ .......n$n\choose n$$x^n$. I wrote the general term and tried to sum it ...
3
votes
4answers
132 views

What is the meaning of $(2n)!$

I came across something that confused me $$(2n)!=?$$ What does this mean: $$2!n!, \quad 2(n!)$$ or $$(2n)!=(2n)(2n-1)(2n-2)...n...(n-1)(n-2)...1$$ Which one is right? The exercise is to show that ...
2
votes
2answers
49 views

divide 6 people in group of 2 in same size

Exercise: divide 6 people in group of 2 in same size. My solution: The exercise tells us to calculate the combination without repetition. If I start by calculating the number of ways to select how ...
2
votes
2answers
84 views

Concrete Mathematics, Newton Series and Inversion

In section 5.3 of Concrete Mathematics, on the bottom of page 192, "A special case of the rule (5.45) we've just derived for Newton's series can be rewritten in the following way:" (this is 5.48) ...
2
votes
1answer
39 views

Binomial coefficients(Concrete mathematics 5.39)

I have no idea what I could do with this problem. I tried to substitute, but failed.. Hope someone can help
0
votes
1answer
63 views

proof: $\sum\limits_{i=k}^n\binom{i}{k}=\binom{n+1}{k+1}$

Let $n ≥ 0$ and $k ≥ 0$ be integers. 1) How many bitstrings of length $n + 1$ have exactly $k + 1$ many $1$s? 2) Let $i$ be an integer with $k ≤ i ≤ n$. What is the number of bitstrings of length $n ...
0
votes
1answer
38 views

Find the coefficient of $x^{4}$ from $(1+x)^{1/3}$

Find the coefficient of $x^{4}$ from $(1+x)^{1/3}$ Should I use the formula $C(n,k) = n!/[k!(n-k)!]$? And what is the solution of this problem?
0
votes
3answers
94 views

Prove an upper bound for the binomials

This is (supposed to be) an upper bound on the binomial coefficient: $$ \binom{n}{k} \le \frac{n^n}{k^k(n-k)^{n-k}}$$ If we prove it by induction for all integers $0 \le k \le n/2$, we can easily ...
0
votes
3answers
31 views

Binomial coefficient problem

I still haven't quite realized how to solve binomial coefficient problems like this, can someone show me an elaborated way of solving this? I need to write this expression in a more simplified way: ...
0
votes
1answer
23 views

Divisibility of binomial coefficients

I have got this series of binomial coefficients - $${2n\choose 0}+3\times{2n\choose 2}+3^{2}\times{2n\choose 4}+\ldots +3^{n}\times{2n\choose 2n}$$ I have to prove this to be divisble by ...
2
votes
3answers
55 views

Proof of non divisibililty of $\binom{n}{r}$ with a prime $p$

I came across this : "It is possible to show that if $p$ is prime, $\binom{n}{r}$ is not divisible by $p$ if and only if the addition $r + (n-r)$, when written in base $p$, has no carries. This means ...
2
votes
3answers
54 views

Proof by induction, binomial coefficient

I have to make the following proof: $${\sum\limits_{k=1}^n}{k}{n\choose k} = n2^{n-1}$$ Base case, $n = 1$: $${\sum\limits_{k=1}^{1}}{k}{1\choose k} = 1 = 1\cdot2^0=1$$ Inductive Hypothesis: for ...
1
vote
5answers
104 views

how to prove: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $ [duplicate]

need help to prove this: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $ where $n$ is integer $\geq 1$. Question also said taking the derivative of $(1 + x)^n$ would be helpful which I've found ...
0
votes
0answers
59 views

An identity for the Fibonacci number $F_{n^2}$

I was manipulating Fibonacci numbers defined by : $F_0=0$ and $F_1=1$ $ \forall n\in \mathbb{N}$ $F_{n+2}=F_{n+1}+F_n$ Until I obtain this equation (which I proved) $\forall n\in \mathbb{N^*}$: ...
3
votes
4answers
97 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 ...
0
votes
0answers
27 views

Prove by induction on the binomial coefficient n choose m …

Prove by induction on $n$ that the binomial coefficient $\begin{pmatrix}n\\m\end{pmatrix}$ is the number of subsets of $I_{n}$ having size equal to $m$. The solution is as follows: So far it can be ...
8
votes
3answers
141 views

The maximum of $\binom{n}{x+1}-\binom{n}{x}$

The following question comes from an American Olympiad problem. The reason why I am posting it here is that, although it seems really easy, it allows for some different and really interesting ...
8
votes
3answers
335 views

Proving the sum of squares of sine and cosine using the Cauchy product formula

Here are the power series of sine and cosine: $$\sin(x) = \sum_{n=0}^{\infty} (-1)^n \frac {x^{2n+1}} {(2n+1)!}$$ and $$\cos(x) = \sum_{n=0}^{\infty} (-1)^n \frac {x^{2n}} {(2n)!}$$ How can it be ...
18
votes
2answers
12k views

A comprehensive list of binomial identities?

Is there a comprehensive resource listing binomial identities? I am more interested in combinatorial proofs of such identities, but even a list without proofs will do.
2
votes
2answers
86 views

Combinatorial proof for $ \sum _{r=1} ^n r^3 \binom nr = n^2(n+3) 2^{n-3}$

Find the combinatorial proof for $$ \sum _{r=1} ^n r^3 \binom nr = n^2(n+3) 2^{n-3}$$ After proving it using algebra, I'm unable to find a combinatorial argument for the above statement. Help ...
8
votes
2answers
117 views

Number of ways to arrange $n$ items in $m$ positions having exactly $k$ items adjacent to each other

It was over 20 years since I studied maths and I am stuck. I'd really appreciate some help understanding this (probably quite simple) problem. I have $n$ items that I can place on $m$ positions. $m$ ...
2
votes
1answer
39 views

What is $\binom{n}{-k}$?

What is $\binom{n}{-k}$ ? If $n,k\ge0$ In Wikipedia there's a case where $n$ is negative and not $k$ But if Pascal's rule still holds, I get for example for $k=0$; ...
0
votes
2answers
27 views

Binomial Expansion where N is negative

Comparing the formula for regular binomial expansion (n>1): $(a+b)^n=a^n + \binom{n}1a^{n-1}b + \binom{n}2a^{n-2}b^2 +...$ to binomial expansion for negative indices, (n<1): $(1+x)^n= 1 + nx + ...
4
votes
3answers
45 views

Hypergeometric 2F1 with negative c

I've got this hypergeometric series $_2F_1 \left[ \begin{array}{ll} a &-n \\ -a-n+1 & \end{array} ; 1\right]$ where $a,n>0$ and $a,n\in \mathbb{N}$ The problem is that $-a-n+1$ is ...
1
vote
1answer
38 views

Proof By Induction Using Binomial Coefficients

I'm having a really hard time with this proof by induction: Prove this formula by induction: $1^2 + 2^2 + 3^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$. Easy enough, right? Wrong. I have to do it using ...
1
vote
1answer
26 views

Finding the coefficient of a power series

How would I find the coefficient of: $[x^{10}]x^6(1-2x)^{-5}$ I know that I can simplify this as follows: $[x^4](1-2x)^{-5}$ and that generally the following formula would be used to solve this: ...
3
votes
2answers
327 views

This question involves Pascal's Triangle & Binomial Theorem. Full Question

Could anyone please help me on the following problem: Factorize the expression $P(n)=n^x-n$ for $x=2,3,4,5$ Determine if the expression is always divisible by the corresponding $x$. If divisible use ...
0
votes
1answer
23 views

Binomial coefficients bounded by entropy exponential

So I'm trying to prove that for $\frac{1}{2}< x \leq 1$ we have $$\sum_{\lceil nx \rceil}^{n}{n \choose k} \leq 2^{nh(x)}$$ I've managed to prove that $$\sum_{0}^{\lfloor nx \rfloor}{ n\choose ...
1
vote
0answers
41 views

Using Stirling's formula to uniformly bound Bernoulli success probabilities (part 2)

In this paper, the authors say that for any $\gamma \in [1/2,1)$, there is a positive constant $A=A(\gamma)$ such that for any $n$, $$ \sum_{n\gamma\leq k \leq n} \binom{n}{k} \geq A n^{-1/2}2^{n ...
13
votes
2answers
230 views

When $\frac{C(n, k)}{n^{k-1}} > 1$?

I came across this while considering the subset sum problem in relation to another problem. Define the ratio, $$R(n,k) = \frac{C(n, k)}{n^{k-1}} = \frac{\binom n k}{n^{k-1}}$$ and the integer ...
1
vote
4answers
49 views

Limit of quotient of summations involving special binomial coefficients

Find the limit, when $n$ tends to infinity, of $$ \frac{\displaystyle\sum_{k=0}^n\binom{2n}{2k}3^k} {\displaystyle\sum_{k=0}^{n-1}\binom{2n}{2k+1}3^k} $$ Please Help Me to solve the problem ...
1
vote
0answers
42 views

Limit of $\frac{1}{n}\log({n\choose np})$ without using Stirling's formula

I am trying to evaluate the following limit: $$ \forall p\in(0,1) ,\lim_{n\rightarrow \infty} \frac{1}{n}\log{n\choose \lfloor np \rfloor} =H(p),$$ where $\lfloor x\rfloor$ means the greatest integer ...
3
votes
1answer
40 views

$\sum_{i=0}^{k} \binom{m}{i}\binom{n}{k-i} =\binom{m+n}{k}$ [duplicate]

I'm trying to show that the equality $$\sum_{i=0}^{k} \binom{m}{i}\binom{n}{k-i} =\binom{m+n}{k}$$ Is true. I know it is since there is a good combinatorical argument for it. If we have a group of ...
3
votes
3answers
66 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, ...
2
votes
0answers
34 views

Closed-form solution for $f(n) = \sum_{k>0}\binom{n}{2k}x^{k}$ without $\sqrt{x}$

Is it possible to reformulate the expression $$ (1+\sqrt{x})^n + (1-\sqrt{x})^n $$ in the form that contains no square roots of $x$ and no iterative sums (i.e. can be computed in constant time)? ...
3
votes
2answers
79 views

On ${-1 \choose 0}=1$, can I assume that $\frac{(-1)!}{(-1)!}=1$?

I've had to evaluate ${-1 \choose0}$ and then I discovered the following: $${-1 \choose0}=\frac{(-1)!}{(-1)!0!}=\frac{(-1)!}{(-1)!}=1$$ Can I assume that $\frac{(-1)!}{(-1)!}=1$?
1
vote
1answer
36 views

Binomial coefficients and cosin

In this question the user ask to prove the next identity: $$1 + 4\cos{2\theta} + 6 \cos{4\theta} +4\cos{6\theta}+ \cos {8\theta} =16\cos{4\theta} \cos^4 \theta$$ I realized the terms in the left ...
1
vote
1answer
31 views

What is the smallest value beside 1 of a binomial with two integer values > 0? [closed]

I'm searching for the smallest possible value of a binomial(a, b) where a >= b and both values are greater than ...
0
votes
1answer
28 views

sum of a binomial coefficient [duplicate]

Trying without success to solve the following: what is the sum of $\binom{80}{0}-\binom{80}{1}+\binom{80}{2}-\binom{80}{3}...-\binom{80}{79}+\binom{80}{80}$ any help will be greatly appreciated
1
vote
4answers
73 views

What is the coefficient of $x^{17}$ in the formula $(x^2+x)^{15} $?

What is the coefficient of $x^{17}$ in the formula $(x^2+x)^{15} $? Any idea how to solve this using the binomial coefficient formula?
1
vote
0answers
62 views

General solution for a combinatorial problem

I want to find a general solution for a problem. I explain the problem with an example. $\underline{Problem}:$We have a matrix $A$ of size $M \times N$, where $M <N$. We choose sub-matrices of ...
1
vote
1answer
117 views

Why binomial distribution for particles in container?

I read in an introduction to information theory and entropy There is N particles, which can move across a million of boxes. What does author mean by Consider the number of configurations with ...
1
vote
1answer
32 views

Calculating the sum of a binomial coefficient series

Calculate this: $$\bigl(\begin{smallmatrix} 80 \\0 \end {smallmatrix}\bigr)-\bigl(\begin{smallmatrix} 80 \\1 \end {smallmatrix}\bigr)+\bigl(\begin{smallmatrix} 80 \\2 \end ...
2
votes
3answers
54 views

Evaluate: $\sum_{k=2}^n\frac {n!}{(n-k)!(k-2)!}$

Evaluate: $$\sum_{k=2}^n\frac {n!}{(n-k)!(k-2)!}$$ Attempt $S_2=\frac {n!}{(n-2)!}$ $S_3=\frac {n!}{(n-3)!}$ $S_4=\frac {n!}{2(n-4)!}$ $\vdots$ $S_{n-1}=\frac {n!}{1!(n-3)!}$ $S_n=\frac ...
15
votes
3answers
7k views

Proof that a Combination is an integer

From its definition a combination $(^n_k)$, is the number of distinct subsets of size k from a set of n elements. This is clearly an integer, however I was curious as to why the equation ...
-1
votes
0answers
19 views

Question on binomial coefficient power [on hold]

Is there an expression to $$2^{\sum_{i=1}^{k}\binom{n}{i}}-2^{\sum_{i=1}^{k-1}\binom{n}{i}}?$$ Also is this expression solution to question in link Number of degree $k$ functions?
17
votes
3answers
476 views

A three variable binomial coefficient identity

I found the following problem while working through Richard Stanley's Bijective Proof Problems (Page 5, Problem 16). It asks for a combinatorial proof of the following: $$ \sum_{i+j+k=n} ...
1
vote
0answers
137 views

Sum concerning Catalan triangle and binomials

I am trying to prove the following relation. For $k \in \mathbb{N},k \geq 2$ and $i=1,\ldots,k-1$ \begin{equation} {2k-2-i \choose k-1-i}=\sum \limits_{l=0}^{k-1-i} 2^{2l} T(k-2-l,k-1-i-l)-2 \sum ...