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
0answers
30 views

Simpler expression for binomial sum

Is there any closed expression for the following sum: $$\sum_{i=0}^{l-k} \binom{n-l}{i} \binom{l-k}{i} \binom{l-i}{k}$$ where $ k<l < n/2$?
-1
votes
2answers
76 views

What does 9P2 mean, and how would one solve it?

We are studying "Sequences, Series, and Probability" and it likely related to binomial theorem and pascals triangle. I've a test tomorrow morning, and if I can't figure this out soon, I'm likely to ...
2
votes
1answer
89 views

Mean value of minimum of binomial variables

Let $X,Y$ be two independent random variables with binomial distribution: $B[4n,p]$ with $p=0.5$. Let $M=\min(X,Y)$. What is the expectation of $M$? This question seems related but it has no answer: ...
1
vote
2answers
33 views

Some binomial equality

I am trying to prove the following equality $$ \sum_{r=k}^{n}\binom{2n+1}{2r+1}\binom{r}{k}=\binom{2n-k}{k}2^{2n-2k}~~;~k\le n. $$ I noticed that for $k=0$ it becomes $$ ...
1
vote
1answer
41 views

$k$ divides $\binom{kn}{n}$

For positive integers $k,n$ , is it true that $k$ divides $\binom{kn}{n}$? I can write $$\binom{kn}{n}=\frac{(kn)(kn-1)\cdots(kn-n+1)}{n(n-1)\cdots 1}$$ but must the $k$ at the top remain after ...
1
vote
2answers
45 views

Legendre polynomial to show identity, can't spot mistake

Using Legendre polynomial generating function \begin{equation} \sum_{n=0}^\infty P_n (x) t^n = \frac{1}{\sqrt{(1-2xt+t^2)}} \end{equation} Or $$ P_n(x)=\frac{1}{2^n n!} \frac{d^n}{dx^n} [(x^2-1)^n] ...
2
votes
1answer
121 views

To find all odd integers $n>1$ such that $2n \choose r$ , where $1 \le r \le n$ , is odd only for $r=2$

For which odd integers $n>1$ is it true that $2n \choose r$ where $1 \le r \le n$ is odd only for $r=2$ ? I know that $2n \choose 2$ is odd if $n$ is odd but I want to find those odd $n$ for which ...
2
votes
1answer
81 views

Binomial expansion (sort of ) rearrangement

Let $$ x_n=\sum_{i=1}^n\binom{n}{i}y_iz_{n-i} \qquad n=1,\ldots,k $$ For general $k$, can you find an explicit expression for $y_k$ only in terms of $x_1,\ldots,x_k$ and $z_1,\ldots,z_k$? For ...
1
vote
1answer
47 views

Can this expression be simplified?

I get a function related to a variable $x$, that is $f(x)=\displaystyle \frac{ \sum_{i=0}^K{ i \binom{n+i}{i} x^i}} {\sum_{i=0}^K{\binom{n+i}{i}x^i}}$, where $K$ and $n$ are positive integers, can ...
2
votes
1answer
30 views

Polynomials and difference operator

Let's consider a difference operator $\triangle f(n)= f(n+1)-f(n)$. How to prove that $f$ is a polynomial so that $deg(f) \leq d$ if and only if $\triangle f ^{d+1} =0$. First step of the solution ...
3
votes
1answer
166 views

Hard binomial sum [closed]

How to prove this relation? $$\sum_{i=0}^{n}\frac{2^{-2i}\binom{2i}{i}}{n+i+2}=\frac{2^{4n+2}-\binom{2n+1}{n}^2}{(2n+3)2^{2n+1}\binom{2n+1}{n}}$$ That seems difficult!
8
votes
4answers
191 views

Proving this binomial identity $\sum_{k=0}^n {n+k \choose k} \frac{1}{2^{k}}= 2^{n}$

A teacher gave this as a homework question, and I have tried but haven't been able to arrive at a solution. $\sum_{k=0}^n {n+k \choose k} \frac{1}{2^{k}}= 2^{n}$ Could someone prove it, or at least ...
1
vote
1answer
33 views

How to prove elementary identities for binomial coefficients using combinatorial arguments?

I'm in a second year discrete mathematics course, and we have identities like this $$\binom{n}{k}(n-k) = \binom{n-1}{k}n$$ and Pascal's Triangle law. Our professor said that algebraic proofs are ...
1
vote
0answers
25 views

How many permutations of a linear equation

How many strictly positive integer solutions does the equation $x_1+x_2+···+x_n = k$ have? (Hint: Consider the equation $y_1+y_2+· · ·+y_n = k−n$ with variables $y_i \ge 0$.) I believe the ...
0
votes
1answer
27 views

How many ways are there to do this experiment?

I don't want the full solution rather a step in the right direction. I believe what I have so far is right but I just would like to verify and know the final basic steps to find out how many ways the ...
0
votes
2answers
57 views

Binomial coefficient identity $\sum_{k=1}^n k {n \choose k } = n\cdot 2^{n-1}$ [duplicate]

I'm having a bit of problems proving the following: $$\sum_{k=1}^n k {n \choose k } = n\cdot 2^{n-1}$$ I always seem to get to the line: $2^{n-1} + 1 = 2^n$ which I know is untrue. Could anyone ...
2
votes
1answer
38 views

length of printout of pascal's triangle

when writing a program, that calculates pascals triangle, I noticed that the printout looks (to me) like an aproximately exponential curve 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 ...
0
votes
1answer
36 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 ...
2
votes
2answers
74 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 ...
0
votes
1answer
125 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
41 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
47 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
31 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
67 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 ...
2
votes
3answers
66 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 ...
0
votes
0answers
38 views

Prove by induction that the binomial coefficient equals the number of subsets of given size

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 ...
1
vote
5answers
132 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
68 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^*}$: ...
8
votes
3answers
372 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 ...
6
votes
3answers
150 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 ...
3
votes
5answers
178 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 ...
2
votes
1answer
42 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
40 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 + ...
1
vote
1answer
52 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
30 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: ...
1
vote
0answers
45 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 ...
0
votes
1answer
29 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
4answers
60 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
50 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
63 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 ...
2
votes
0answers
40 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
3answers
76 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
3answers
54 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 ...
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
42 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
32 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
78 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
1answer
34 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
57 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 ...