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)

3
votes
2answers
105 views

Prove that $\sum_{k=1}^{n}k\binom{n}{k}=n\cdot2^{n-1}$ [duplicate]

I want to prove the following: $$\sum_{k=1}^{n}k\binom{n}{k}=n\cdot2^{n-1}$$ what I did is(use binominal): $$\binom{n}{k}X^k\cdot 1^{n-k} = (X+1)^n$$ $$k\binom{n}{k}X^k\cdot 1^{n-k} = k(X+1)^k-1$$ now ...
3
votes
1answer
134 views

Combinatorial Proof of a Binomial Identity

$$\sum_k {m\choose k} {n \choose k} = {m+n \choose n}$$ In this identity we seem to be choosing subsets that do $\it not$ contain k of type m and type n for all possible k. In the style of ...
3
votes
2answers
985 views

Number of triangles inside given n-gon?

How many triangles can be drawn all of whose vertices are vertices of a given n-gon and all of whose sides are diagonals ( not sides ) of the n-gon ? How many k-gons can be drawn in such a way ?
3
votes
1answer
286 views

Surprising approximation of weighted sum of binomial coefficients

The following sum appeared in connection to the problem addition of angular momentum in physics: $$ \frac{1}{2^{n+3}}\sum_{k=0}^n \left(\frac{n-2k-1}{\sqrt{k+1}}+\frac{n-2k+1}{\sqrt{n-k+1}}\right)^2 ...
3
votes
2answers
138 views

Why is the binomial coefficient related to the binomial theorem?

The binomial coefficient basically provides the number of ways to choose a set of $k$ from $n$ sets. To me, it can be considered the number of unique ways to pick $k$ amount of "cards" from a deck of ...
3
votes
1answer
241 views

Summation: $ \sum \limits_{r=0}^n \frac{ \binom n r}{x+r} $

How to evaluate $$ \sum \limits_{r=0}^n \large \frac{\binom n r} {x+r} $$ I got this problem from a friend according to him, $ \binom n r$ is the coefficient of $(1+x)^n$. I am not sure how to ...
3
votes
1answer
192 views

Quick way of showing an $n\times n$ Jordan block associated to $1$ is similar to the companion matrix of $(x-1)^n$

Is there a quick, clean way of proving that the $n\times n$ Jordan block with $1$'s on the diagonal and the Frobenius companion matrix corresponding to the polynomial $(x-1)^n$ are similar matrices? ...
3
votes
1answer
139 views

Simplification of a sum

Any ideas on how to approximate and/or simplify this crazy-looking sum will be massively appreciated) $$\frac{1}{\mu}\sum_{j=0}^{\frac{\lambda}{2}} ...
3
votes
2answers
108 views

Bounding sum of binomials

For a small $c>0$, what is a smallest $k$ such that $$\sum_{i=0}^k \binom{n}{i} \ge c \cdot 2^n.$$ The sum jumps somewhere around $k=\frac{n}2$ from $o(2^n)$ to almost $2^n$. Is there a better ...
3
votes
1answer
51 views

Prove combination identity

$ \sum_{k=0}^n {2k \choose k} {2n-2k \choose n-k} = 4^n $ I tried with mathematical induction only to fail. Is this formula related to some special function like Beta, Gamma, etc?
3
votes
1answer
39 views

How to simplify a sum with binomial coefficients multiplied by $k^3/2^k$?

The sum is $$\sum_{k=5}^{\infty}\binom{k-1}{k-5}\frac{k^3}{2^{k}} $$ The first thing I thought of was the binomial coefficient. So I re-indexed it ...
3
votes
1answer
74 views

Upper bound of $S=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$

EDIT: How can I find a good upper bound to this quantity ? $$S_{n,m}=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$$ where $P=\min\{m,n\}$ et $Q=\max\{m,n\}$.
3
votes
4answers
142 views

Proving Combinatorical Summation: $n!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n$ [duplicate]

been stuck with this question for the last few hours, any help would be appreciated. $$ {\large n! = \sum_{k = 0}^{n}\left(-1\right)^{k}{\,n\, \choose \,k\,} \left(\,n - k\,\right)^{n}} $$ what I ...
3
votes
2answers
36 views

show that these two equation holds by binomial theorem

I know the binomial theorem, but I have no idea how to simplify this. I tried to write it as (y+x)^n+(y+x)^n-(y+x)^0+(y+x)^n-(y+x)^1+...+(y+x)^n-(y+x)^(n-1), but it didnt work out.
3
votes
1answer
47 views

A combinatorics question on a sequence of binomial coefficents

On a past-paper of a Combinatorics exam I will be taking they ask the question: Prove that for $k$ odd and greater than 1, the sequence of numbers $\binom{k}{1}, \binom{k}{2}, ..., ...
3
votes
2answers
133 views

$\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$?

Is it true that $\sum_{k=1}^{m+n} \binom {m+n}k k^m (-1)^k=0 , \forall m,n\in \mathbb N$ ? I feel that it is true because if we define $H_1 (x,r)=rx(1+x)^{r-1}$ , and $H_{m+1}(x,r)=x \dfrac d ...
3
votes
3answers
71 views

undetermined coefficients. What am I doing wrong?

I am having some trouble to solve the following differential equation for the undetermined coefficient: $$ y''+2y'+y=xe^{-x} $$ I have been watching some videos on youtube and done some reading but ...
3
votes
2answers
81 views

Arithmetical proof of $\cfrac{1}{a+b}\binom{a+b}{a}$ is an integer when $(a,b)=1$

When $(a,b)=1$, $\cfrac{1}{a+b}\binom{a+b}{a}$ refers to the number of paths from one corner to its opposite corner of an $a\times b$ lattice that lies completely above (or below) the diagonal. ...
3
votes
1answer
139 views

Find the coefficient of $x^m$ in the expansion $(1 + ax + bx^2)^n$

Find the coefficient of $x^m$ in the expansion of $(1 + ax + bx^2)^n$ One approach would be: Let $p = 1+ax$ and $q = bx^2$ Now expand $(p+q)^n$ and then expand $p$ and $q$ individually. But ...
3
votes
3answers
142 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 ...
3
votes
1answer
155 views

How do i reduce this expression of binomial coefficients

I was solving a problem and am stuck with this expression. Any leads on how can I simplify this expression? $$\frac{{\sum\limits_{x=Q}^{N-P+Q} (x-Q) \binom{x}{Q} ...
3
votes
2answers
98 views

What is the exponent of the last term of $(2x^2+3y^3)^{10}$?

What is the exponent of the last term of: $$(2x^2+3y^3)^{10}$$ Hi! I'm sorry if this question seems a bit amateurish. I'm quite confused with this question that was asked in a quiz about binomial ...
3
votes
1answer
448 views

Number of possible triangle for the given triangle.

An equilateral triangle has n equally spaced dots on each side. How many triangles can be formed (of any size)? Analysis If there are n dots on each side then total no of dots =n(n+1)/2 Number of ...
3
votes
1answer
483 views

Combinatorial Argument

Can you give a Combinatorial argument that $$\binom{3n}{3}=3\binom{n}{3}+(3)(2)\binom{n}{2}\binom{n}{1}+\binom{n}{1}\binom{n}{1}\binom{n}{1}?$$
3
votes
1answer
56 views

Proving a certain sum is 1 [duplicate]

I'd like to prove that, for any $M,N\in\mathbb{N}$ with $M\leq N$, and any $n\in\mathbb{N}$ with $n\leq M$, the sum: $$\sum\limits_{k=0}^n\frac{\binom{M}{k}\!\!\binom{N-M}{n-k}}{\binom{N}{n}}=1.$$ I ...
3
votes
3answers
73 views

Find $k$ given that ${14 \choose k} = {14 \choose k-4}$

Ok, so I stumbled upon the question on the title these days, when going over Apostol's Calculus I. Now, because of the placement of the question in the exercises section, I'm convinced that the book ...
3
votes
1answer
27 views

Show by committee selection argument

First post in Stack Exchange and feel bad to be in need of help. But, I'm having a hard time understanding this one or rather showing the argument. $\binom{n}{k} = \binom{n-2}{k-2} + ...
3
votes
3answers
110 views

Evaluate the sum

I need to evaluate the following sum, which depends on $n \in \mathbb N$ (call it $S(n)$ if you will) $$ \sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$$ where $f$ defined over $\mathbb N$ is ...
3
votes
3answers
57 views

Sum of products of binomial coefficients

In a proof I've come across the following identity: $$ \sum_{l=0}^{n-j} \binom{M-1+l}{l} \binom{n-M-l}{n-j-l} = \binom{n}{j} $$ I see that it's right, when plugging in numbers, but I don't see the ...
3
votes
2answers
102 views

Simplify a triple sum

I need to find a closed form for this summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m}\choose{k}}}{j{m\choose j}}r^{k-j+i}$$ I posted this a long time ago, but today I found out ...
3
votes
3answers
140 views

Prove an equation about binomial coefficients

Could we prove: $ \sum_{k} \binom{2k}{k}\binom{n+k}{m+2k} \frac{(-1)^k}{k+1} = \binom{n-1}{m-1}$ when $m,n \in N$
3
votes
1answer
48 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 ...
3
votes
2answers
79 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 ...
3
votes
3answers
211 views

Find the 100th derivative of $x \sinh(2x)$

If $f(x) = x \sinh(2x)$, find $f^{({100})}(x)$. My (Incorrect) working so far: Using Leibniz' Formula for derivatives: $$(fg)^{(n)}=\sum_{k=0}^n{n\choose k}f^{(k)}g^{(n-k)}$$ ...
3
votes
2answers
87 views

For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$

Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that $(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.) The answer is all powers of 2, and it's fairly simple ...
3
votes
1answer
88 views

Bertrand's postulate proof

Regarding http://michaelnielsen.org/polymath1/index.php?title=Bertrand%27s_postulate I think the last inequality should be $4^{n/3}\le(2n+1)(2n)^{\sqrt{2n}}$. But even when the RHS is decreased from ...
3
votes
1answer
72 views

Evaluating Sums Combinatorially

Consider the following finite sums: (1) $\sum k(k!)$ for k from 1 to n (2) $\sum (k-1)(n-k)$ from 1 to n I am trying to determine how to evaluate these sums combinatorially. It seems the first is ...
3
votes
3answers
296 views

Induction proof of $\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$

Does anynone have some hints to prove the following equation by induction for all $n\geq 1$ and $m\in\mathbb{Z} $ $$\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$$ use for ...
3
votes
1answer
52 views

Binomial coefficient help?

I'm studying for my exams and would appreciate any help with binomial coefficients. I think I got the idea but having trouble with a specific one: Q) If a there are 11 dogs and 9 cats: a) How many 7 ...
3
votes
3answers
116 views

Probability someone's phone will ring during a movie?

Trying to figure out what the probability is that in a room of 200 people what the probability that at least one will get a phone call during a certain time window... In this case 2 hours ...
3
votes
1answer
139 views

Choosing k Multisets from [n]

We are to play a lottery game where five numbers are drawn out of [90], but the numbers drawn are put back into the basket right after being selected. To win the jackpot, one must have played the same ...
3
votes
2answers
282 views

Lower Bound of Central Binomial Coefficients

I would like to prove by induction the following inequality: $\frac{4^n}{n+1} < \binom{2n}{n}$, for all natural numbers n > 1. Any hints?
3
votes
2answers
124 views

A combinatorial exercise

Suppose to have a jar containing 100 coins. I want to count the possibile configuration with pennies, nickels, dimes, quarters and half-dollars. This is what I have done, but I realized that it's ...
3
votes
1answer
264 views

binomial expansion

$\displaystyle \binom{n}{k}=\binom{n-1}{k} + \binom{n-1}{k-1}$ $\displaystyle \left(1+x\right)^{n} = \left(1+x\right)\left(1+x\right)^{n-1}$ how do I use binomial expansion on the second equations ...
3
votes
1answer
376 views

Finding a simple expression - Binomial Theorem

How does one find a simple expression of the one below applying the binomial theorem: $$\sum_{k=1}^n k \cdot 2^k{ n \choose k}$$ Edit: $\frac{d}{dx}(x^k)=kx^{k-1}$ $(1 + x)^n = \sum_{k=0}^n { n ...
3
votes
1answer
47 views

Proving a Binomial Identity

Can you please help me with problem 25. I need to prove that $f(n+1)=2 f(n)$, where $f(n)$ is the LHS of the expression, from there on I can do it my self. I have tried using the binominal theorem ...
3
votes
1answer
34 views

Growth of ratio of binomials polynomial or exponential?

Is the growth of $$ \dfrac{\binom{2n}{\sqrt{n}}}{\binom{n}{\sqrt{n}}} $$ polynomial or exponential (or other kind of growth) in $n$? I tried using the Stirling's approximation, which gives ...
3
votes
2answers
98 views

Sums of binomial coefficients

Does anyone know something about the following sums? $$ S_m(n)=\sum\limits_{k=o}^n(-1)^k{mn\choose mk} $$ Notice that $S_m(n)=0$ for odd $n$, so we only consider $S_m(2n)$. It holds that $S_0(2n)=1$, ...
3
votes
1answer
89 views

Combinatorial Analysis: Fermat's Combinatorial Identity

I was looking through practice questions and need some guidance/assistance in Fermat's combinatorial identity. I read through this on the stack exchange, but the question was modified in the latest ...
3
votes
1answer
53 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...