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)

7
votes
6answers
342 views

Prove that $\binom n2 + \binom {n-1}2$ is always a perfect square

Prove that if $n$ is a positive integer and $n >1$: $$\binom n2 + \binom {n-1}2$$ is always a perfect square. I know we need to turn that into a binomial, but I can't follow how. Please note I'm ...
0
votes
4answers
46 views

Proving a formula with binomial coefficient

Is this formula true? How can I prove it? $$\sum_{s=0}^{n-1}\binom{n-1}{s}2s =2^{n-1}(n-1)$$ Thanks!
0
votes
1answer
35 views

Identity of sum of binomial coefficients

I'm struggling to understand the following derivation where $n$ is a positive integer. $$ \sum_{\ell=0}^n {n \choose \ell} 2^\ell \log 2^\ell = n \sum_{\ell=0}^{n-1} {n-1 \choose \ell} 2^{\ell+1}. $$ ...
3
votes
2answers
203 views

Proving that $\Phi_{t*}[\mathbb{Y},\mathbb{Z}]=[\Phi_{t*}\mathbb{Y},\Phi_{t*}\mathbb{Z}]$

Let $\mathbb{X},\mathbb{Y}$ be vector fields on $\mathbb{R}^n$. Let $\Phi_t$ denote the flow of $\mathbb{X}$. Define $L_{\mathbb{X}}\mathbb{Y}=[\mathbb{X},\mathbb{Y}]$. You are given that ...
1
vote
1answer
88 views

How to prove this Catalan number identity

Catalan number is $\displaystyle C_n= \frac{1}{n+1}\binom{2n}{n}$. How to prove that $$C_{2n-1} = \sum_{k=0}^{n-1}\left(\binom{2n-1}{n-k-1}-\binom{2n-1}{n-k-2}\right)^2$$ for $n\geq 1$. Thank you.
4
votes
3answers
131 views

How to prove combinatorial identity $\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose s}{s\choose m-s}$?

The following combinatorial identity have been verified via maple, but I can not prove it. Who can prove it without WZ mehtod? $$\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose ...
1
vote
2answers
105 views

How prove this identity$\sum_{k=0}^{n}\binom{2k}{k}\binom{n+k}{2k}(s-t)^{n-k}t^k=\sum_{k=0}^{n}\binom{n}{k}^2s^{n-k}t^k$

Today I see a paper,and this author say it is easy to have this identity.But I take sometimes to prove it,and I can't prove it. show this following identity holds for any real $s$ and $t$ and any ...
0
votes
0answers
27 views

Why we can use normal distribution to approximate binomial distribution when n is large enough?

Prove why we can use normal distribution to approximate binomial distribution when n is large enough. Hint: Try to read something on bernoull ...
0
votes
2answers
35 views

Generating functions and central binomial coefficient

How would you prove that the generating function of $\binom{2n}{n}$ is $\frac{1}{\sqrt{1-4y}}$? More precisely, prove that( for $|x|<\frac{1}{4}$ ): ...
3
votes
0answers
92 views

Prime factors of binomials

Is it true that for each $n\geq 2$ there are two primes $p, q$ such that (at least) one of them divides $\binom{n}{k}$ for each $1\leq k\leq n-1$? Examples: For $n=6: \binom{6}{1}=6; ...
2
votes
1answer
28 views

If $a_n = \sum^n_{r=0} \frac{(\ln10)^n}{r! (n-r)!}$ for $n \geq 0$ …

Problem: If $a_n =\sum^n_{r=0} \frac{(\ln10)^n}{r! (n-r)!}$ for $n \geq 0$ then find the value of $a_0+a_1+a_2+\cdots \infty$ My approach: $a_n = \sum^n_{r=0} \frac{(\ln10)^n}{r! (n-r)!}$ $= ...
1
vote
0answers
62 views

General solution for a combinatorial problem

I want to find a general solution for a problem. I explain the problem with an example. $\underline{Problem}:$We have a matrix $A$ of size $M \times N$, where $M <N$. We choose sub-matrices of ...
1
vote
1answer
46 views

Growth of binomial coefficient

I am interested in the growth of the binomial coefficient ${n\choose n^a}$ for some fixed $a\in (1/2,1]$. Of course, for $a=1$ the binomial constantly equal to $1$. For $a<1$, computations suggest ...
1
vote
2answers
52 views

Probability involving bread and jam!

SO, I drop a piece of bread and jam repeatedly. It lands either jam face-up or jam face-down and I know that jam side down probability is $P(Down)=p$ I continue to drop the bread until it falls jam ...
0
votes
1answer
23 views

Lie derivatives of vector fields and the binomial expansion

Given the Jacobi identity $[\mathbb{X},[\mathbb{Y},\mathbb{Z}]]+[\mathbb{Y},[\mathbb{Z},\mathbb{X}]]+[\mathbb{Z},[\mathbb{X},\mathbb{Y}]]=0$ and that the Lie derivative of a vector field is ...
1
vote
1answer
46 views

Finite natural summation that leads to double exponential results

We know that $$f(n)=\sum_{i=0}^n\binom{n}{i}=2^n$$ and $$g(n)=\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}.$$ Are there any finite natural sums that lead to $2^{2^n}$ or $2^n2^{2^{n-1}}$ results other than ...
2
votes
4answers
48 views

A finite binomial sum

Is their an exact expression for the following sequence involving binomial coefficients $$\sum_{i=0}^n i\binom{n}{i}?$$
1
vote
1answer
29 views

Multinomial identity - guidance needed

I need hints on a direction to proove that $$\displaystyle\prod_{k=1}^{n} {{k+1\choose2}\choose k} ={{n+1\choose2}\choose1,2,3.....,n}$$ Any ideas?
1
vote
0answers
20 views

Closed form for binomial coefficient series

If $6|n$, is there a closed form for $$\sum_{t=\frac{n}{2}}^n\binom{\frac{n^2}{3}}{t}\binom{\frac{2n^2}{3}}{n-t}?$$
0
votes
4answers
39 views

proof of summation using $\displaystyle \binom{n}{r}$

Prove that $\sum_{r=0}^{n} \binom{n}{r}2^r = 3^n$ for $n \in \mathbb P$. "Hint: give me an argument having to do with the number of strings of length $n$ with $3$ symbols."
2
votes
2answers
86 views

How many positive integer solutions are there to the equation $(a + b + c + d) < N$?

Here's my attempt: My thinking is that this is the same as finding all the non-negative $a, b, c, d$ such that $a + b + c + d = M$ where $M \in \{0, 1, ..., N - 4\}$. Which further reduces to a stars ...
0
votes
0answers
41 views

Closed Form for a Sequence

I have come across this sequence $$a_0 = -2, a_1 = 5, a_2 = -28, a_3 = 255$$ and, in general $$a_n = -\frac{1}{2}\bigg(\sum_{i=1}^n \binom{2n+4}{2i}a_{n-i} + \binom{2n+4}{2n+1}\bigg)$$ I've tried ...
0
votes
1answer
50 views

A binomial inequality

I've tried both expanding the binomials as well as trying to deduce something from the hypergeometric distribution, but I don't see how to prove: $${N\choose n}^{-1}\sum_{i\geq j}{M\choose ...
3
votes
2answers
54 views

Average number of trials until drawing $k$ red balls out of a box with $m$ blue and $n$ red balls

A box has $m$ blue balls and $n$ red balls. You are randomly drawing a ball from the box one by one until drawing $k$ red balls ($k < n$)? What would be the average number of trials needed? To ...
0
votes
2answers
36 views

Ratio of 2 Sums of products of binomial coefficients

I want to prove that for $k \ even, 0 \leq k<n, n\in \mathbb{N}$: $-\frac{1}{(2n-3-k)(k+2)}\sum \limits_{i=0}^{k} \frac{(-1)^{i} 2^{i} (2n-2-i)!}{(n-1-i)!i!(k-i)!}=\sum \limits_{i=0}^{k+2} ...
0
votes
1answer
37 views

prove binomial multiplication less than 1

please show me how to prove the following. Given $m >= n,n\geq2$ prove $\binom mn$ $\cdot \frac{1}{n^m} < 1$ ------UPDATE-------- Given the inequalities: $(\frac{m}{n})^n \le \binom mn \le ...
1
vote
1answer
22 views

Binomial Formula conversion

I saw an answer in stackoverflow about binomial here The answerer provide some nice explanation how can binomial can be calculated by pascal triangle. But I'm still not sure how to convert this ...
1
vote
1answer
40 views

Number of overlapping columns

Consider an $m \times n$ matrix $A$ with $m<n$. It is well-known that number of ways of choosing $k$ columns out of $n$ from $A$ is $\binom{n}{k}$, where ($k<m<n$). What is the number of ways ...
2
votes
1answer
44 views

Combinatorics: Number of Six-Card Hands That Can Be Dealt from r Combined Decks

I am having trouble solving this combinatorial problem dealing with the number of different card hands possible from multiple decks of identical cards. Here is the exact question: Use a combinatorial ...
1
vote
2answers
122 views

Compute the following sum $ \sum_{i=0}^{n} \binom{n}{i}(i+1)^{i-1}(n - i + 1) ^ {n - i - 1}$?

I have the sum $$ \sum_{i=0}^{n} \binom{n}{i}\cdot (i+1)^{i-1}\cdot(n - i + 1) ^ {n - i - 1},$$ but I don't know how to compute it. It's not for a homework, it's for a graph theory problem that I try ...
1
vote
0answers
20 views

binomial coefficient and recurrence relation [duplicate]

any hints on how to solve the recurrence relations for the following binomial coefficient \begin{equation} {n \choose k}=\begin{cases} 1, & \text{if $k\in\{0,n\}$}.\\ {n-1 \choose ...
0
votes
1answer
24 views

Binomial distribution “matix of results”

I am having trouble understanding the formal definition of the binomial distribution. $$f(k;n,p) = \Pr(X = k) = {n\choose k}p^k(1-p)^{n-k}$$ Or rather how I "transform" the definition to suit my ...
2
votes
1answer
50 views

Using Stirling's formula to uniformly bound Bernoulli success probabilities

In this paper, the authors say that for any $\gamma \in [1/2,1)$, there is a positive constant $B=B(\gamma)$ such that for any $n$, $$ \sum_{n\gamma\leq k \leq n} \binom{n}{k} \leq B n^{-1/2}2^{n ...
2
votes
2answers
50 views

Proof by induction, or without it if possible?

I was given a task to prove: $$ \frac{1}{(x+1)(x+2)\ldots(x+n)}=\frac{1}{(n-1)!}\sum_{i=1}^n\binom{n-1}{i-1}\frac{(-1)^{i-1}}{x+i} $$ I am almost 100% sure this is best solved by induction but to be ...
3
votes
3answers
163 views

A specific kind of probabilistic proof for central binomial coefficients

I'm looking for a specific kind of proof of the statement $$ \lim_{n\to\infty} \frac1{4^n}\binom{2n}{n} = 0 $$ I know how to show this using Stirling's formula; I have seen the very nice elementary ...
6
votes
1answer
86 views

Combinatorial Interpretation of a Binomial Identity

The original post due to David Peterson is here. How to establish the following Binomal identity combinatorially: $$\displaystyle \sum\limits_{k = 0}^{[n/2]}\binom{n-k}{k}2^k = ...
18
votes
1answer
638 views

How to prove a double sum is always an integer?

I have verified the following double sum is always an integer for $s$ up to $1000$ via Maple. But I can not prove it. Proofs, hints, or references are all welcome. Thanks! ...
4
votes
2answers
97 views

Show that $\sum\limits_{i=0}^{n/2} {n-i\choose i}2^i = \frac13(2^{n+1}+(-1)^n)$

While doing a combinatorial problem, with $n$ being even, I came up with the expression $$\sum_{i=0}^{n/2} {n-i\choose i}2^i$$ for which I used wolfram to get a closed form expression of ...
1
vote
8answers
55 views

Binomial coefficient proof for ${n\choose m-1}+{n\choose m}={n+1\choose m}$

I need to prove the following: ${n\choose m-1}+{n\choose m}={n+1\choose m}$, $1\leq m\leq n$. With the definition: ${n\choose m}= \left\{ \begin{array}{ll} ...
1
vote
3answers
31 views

${n\choose m}={n\choose n-m}$ Proof

I need to prove the following: ${n\choose m}={n\choose n-m}$ With the definition: ${n\choose m}= \left\{ \begin{array}{ll} \frac{n!}{m!(n-m)!} & \textrm{für ...
4
votes
4answers
74 views

Proof $\displaystyle \binom{p-1}{k}\equiv (-1)^k \mod{p}$

Proof that if $p$ is a prime odd and $k$ is a integer such that $1≤k≤p-1$ , then the binomial coefficient $$\displaystyle \binom{p-1}{k}\equiv (-1)^k \mod p$$ This exercise was on a test and I could ...
3
votes
2answers
67 views

If $(1+x+x^2)^{25} =\sum^{50}_{r=0} a_r x^r$ then …

If $$(1+x+x^2)^{25} =\sum^{50}_{r=0} a_r x^r$$ then find : $\sum^{16}_{r=0} a_{3r} =$ My approach : let (1+x) =t therefore, $(1+x+x^2)^{25} =\sum^{50}_{r=0} a_r x^r$ =$(1+x+x^2)^{25} = ...
1
vote
1answer
30 views

Prove of an addition theorem for the general binomial coefficients

Prove that: $\sum_{k=0}^n \binom{s}{k} \binom{t}{n - k} = \binom{s + t}{n}$ for all $s, t \in\Bbb C $, $n \in N\cup {0}$. That's pretty much all I'm given, and therefore, I haven't come quite far ...
1
vote
1answer
75 views

Induction Proof that $\sum_{i=0}^n 3^{n-i} {n \choose i} = \sum_{i=0}^n (-1)^i 5^{n-i} {n \choose i}$

Show that for all $n\geq0$ $$\binom{n}{0}3^n+\binom{n}{1}3^{n-1}+\dotsc+ \binom{n}{n-1}3^{1}+\binom{n}{n} $$ $$= \binom{n}{0}5^n-\binom{n}{1}5^{n-1}+\binom{n}{2}5^{n-2}-\binom{n}{3}5^{n-3}+\dotsc ...
-1
votes
1answer
49 views

Coefficeient of $x^k$ in $(1+x)^n$ when $n<0$

I know this is a very basic question. But I simply cannot derive the final answer. We have the alternate form of binomial theorem if we want to deal with negative exponents. ...
1
vote
1answer
68 views

combinatorial proof that $\sum_{i=r}^{n}(2i-r)\binom{i-1}{r-1}^2=r\binom{n}{r}^2$

I came accros the following identity when I was doing an olympiad problem (IMOSL 1997 - 13), but I'm having troubles finding a combinatorial interpretation. Can someone help me? ...
2
votes
2answers
68 views

Do I use induction or is there another way to prove $\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$? [duplicate]

Prove the following statement is true: $$\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$$. Since $\binom{r}{r}=\binom{n}{r}=\dfrac{n!}{r!(n-r)!}$, is that to form a basis step? If ...
2
votes
3answers
108 views

How to prove this statement: $\binom{r}{r}+\binom{r+1}{r}+\cdots+\binom{n}{r}=\binom{n+1}{r+1}$

Let $n$ and $r$ be positive integers with $n \ge r$. Prove that Still a beginner here. Need to learn formatting. I am guessing by induction? Not sure what or how to go forward with this. Need help ...
0
votes
2answers
48 views

Sum function operation: coefficient.

I have problem with the sum: $$ \sum_{k=0}^n \dbinom{n}{k}(\cos \alpha)^k(i\sin \alpha)^{n-k}\,\, $$ Apparantly, I have an imaginary unit therefore I need to distinguish even and odd powers of $i$ to ...
0
votes
1answer
32 views

Definition of binomial coefficient

I have this problem that I am a bit unsure about how to proceed forward with. Problem: Show that $n{\binom{m+n}{m} = (m+1)\binom{m+n}{m+1}}$ for all integers n, m > 0. In the solution it says that ...