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

6
votes
1answer
135 views

How prove binomial cofficients $\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$

How prove this $$\sum_{k=0}^{[\frac{n}{3}]}(-1)^k\binom{n+1}{k}\binom{2n-3k}{n}=\sum_{k=[\frac{n}{2}]}^n\binom{n+1}{k}\binom{k}{n-k}$$ This equation How prove it? Thank you I want take this ...
2
votes
2answers
38 views

Is it true that $\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3} = \binom{n}{3}\binom{n-3}{k-3}$?

I was asked to find a closed formula for $$\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3}$$ To remove the $\sum$ if you will. Here's my reasoning, let's say we have a football team with $n$ players. First we ...
10
votes
2answers
234 views

Show that $\displaystyle\sum_{k=0}^n\binom{2n}{2k}^{\!2}-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove this $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
1
vote
2answers
37 views

Proving a summation involving binomial coefficients.

I need to prove the following inductively: (http://upload.wikimedia.org/math/9/e/5/9e57871ba17c1ad48e01beb7e1bb3bb9.png) $$\sum_{i=1}^{n} i{n \choose i} = n2^{n-1}$$ And for the life of me I can't ...
2
votes
1answer
72 views

Finding the super-mean (NOT the mean) of a set of numbers.

the super-mean is found by grouping pairs of numbers and finding the average successively until there is just one number. For example, $$(1-2-3-4-5) \to ((1+2)/2,(2+3)/2,(3+4)/2,(4+5)/2) \\ ...
1
vote
1answer
22 views

Largest K-multiple free set out of a fully ordered set

i'm struggling conceptually with this problem, i don´t know how to approach it in a clever way (without a computer, or at least without a brilliant algorithm). Mathematicians defined a k-multiple set ...
2
votes
1answer
31 views

Coefficients in Pochhammer Expansion

Can anyone tell me if there is a formula for finding the coefficient of $x^3$ in the expansion of $(3x+5)_{6}$, where $(a)_n$ denotes the Pochhammer symbol, i.e. $(a)_{n}=a\cdot(a+1)\cdots(a+n-1)$? ...
1
vote
2answers
103 views

Help proving ${n \choose k} \equiv 0 \pmod n$ for all $k$ such that $0<k<n$ iff $n$ is prime.

I can prove the $n$ is prime case: If $n$ is prime, then since $k < n$ and $n$ is prime, the factor of $n$ in the numerator won't be cancelled out. So the question boils down to Let an integer ...
0
votes
1answer
62 views

Compute a sum involving binomial coefficients

Let $0 < a < b$ and $p_1 >0$ and $p_2>0$ be integers. The question is to prove the following identity: \begin{equation} \sum\limits_{j=a}^b \left(\begin{array}{c} j \\ p_1 \end{array} ...
1
vote
2answers
42 views

Probability problem with binomial/multinomial distribution

Mary knows the answers to $20$ of the $25$ multiple choice questions on the Psychology $101$ exam, but she has skipped several of the lectures, she must take random guesses for the other five. ...
0
votes
1answer
146 views

Project Euler #453 confusion

So I decided to give a shot on the #453 project euler problem but there is something that confuses me with the numbers given. I decided to start by calculating the possible arrangements of 4 vertices ...
4
votes
2answers
234 views

maybe this sum have approximation $\sum_{k=0}^{n}\binom{n}{k}^3\approx\frac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty$

prove or disprove this $$\sum_{k=0}^{n}\binom{n}{k}^3\approx\dfrac{2}{\pi\sqrt{3}n}\cdot 8^n,n\to\infty?$$ this problem is from when Find this limit ...
0
votes
2answers
45 views

Prove that the set of all subsets of cardinality k of a set of cardinality n has cardinality n choose k

That title is probably very compound and confusing so here's a picture. I'm onto something here. Intuitively this makes sense. Let $A$ be a set such that $|A| = n$. If we choose the first $k$ ...
0
votes
3answers
89 views

Combinatorial proof that $\sum_{j=0}^k (-1)^j {\binom n j}=(-1)^k \binom{n-1}{k}$

Prove $\sum_{j=0}^k (-1)^j {\binom n j}=(-1)^k \binom{n-1}{k}$. It can be proven easily using induction and Pascal's identity, but I want some insight. The alternating sum reminds of ...
8
votes
1answer
269 views

Smallest constant in exponent so that limit of sum is $0$

I am trying to work out the smallest constant $c>0$ so that $$\lim_{n \to \infty} \sum_{a=1}^n \sum_{b=0}^n {n \choose a} {n-a \choose b} \left({a+b \choose a} 2^{-a-b}\right)^{c n/\ln{n}} =0 .$$ ...
3
votes
1answer
85 views

Proof sought for a sum involving binomials that simplifies to 1/2

A proof of: $$\begin{align*}(1/2)^{2m+1} \sum_{k=0}^{m} \binom{m}{k} \sum_{j=0}^{k} \binom{m+1}{j} = \frac{1}{2} \end{align*} $$ Conjecture based on the following Maple code: ...
0
votes
2answers
156 views

Binomial Theorem Practical Problem

I have been studying the 'Binomial Series', Chapter 16, Pg.125 within the Engineering Mathematics Book by John Bird. After completing this section I have attempted to complete the exercises for ...
5
votes
2answers
187 views

How prove this $\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $

I think the following equality is true ($p\in \mathbb{N},p\ge 2$): $$\sum_{k=0}^n \binom{n}{k} \binom{(p-1)n}{k} \binom{pn+k}{k} = \binom{pn}{n}^2 $$ when $p=2$, then ...
0
votes
1answer
58 views

General term of a series

I am trying to find the general term of the series: $$( 1 + x + ... + x^{m-1} )^k$$ I am trying to implement the KZ filter and it requires the coefficients of the above series. Here, k and m are ...
0
votes
2answers
36 views

Couple of Counting (how many ways) questions.

1.If I have a group of 10 seats reserved for people, and there are n=>10 total people, how many ways are there to choose who gets the 10 seats? for ex:If there was a definite number of people lets ...
1
vote
2answers
71 views

Given integers $a \ge b > 0$ and a prime number $p$, prove that ${pa \choose pb} \equiv {a \choose b} \mod p$.

I've been grappling with this problem for a while but haven't solved it. Given integers $a \ge b > 0$ and a prime number $p$, prove that ${pa \choose pb} \equiv {a \choose b} \mod p$.
0
votes
2answers
54 views

Pascal's Triangle Proof

Trying to determine a formula for the sum of the entries of the $n$th row of Pascal’s triangle, for any natural number $n$. Any proof will do as I have to determine $3$ different proofs. - So far, ...
1
vote
1answer
58 views

Binomial coefficient properties

On "theoretical computer science cheat sheet" I found a special formula which is: $$ {n \choose k} = (-1)^k {k-n-1 \choose k}$$ But when I try to expand the value of ${k-n-1 \choose k}$ I have ...
0
votes
1answer
42 views

Finding coefficient of $x^k$ in summation of binomial series

I am not able to solve this problem Find the coefficient of $x^k\;\;(k$ is greater than or equal to zero and lesser than or equal to $n$) in the expansion of $E = 1 + (1+x) + (1+x)^2 .... + (1+x)^n$ ...
3
votes
1answer
34 views

Binomial coefficient difference

I have the following difference of binomial coefficients: $$f(m)={m+n\choose n}-{m-d+n\choose n}$$ I believe the following two things should hold true: For $m$ large enough, $f(m)$ is a polynomial ...
1
vote
1answer
85 views

What is the sum of divisors of binomial&factorial

$$\sum_{m|\frac{n!}{i!(n-i)!}} m$$ Perhaps a good start is $$\sum_{m|n!} m$$ When seeing this last sum or also this one $$\sum_{m|lcm(1,2,...,n)} m$$ I sort of want to use $(n+1)n\over2$ somehow.
1
vote
2answers
88 views

Is this Newton binomial legal?

is this equation proper? $$ \binom {9} {12} = 0 $$ so if we have a binomial $$ \binom {n} {k} $$ and when $$ n<k $$ the result is 0?
4
votes
2answers
82 views

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

As the title says... We are asked to show that $$\sum_{i=1}^{n}\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}$$ I tried with induction, but that seems to never work with these kind of questions. We need ...
1
vote
2answers
50 views

Number of solutions to equation - is there a better way of solving this than inclusion-exclusion?

We are asked to find the number of solutions for $a+b+c+d+e+f=20$ when $2 \leq a,b,c,d,e,f \leq 6$ Is there a better way of solving it than what I did ? because it an exam, this seems like a very ...
10
votes
3answers
287 views

Prove that $\,\,\displaystyle\inf_{n\in\mathbb N}\sum_{k=0}^{p}\lvert\sin{(n+k)^p}\rvert>0$

For any poistive integer number $p$, show that $$\inf\left\{ {\left\vert\sin{(n^p)}\right\vert+\left\vert\sin{(n+1)^p}\right\vert+\cdots+ \left\vert\,\sin{(n+p)^p}\right\vert\, :\,n\in ...
1
vote
2answers
120 views

Show $\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$

My question is: show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this. We could either ...
3
votes
1answer
80 views

Sum of fraction of factorials

Can anybody explain this? $$\sum\limits_{k=1}^{\frac{m-1}2}\frac{(2k)!(2m-2k)!}{(2k-1)(2m-2k-1)k!^2(m-k)!^2}=\frac{(2m)!}{(2 m-1)m!^2}$$ I did actually simplify this to: ...
1
vote
0answers
46 views

Increasing fraction of sum of binomial coeffients

Let $n$ be a positive integer. Show that the quantity $$ \displaystyle \frac{ \displaystyle \sum_{i=1}^n { n+k \choose i-1 } }{ \displaystyle \sum_{i=1}^n { n+k+1 \choose i } } $$ is ...
2
votes
1answer
117 views

Identify $\sum(-1)^{n-k}2^{2k}\binom{n+k}{2k}$

Does anybody know what the following sum evaluates to? $$ \sum_{k=0}^n{(-1)^{n-k}}2^{2k}\binom{n+k}{2k} $$
0
votes
1answer
46 views

Linear combinations of vector $\binom{n+r-1}{r-1}$ and combinations with repetitions $\binom{n+r-1}{r}$

There are $$\binom{n+r-1}{r-1} \tag{1}$$ nonnegative vectors $(x_1,x_2,\dots,x_r)$ such that $x_1+x_2+\dots+x_r=n, \ \ \ \ \ \ x_i \ge 0, \ \ \ 1 \le i \le r$ Then the number of selections of ...
0
votes
1answer
36 views

Binomial distribution convergence

Let $Y \sim\binom{n}{\pi}$ Suppose $n \rightarrow \infty$ and $\pi \rightarrow 0$ such that $n\pi \rightarrow \mu$, where $\mu$ is a constant. derive the limiting distribution of Y. $f_Y(y)= ...
0
votes
2answers
64 views

Binomial Theorem question

Find the coefficient of $x$ in the expansion of $$\left(1-2x^3+3x^5\right)\left(1+\frac{1}{x}\right)^5.$$ Answer is $154$, but how?
0
votes
2answers
56 views

How Do You Calculate Probabilities of Random Events Occuring in Sequence?

So I have a series: $f(x_{n+1})=x_n \pm t$ and $f(x_0)=W$ What I'd like to calculate is the probability in terms of $t$ and $W$ (assuming they're any constant $W>t$) that any $f(x_q)=0$ for all ...
1
vote
1answer
56 views

Binomial coefficient manipulation

Can somebody explain why this is true? $$\sum_{k=1}^n \binom{k}{m}\frac 1k=\sum_{k=m}^n \binom{k}{m}\frac 1k$$ This manipulation is a part of an exercise, but I'm stuck at here.
1
vote
1answer
64 views

Show binomial coefficient for $x^n$ in the expansion $(1+x)^r(1+x)^s$

Show that the binomial coefficient for $x^n$ in the expansion $(1+x)^r(1+x)^s$ is $\sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}$. I dont know how to reach that. What i see is that: ...
3
votes
2answers
71 views

$2^n=C_0+C_1+\dots+C_n$

Could anyone give me hints for this one? $2^n=C_0+C_1+\dots+C_n$ Thats all I can say and I know tricks like integrating or differentiating both side and then put $x=1$ or what ever we need. but ...
4
votes
1answer
66 views

First digits of extremely large binomial coefficients

Can the first digits of a binomial coeffecient $$\binom{n}{k}$$ be calculated, if n and k are very large numbers ? For example Calculate the first ten digits of $$\binom{10^{85}}{10^{23}}$$ Any ...
4
votes
1answer
110 views

Recursive sequence with binomial coefficients

I have a sequence $\epsilon_i$ defined recursively for $i\ge 1$ as follows \begin{eqnarray*} \epsilon_1 &=& \frac{1}{p}\\ \epsilon_n &=& \frac{1}{1-(1-p)^n}\left( 1 + \sum_{j=1}^{n-1} ...
1
vote
2answers
82 views

Prove $p_0-p_2+p_4-\cdots=2^{n/2}\cos{\dfrac{n\pi}{4}}$ and $p_1-p_3+p_5-\dots=2^{n/2}\sin{\dfrac{n\pi}{4}}$

Consider: $$(1+x)^n= p_0 + p_1 x + p_2 x^2+\cdots$$ From where $$p_0=1,\quad p_1=\dfrac{n}{1},\quad p_2=\dfrac{n(n-1)}{2!},\ldots$$ Are the coefficients of the Newton´s Binomial expansion, using $x=i$ ...
15
votes
2answers
261 views

Continuous generalization of $\sum_{k=0}^n {n \choose k} = 2^n$?

We know that $$\sum_{k=0}^n {n \choose k} = 2^n.$$ A continuous generalization of the formula would be $$\int_0^{n+1} \frac{\Gamma(n+1)}{\Gamma(n-x+1) \Gamma(x+1)} dx = 2^n?,$$ but this is incorrect ...
1
vote
2answers
60 views

How to prove $\sum_{k\leq n}^{n} \binom{n}{k}= 2^n$ by induction [duplicate]

$\sum_{k\leq n}^{n} \binom{n}{k}= 2^n , n, k \in \mathbb{N}$ Im trying with mathematical induction but im stuck. My inductive step: $H) \sum_{k=0}^{h} \binom{h}{k}= 2^h$ $T) \sum_{k=0}^{h+1} ...
3
votes
1answer
186 views

Find the sum of the series.

I need to find the following sum: $$\sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s}$$ First I tried to simplify this: $$\begin{split} \sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s} &= ...
2
votes
2answers
151 views

Use induction and Newton's binomial formula to show that $\binom{n}{0}+\binom{n}{1}+\cdot+\binom{n}{n}=2^n, \forall n\in \mathbb N$ [duplicate]

Use induction and Newton's binomial formula to show that: $ i)$ $ \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n, \forall n\in \mathbb N$ $ ii)$ ...
2
votes
0answers
175 views

How to calculate this triple summation?

I need to calculate the following summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m-j}\choose{k-j}}}{k\choose j}r^{k-j+i}$$ I do not know if it is a well-known summation or not. ...
4
votes
2answers
76 views

Series of inverses of binomial coefficients

Can you think of a simple way of proving that $$ \sum_{n=k+1}^\infty \frac{1}{n \choose k} $$ is rational for any $k \geq 2$? Here's the background. Consider a series: $$ \sum_{n=1}^\infty ...