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)

6
votes
3answers
129 views

Evaluation of $\sum_{k=0}^n{n\choose k}^2u^k$

I am trying to evaluate the finite sum \begin{equation} f(u)=\sum_{k=0}^n{n\choose k}^2u^k,\quad 0<u\le1 \end{equation} In an first attempt, I think of the generating function \begin{equation} ...
1
vote
2answers
104 views

Proof that $\dfrac{1}{e^x}=e^{-x}$ without converting it to $e^{x}e^{-x}=1$.

I want to show that $\dfrac{1}{e^x} = e^{-x}$ from the Taylor expansion of $e^x$. To express $\dfrac{1}{e^x}$ as a power series, I let: $$ \left(\dfrac{1}{0!}x^0 + \dfrac{1}{1!}x^1 + ...
0
votes
1answer
46 views

How to evaluate $\sum_{k=0}^{n} \alpha^k \binom{n}{k}$?

I am trying to show that the function that satisfies $f^\prime(x)=f(x)$ with $f(0)=1$ behaves in an exponential way (in other words, I want to justify writing it as $e^x$). I need to show that: $$ ...
2
votes
2answers
27 views

Appromixation of binomial coefficient for large numbers

In the context of writing a program for sortition, I would like to know if the entropy of my input random variable in large enough to potentially produce all outcome of my sortition problem. Let say ...
2
votes
1answer
28 views

Sum of combinations of the n by consecutive k

In a book, I found that the sum of combinations: $\binom{n}{k} + \binom{n}{k+1} +\cdots+ \binom{n}{n}$, where k starts from 0, equals $2^n$. It is possible to express this statement via sum: $2 + ...
2
votes
2answers
73 views

Alternating sum of binomial coefficients is equal to zero [duplicate]

Prove without using induction that the following formula:$$\sum_{k=0}^n (-1)^k\binom{n}{k}=0$$ is valid for every $n\ge1$. Progress For each odd $n$ we can use the ...
2
votes
2answers
78 views

How to prove $n! > n^a$ for all $a\in \mathbb{R}$ (for sufficiently large $n$)?

I've encountered a proof which claims $n! > n^2$ for sufficiently large $n$. I tried using induction to prove it for an arbitrary $a$: $n! > n^a$. Lets assume the claim is true for $n$: $n! ...
1
vote
1answer
33 views

Verification of binomial coefficient congruence $\binom{jp}{j}\equiv j\binom{p}{j}\pmod{p^2}$

Let $j\ge 1$ be an integer and $p$ prime. Is it true that $$\binom{jp}{j}\equiv j\binom{p}{j}\pmod{p^2}$$ My work No, take $j>p$, then the RHS is zero, while the LHS need not be $\equiv 0$. For ...
6
votes
4answers
145 views

How prove this inequality $(1+\frac{1}{16})^{16}<\frac{8}{3}$

show that $$(1+\dfrac{1}{16})^{16}<\dfrac{8}{3}$$ it's well know that $$(1+\dfrac{1}{n})^n<e$$ so $$(1+\dfrac{1}{16})^{16}<e$$ But I found this $e=2.718>\dfrac{8}{3}=2.6666\cdots$ ...
0
votes
0answers
24 views

is binomial congruence given in article true or false?

I'm just reading a paper which, on its page 3, Application 8, claims the following: $$\binom{k+sp}{j}\equiv\binom{k}{j}\pmod{p}$$ where $p\ge 1$, $s\ge 1$, $k\ge 1$ and $p\not\mid j$ (actually, it ...
1
vote
3answers
63 views

Showing that $\sum\limits_{k=2}^n {k\choose2} = {{n+1}\choose 3}$ for integers $n\geq 2$

I'm trying to prove that $\sum\limits_{k=2}^n {k\choose2} = {{n+1}\choose 3}$ for integers $n\geq 2$. I figured induction was the way to go, so I tried. This is what I've accomplished so far: Proved ...
-1
votes
2answers
57 views

Squared binomial paradox?

When you square this $$(5-2)^2$$ you will get 49 $$ 5^2 - 2 * 5 * (-2) + (-2)^2$$ $$25 + 20 + 4 = 49$$ but if you do it like this (5-2) * (5-2) you will get 9 $$ 5(5-2) - 2(5-2)$$ $$25-10-10+4$$ ...
1
vote
3answers
26 views

refactoring binomial with negative power

I am reading Calculus Made Easy where in Chapter IV: $$(x+dx)^{-2}$$ Is refactored as: $$x^{-2}\left(1+\frac{dx}x\right)^{-2}$$ Could someone give me an insight into this refactoring? I can see from ...
0
votes
1answer
34 views

The sum of the product of two binomial coefficients

This is really phsycics related question with mathematics behind it. In my physics book there's the following relation: ...
1
vote
2answers
44 views

Problem involving summation and binomial coefficient

I have been fighting with this but I'm really not getting anywhere. $$\sum_{0\leq2k\leq n}\binom{n}{2k}2^k\equiv0\pmod 3$$ $$iff$$ $$n\equiv2\pmod 4$$ Hint: Consider ...
2
votes
1answer
20 views

Relating Binomial Coefficients

This question popped up in my revision sheet, and was just wondering on how to do it (this is high-school math by the way, so nothing too complicated please) "Expand $(x+(1-x))^n$, and use this to ...
1
vote
0answers
20 views

The distribution of sum of two binomials with complement success probabilities

It is well-known that if $X$ and $Y$ are independent binomial random variables with parameters $(n_1,p)$ and $(n_2,p)$ respectively, $Z = X+Y$ has a binomial distribution with with parameters ...
3
votes
0answers
79 views

What's so special about binomial coefficients that someone decided to organize them in a triangle?

I know that binomial coefficients are related to figurate numbers (which were studied by Greeks a loooong time ago, because of its connections to geometry). I also understand how the Pascal's triangle ...
-1
votes
1answer
32 views

Binomial Coefficients (2,1) [closed]

What are binomial coefficients? Can someone explain. For example: (2,1). or what (2n,n) means
4
votes
0answers
79 views

Binomial triplets

Solutions to the equation $$\dbinom{a}{n}+\dbinom{b}{n}=\dbinom{c}{n}$$ I will refer to as 'Binomial triplets of order $n$'. These triplets describe simplicial $n$-polytopic numbers that can be ...
2
votes
2answers
77 views

Product rule for simplex numbers

The $n$th triangular number is defined as $T_2(n) = n(n+1)/2$, and there is an interesting product rule for triangular numbers: $$T_2(mn) = T_2(m)\,T_2(n) + T_2(m-1)\,T_2(n-1).$$ The tetrahedral ...
3
votes
3answers
143 views

Evaluation of a sum of $(-1)^{k} {n \choose k} {2n-2k \choose n+1}$

I have some question about the paper of which name is Spanning trees: Let me count the ways. The question concerns about $\sum_{k=0}^{\lfloor\frac{n-1}{2} \rfloor} (-1)^{k} {n \choose k} {2n-2k ...
3
votes
3answers
63 views

difficult problem about binomial coefficients

If $r,m,n\in \mathbb N$ so that $r\le \min \{n,m\}$, then $$\binom{n+m}{r} = \binom{n}{0}.\binom{m}{r}+\binom{n}{1}.\binom{m}{r-1}+...+\binom{n}{r}.\binom{m}{0}.$$ If $\min \{n,m\} < r$, then how ...
0
votes
0answers
41 views

Sum of independent discrete random variable

Here is my attempt of deriving the sum of independent random variable in the discrete case : $\underline{\textbf{Sum of independent random variables}}$ Let $\mathcal{C_1}, \mathcal{C_2}$ be ...
1
vote
1answer
18 views

Question concerning an example of higher derivatives and binomes

I got this exercise form OCW 18.03SC - problem 1G-5b: What is the solution of the following derivative?: $$\dfrac{d^{p+q}}{dx^{p+q}}x^p(1+x)^q$$ I used Leibniz' formula and the only non-zero term ...
2
votes
1answer
24 views

Order of Binomial addition

I was reading up a statement in probability which said that $nC_0 + nC_1 + nC_2 +\dots+ nCm$ is of order $n^m$ where $nCm$ is notation for number of combinations from a collection of $n$ taking $m$ ...
2
votes
1answer
73 views

Find the sum of all coefficients in expansion of $(x^2+2x)^{20}$.

Find the sum of all coefficients in expansion of $(x^2+2x)^{20}$. Is there a specific method or formula for this?
2
votes
2answers
94 views

Proof of equality $\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $ by induction

I have a problem with following equality: $$\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $$ And I would like to use induction in following way: Base: $$ m = n $$ And: $$ ...
2
votes
1answer
53 views

When does $(x+y)^n+(x-y)^n\leq(2x)^n$ hold?

With $n\in\mathbb{N}$, what is the relation between $(x+y)^n+(x-y)^n\leq(2x)^n$ and the values of $x$ and $y$? Or mathematically: $(x+y)^n+(x-y)^n\leq(2x)^n\iff$ the values of $x$ and $y$ are such ...
2
votes
0answers
40 views

How to prove: $pq=\binom{k}{q}-\binom{p}{q}-\binom{k-p}{1}+1$

For any two distinct primes $p, q$ there is a unique integer $k$ such that: $$pq=\binom{k}{q}-\binom{p}{q}-\binom{k-p}{1}+1$$ Where $k$ is the smallest integer greater than $p$ that is relatively ...
0
votes
1answer
62 views

Is this possible or hopeless to try to prove?

If I have $x_1, ..., x_k=o(n)$ and $j=O(1)$. Is it possible to prove something like: $$\sum_{i=1}^k {n \choose j} \left(\frac{x_i}{n}\right)^j \left(1-\frac{x_i}{n}\right)^{k-j} \sim {n \choose j} ...
0
votes
0answers
20 views

Bounding a specific function of binomial coefficients

While trying to directly prove the existence of expander graphs (e.g. http://www.cs.toronto.edu/~avner/teaching/S6-2414/TUT2.pdf), one uses the following inequality: $$\sum_{s=1}^{n/2} ...
3
votes
1answer
28 views

Derivative of Binomial Coefficient wrt k

I've got $\binom{2N}{N-x}$ and I'd like to take the derivative with respect to x. I know that I can take the derivative of $\binom{n}{k}$ w.r.t. n using logarithmic differentiation, but that's not ...
3
votes
3answers
55 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
231 views

How find this sum closed form?

Have this sum have close form $$f(n)=\sum_{k=0}^{n-1}\left(\left(\sum_{i=0}^{k}(-1)^i\binom{n}{i}\right)\cdot\left(‌​\sum_{j=k+1}^{n}(-1)^j\binom{n}{j}\right)\right)$$ Maybe this sum can use ...
4
votes
3answers
166 views

Closed form of a sum of binomial coefficients?

I have the following function: $T_n(d)=\sum\limits_{k=\frac{n-d}{2}}^{\lceil \frac{n}{2} \rceil}{k\choose \frac{n-d}{2}}$ ${n \choose 2k}$, where $n,d\in \mathbb{N}^0$, and $n,d$ have the same ...
4
votes
2answers
115 views

How prove this sum $\sum_{k=0}^{n-1}a_{k}b_{k}=\frac{n}{2}\binom{2n}{n}$

QUestion: show that $$\sum_{k=0}^{n-1}\left(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}\right)\left(\binom{n}{k+1}+\cdots+\binom{n}{n}\right)=\dfrac{n}{2}\binom{2n}{n}$$ My idea: let ...
1
vote
0answers
23 views

How to get a nice approximation of $f(N,s)=\sum_{k=0}^{N}{N \choose k}{k \choose s-k+N}$ when $N>>1$ and $|s|<<N$?

I need to approximate the above sum in order to calculate $\mathbb{E}(s^2)$, which is the expectation value determined by the probability density function $f$ and the position $s$. Any idea?
0
votes
1answer
29 views

For each integer $s$, how many N-tuples with possible elements $\{0, 1, -1\}$ satisfy the condition that the sum of its elements is $s$?

So, we can find the answer using the generating function: $$f(x)=(1+x+x^{-1})^N=x^{-N}\sum_{k=0}^{N}\sum_{m=0}^{k}{N \choose k}{k \choose m}x^kx^m$$ and the number of N-tuples for each integer $s$ is ...
4
votes
4answers
73 views

Conjecture for product of binomial coefficient

Is it true that for any $n, k\in\mathbb N$ $$\frac{(kn)!}{k!(n!)^k} = \prod_{l=1}^k {{ln-1}\choose{n-1}} \quad?$$ I tested it for some small $k$ and $n$, but I don't know how to prove that it is true ...
0
votes
3answers
107 views

Given the sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for it?

Given a sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for this sequence? Is there any optimised approach? My approach: the given series is equal to summation of $\binom{n}{k}$ ...
0
votes
0answers
51 views

Generalized Leibniz Rule

Leibniz Rule states that, $$(f\cdot g)^{(m)}(x)=\sum_{k=0}^m \binom{m}{k} f^{(m-k)}(x)g^{(k)}(x).$$ Writing this with differentiation denoted by $D$, we might say $$D^m (fg) = \sum_{k=0}^m ...
6
votes
4answers
203 views

Truncated alternating binomial sum

It is easily checked that $ \sum_{i = 0}^n (-1)^i \binom{n}{i} = 0$, for example by appealing to the binomial theorem. I'm trying to figure out what happens with the truncated sum $\sum_{i=0}^{D} ...
0
votes
2answers
64 views

A summation with binomial coefficients

Evaluate There seemed to be some problem with stackexchange's math rendering but Ian corrected whatever error was there in the expression.Thanks $$5050 \frac {\left( \sum _{r=0}^{100} \frac ...
1
vote
1answer
26 views

How to find the limit superior of the nth root of the generalized binomial coefficient?

My book says that $$ \varlimsup_{n \to \infty} \sqrt[n]{\left|{\binom{\alpha}{n}} \right|} = 1 $$ where $\alpha \in \mathbb{R} \setminus \mathbb{N} \cup \{ 0 \} $ and $n \in \mathbb{N}$. Where ...
0
votes
1answer
69 views

Multiple sum involving binomial factors

Let $n$ and $m$ be positive integers and let $0 \le j \le n-m-1$. Show that: \begin{align} \sum\limits_{l=m}^{n-j-1} \binom{n-l-1}{j} \binom{l}{m} \binom{n+l}{j} &=\sum\limits_{p=0}^j ...
1
vote
4answers
112 views

The probability that after repeated random drawing from an urn, all balls left in the urn will be red

Problem An urn contains $p$ red and $q$ green balls. Balls are drawn one by one till balls left in the urn are all red. Prove that the probability of this event is $\dfrac {p}{p+q}$. Please note that ...
2
votes
1answer
77 views

A double sum with combinatorial factors

Let $n$, $p$ and $j$ be integers. As a byproduct of some other calculations I have discovered the following identity: \begin{equation} \sum\limits_{p=0}^{j} \sum\limits_{p_1=0}^j \binom{p+p_1}{p_1} ...
0
votes
0answers
42 views

$\sum$ of binomial coefficients inequality

Let $m,n$ be positive integers with $m>n$. When is it true that $$m\cdot 5^{m-1}\cdot 3+\binom{m}{3}\cdot 5^{m-3}\cdot 3^3\cdot 2+\cdots +\binom{m}{2k+1}\cdot m^{m-2k-1}\cdot 3^{2k+1}\cdot ...
2
votes
0answers
26 views

Proving an inequality having binomial coefficients

Suppose that $0 \leq b \leq b+x < a$. How could I prove the inequality \begin{equation} \left(\frac{a-b-x}{a-x}\right)^x \leq \cfrac{\binom{a-x}{b}}{\binom{a}{b}} \leq \left(\frac{a-b}{a}\right)^x ...