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)

1
vote
2answers
44 views

Negative binomial theorem

I have been supplied with a combinatorical proof based on the n'th power, however I am trying to prove this by induction. I have no problem with the base case, or assuming that n=N. However, for ...
0
votes
0answers
31 views

closed form for $\sum_{k=0}^{n-1}\frac1{\binom{2n-1}{k}}\sum_{r=0}^{k}\binom{2n-1}{r}$?

Does there exist any closed form for the following sum? $$\sum_{k=0}^{n-1}\frac1{\binom{2n-1}{k}}\sum_{r=0}^{k}\binom{2n-1}{r}$$ Edit: Then can we find an asymptotic nice approximation as $n\to ...
0
votes
1answer
43 views

Sum of binomial coefficients and powers

The following identity is true for $n\geq1$: $$ n!=\sum_{k=1}^n (-1)^{n-k} {n\choose k} k^{n} $$ You can obtain it from the equation in this question by setting the variables equal to 1. I was ...
0
votes
4answers
64 views

Induction proof: sum of binomial coefficients

Prove by mathematical induction for all natural numbers $n$: $$\sum_{k=0}^{n} \binom{n}{k}=2^n$$ thus is it sufficient to show that (but I think I made a mistake) thus how to do it properly? ...
1
vote
2answers
63 views

$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{2^{2n}}$

I want to examine the convergence of the series $$\sum_{n=0}^{\infty}\binom{2n}{n}\frac{1}{2^{2n}}$$ In case it converges I want to evaluate it. I tried the D' Alembert theorem but it was ...
1
vote
1answer
55 views

Simplify the sum

Consider the sum of two polynomials $$ \sum_{k=0}^{n-1} {{{n-1} \choose {k}}^2 z^{2k}}+\sum_{k=0}^{n-2} {{n-2} \choose {k}} {{n} \choose {k+1}} z^{2k+1}=\sum_{i=0}^{2n-1}a_i z^i. $$ I want to find the ...
1
vote
1answer
40 views

Issue to identify binomial distribution

I'm trying to find a general formula for the following case : A production process has one of three possible states: (1) in control, (2) out of control with a type 1 problem, or (3) out of control ...
0
votes
1answer
45 views

How to compute $\displaystyle\sum_{k\equiv 1\!\!\pmod{\!4}}\!\!\binom{2014}{k}$?

I have to compute: $S=\binom{2014}{1}+\binom{2014}{5}+\binom{2014}{9}+...+\binom{2014}{2009}+\binom{2014}{2013}$ Could someone help me ?
0
votes
0answers
24 views

How to compute $\int_{-\infty}^{\infty} [(\frac{v}{i+1}+1)^2+\frac{1}{2}]^{-n-2} e^{-a v^2 } \mathrm{d}v$

How to compute the following integral? $$\int_{-\infty}^{\infty} [(\frac{v}{i+1}+1)^2+\frac{1}{2}]^{-n-2} e^{-a v^2 } \mathrm{d}v$$ in which, $a$ is a positive real number, $n$ is positive integer and ...
1
vote
4answers
117 views

How to expand $(x+y)^{-n}$?

How to expand $(x+y)^{-n}$ by binomial theorem, where $n$ is a positive integer? Is there any limitation for $x$ and $y$? If it can be expanded, how to compute the coefficients? Many thanks in ...
0
votes
1answer
24 views

Approximating a binomial sum over a simplex

For partial binomial sums such as $\sum_{k\le\Delta} \binom{n}{k}$ we don't tend to have closed forms. However we still know asymptotic expansions that are easy to work with. Can we do something ...
0
votes
1answer
25 views

Compute convolution

Let $a>0$ and $a_1>0$ be real numbers. Using the convolution theorem I have shown a following identity: \begin{equation} \sum\limits_{l=1}^n \binom{a_1}{n-l} \frac{1}{l} \binom{a}{l} = -\gamma ...
1
vote
1answer
30 views

Express $\binom{n+2}{k}$ according to $\binom{n}{k}$

I've just begun studying binomial coefficient and I'm trying to express $\dbinom{n+2}{k}$ according to $ \dbinom{n}{k}$. With this result I have to conclude that $\dbinom{2n}{2k}, \dbinom{2n+1}{2k}$ ...
0
votes
1answer
32 views

To prove for every integer $k >1 $ , $2+2^k \choose r$ is even for all $2 < r \le n=1+2^{k-1}$ , without Lucas' theorem

Can we prove by induction that for every integer $k >1 $ , $2+2^k \choose r$ is even for all $2 < r \le n=1+2^{k-1}$ ? Or by some divisibility properties of Binomial co-efficients ? I wanted to ...
0
votes
1answer
56 views

Use of Multinomial theorem.

I have the next identity which I want to prove. $$(\sum_{j}k_j^2)^{s} = \sum_{b_1+\ldots+ b_n =s} \prod_j k_j^{2b_j}$$ Obviously I need to use the Multinomial theorem, but how to procceed from ...
2
votes
3answers
58 views

How can I compute $\sum\limits_{k = 1}^n \binom{n - 1}{k - 1}$?

I know what $n \choose k$ equals, but I don't see how that would help me solve the sum of $n - 1 \choose k - 1$ from $k = 1$ to $n$. Is there any special trick I should know?
3
votes
1answer
337 views

How to deal with this double summation?

I'm stuck with the proof of this result: $$2^n = \sum_{t=-\frac{n-1}{2}}^{\frac{n-1}{2}} \binom{n+1}{\frac{n+1}{2} + t} \sum_{k=\vert t \vert}^{\frac{n-1}{2}} \binom{\frac{n-1}{2}+k}{k} ...
4
votes
1answer
55 views

To prove ${2p - 1 \choose p } \equiv 1 \pmod{p^2}$ without using Wolstenholme's theorem

How to prove that ${2p - 1 \choose p} \equiv 1 \pmod{p^2}$ ? I don't want to use Wolstenholme's theorem; but one might use $p|{p \choose k} , 1 \le k \le p - 1$ , and $(p - 1)! \sum_{k = 1}^{p - 1} ...
1
vote
1answer
75 views

What are all the even positive integers $n$ such that for $1 \le r \le n-1 $ , $2n \choose r$ is odd for exactly one $r$ ?

Motivated from this To find all odd integers $n>1$ such that $2n \choose r$ , where $1 \le r \le n$ , is odd only for $r=2$ ; what are all the even positive integers $n$ such that for $1 \le r ...
0
votes
1answer
15 views

Production process testing - binomial probabilities

A process produces faulty items with probability 0.04. Samples of 100 items are taken from batches at random and if there are less than 5 faulty items in the sample then the batch is accepted; ...
7
votes
3answers
173 views

Show that there are infinitely many integers such that $ \binom{m}{n-1} = \binom{m-1}{n} $

This question comes from the 1st Brazilian's IMO TST of 2004. I have found no solutions of it online, though I have developed one. After getting to $ mn = (m-n)(m-n+1) $, my solution relies on the ...
2
votes
0answers
34 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
135 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
106 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
39 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
44 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
58 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
123 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
85 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
54 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
32 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
177 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
198 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
37 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
34 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
28 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
67 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
43 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
43 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
90 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
126 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
59 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
32 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
75 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
67 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
41 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
134 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
70 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
388 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 ...