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)

0
votes
4answers
41 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
126 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
50 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
53 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 ...
2
votes
2answers
58 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
37 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
38 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
26 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
41 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
65 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
128 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
21 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
55 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
54 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
176 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
105 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
658 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! ...
6
votes
3answers
138 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
66 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
35 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
77 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
69 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
34 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
78 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
86 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
72 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
124 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
53 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
33 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 ...
1
vote
1answer
27 views

Evaluation of $\sum\limits_{i = 0}^s {\left( {\begin{array}{*{20}{c}} q \\ {{2^i}} \end{array}} \right)}$

Assume that $q=2^s$ for some non-negative integer $s$. Is there any simple formula for: $$\sum\limits_{i = 0}^s {\left( {\begin{array}{*{20}{c}} q \\ {{2^i}} \end{array}} \right)}?$$
0
votes
1answer
140 views

Combinatorial proof (multi choose)

I'm struggling to explain why these two sides are equal in a non algebraic way. Basically I'm looking for a combinatorial proof of why these sides are equal. I know they are equal by algebra. N ...
5
votes
3answers
43 views

Find the summation $\sum_{k=0}^n (-1)^k \binom{n}{k}\frac{1}{s+k}$

Anyone can help me finding this summation: $$ \sum_{k=0}^n (-1)^k \binom{n}{k}\frac{1}{s+k}. $$ Where there is a similar one with known answer $$ \sum_{k=0}^n (-1)^k ...
0
votes
1answer
24 views

If $C_0,C_1,C_2,\cdots C_n$ denotes the binomial coefficients in the expansion of $(1+x)^n$ then $\sum^n_{r=0}\sum^n_{s=0} (C_r+C_s)$ =?

Problem : If $C_0,C_1,C_2,\cdots C_n$ denotes the binomial coefficients in the expansion of $(1+x)^n$ then $\sum^n_{r=0}\sum^n_{s=0} (C_r+C_s)$ = ? Solution : We have : $\sum^n_{r=0}\sum^n_{s=0} ...
2
votes
1answer
217 views

Counting binary strings that have atmost k consecutive 0's

I know how to count how many binary strings with length n and having exactly k 0's are there but i am not able to find a way to count the number of binary strings that have exactly x 0's and y 1's and ...
3
votes
2answers
45 views

Silly mistake on evaluating the sixth term of $\left (\frac{a}{b}+\frac{b}{a^2}\right)^{17}$?

I am trying to evaluate the sixth term of $\displaystyle \left (\frac{a}{b}+\frac{b}{a^2}\right)^{17}$ with the binomial theorem. I've done the following: The sixth term might be the term for $k=5$ ...
1
vote
2answers
61 views

n-th Derivative

It can be proven the for a function $h(x)=f(x)g(x)$, letting $f^{(k)}(x)=\frac{d^k}{dx^k}f(x)$ and $g^{(k)}(x)=\frac{d^k}{dx^k}g(x)$ then the n-th derivative, for n is an integer is: ...
6
votes
2answers
165 views

What is the coefficient of $x^{25}$ in $(x^3 + x + 1)^{10}$?

Here's what I have so far on the off chance that my thinking is correct... So using Vieta's the coefficient of the $x^{25}$ should be $-(r_1r_2r_3r_4r_5+r_1r_3r_4r_5r_6+...+r_6r_7r_8r_9r_{10})$ Since ...
11
votes
5answers
227 views

Sum $\displaystyle \sum_{n=i}^{\infty} {2n \choose n-i}^{-1}$

$\displaystyle \sum_{n=i}^{\infty} {2n \choose n-i}^{-1}=\sum_{n=i}^{\infty} \frac {1}{{2n \choose n-i}}$ is a very interesting one. Here is what I have from WolframAlpha. $\displaystyle ...
5
votes
1answer
85 views

Binomial identity $\binom{0}{0}\binom{2n}{n}+\binom{2}{1}\binom{2n-2}{n-1}+\binom{4}{2}\binom{2n-4}{n-2}+\cdots+\binom{2n}{n}\binom{0}{0}=4^n.$ [duplicate]

Prove the identity $$\binom{0}{0}\binom{2n}{n}+\binom{2}{1}\binom{2n-2}{n-1}+\binom{4}{2}\binom{2n-4}{n-2}+\cdots+\binom{2n}{n}\binom{0}{0}=4^n.$$ This is reminiscent of the identity ...
1
vote
1answer
35 views

Expected number of passengers for the flight

One of the interview questions that I was asked was : The small commuter plane has 30 seats. The probability that any particular passenger will not show up for a flight is 0.1, independent of ...
2
votes
1answer
36 views

Generalized Case: Three Consecutive Binomial Coefficients in AP

This is a generalization of my earlier question here posted recently, and is a more interesting one. Three consecutive binomial coefficients $$\binom n{r-1},\binom nr, \binom n{r+1}$$ are in an AP ...
1
vote
1answer
45 views

Three Consecutive Binomial Coefficients in AP

I came across an interesting pattern in the Pascal triangle, and thought I would post it as a problem here. Given three consecutive binomial coefficients $$\binom n{r-1},\binom nr,\binom n{r+1}$$ ...
0
votes
0answers
24 views

Sampling combinations (from a binomial coefficient) without replacement

The total number of combinations of $k$ items out of $n$ total is $n \choose k$, or a binomial coefficient. This can be a very large number even for pretty small $n$. The binomial coefficient ...
1
vote
1answer
46 views

Asymptotic relation between specific binomial coefficient and exponential function

I need to determine the asymptotic relationship between the functions: $$f_1(n)={n\choose{\lfloor{n\over{2}}\rfloor}}, f_2(n)=7^{\sqrt{n}}$$ (I'm going to just assume $n$ is always even.) I've ...
4
votes
1answer
118 views

Growth of ratio based on sum of squared binomial identity

It is a well-known identity that $$\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}.$$ By symmetry of the binomial coefficients, this means the ratio ...
0
votes
1answer
31 views

How do we express binomial coefficients as linear expressions?

I have a question from Putnam and Beyond. It says that "...for some positive integers m and k, the binomial coefficient $m \choose k$ is a linear combination of $m^k$, $m \choose {k−1}$ , $\dots$ , ...
0
votes
0answers
29 views

Sum of binomial coefficients multiplied

How to approximate the next one relative to $m$ $$ \sum_{k=0}^m \binom {n}{n-k} (n-k-\frac k{\sqrt{2}})^2? $$ Or for example the simplier sum $$ \sum_{k=0}^m \binom {n}{n-k} (n-k)^2? $$
4
votes
2answers
168 views

Unusual binomial sum: $\sum_{d=k}^{n} {d \choose k} p^{d}(1-p)^{n-d}$

Does anyone know how to simplify the following sum? It's been giving me and everyone else I've showed it to quite a bit of trouble. I'm quite confident that this should simplify, but I just can't seem ...