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)

4
votes
0answers
34 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 = ...
4
votes
0answers
65 views

How to prove that 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
53 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
49 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
27 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
65 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
60 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
20 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 ...
-2
votes
0answers
18 views

Identities involving binomial coeffcient [duplicate]

Show that $\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+ \cdots +\binom{n}{k}=\binom{n+1}{k+1}$ for all natural numbers $k\leq n$.
-1
votes
0answers
18 views

Probability density fuction [closed]

Suppose $X_1, X_2$ and $Y$ are independent random variables. Find the probability density function of $$S = X_1 + X_2 + Y$$ if $X_1$ is Poisson distributed with parameter $5$, $X_2$ is Poisson ...
-1
votes
1answer
46 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
48 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
65 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
90 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
40 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
30 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
26 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
39 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
36 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
18 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} ...
1
vote
0answers
28 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
44 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
51 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
140 views

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

Working on some contest problems and came across this question. 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 ...
11
votes
5answers
201 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
66 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
25 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
19 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
33 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
16 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 ...
0
votes
0answers
13 views

n-th degree Bezier curve-bernstein polynomial

I want to make a code that will draw n-th degree Bezier curve which would be calculated through Bernstein polynomials.My problem is not related to code writing,but its math kind.Reason I have ...
1
vote
1answer
21 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
110 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
21 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
24 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? $$
3
votes
0answers
87 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 ...
0
votes
0answers
52 views

Relation between Hyperfactorial, Superfactorial, Pascal's Triangle and Binomial Coefficient

I read here that the product of the elements in the $N^{th}$ row of Pascal's triangle is equal to $(n!)^{n+1}/(\prod_{k=1}^n k!)^2$. Let's call the product of elements in the $i^{th}$ row of Pascal's ...
0
votes
1answer
23 views

Rising factorial power

How the expression below can ve proved: $(a + b)^{\overline{n}} = \sum\limits_{j=0}^{n}C_n^j a^{\overline{n-j}}b^{\overline{j}}$ where $x^{\overline{n}}$ - is rising factorial power: ...
2
votes
1answer
142 views

How to solve the equation $\sum_{n=1}^\infty n^{-2}/\binom{n+x}{n} =\frac{3}{2}$ for $x$?

I find this problem on this page. Find $x\in\mathbb{R}$ such that $$\sum_{n=1}^\infty \frac{1}{n^2\displaystyle\binom{n+x}{n}}=\frac{3}{2}$$ Thank you very much.
2
votes
4answers
64 views

Algebric proof for the identity $n(n-1)2^{n-2}=\sum_{k=1}^n {k(k-1) {n \choose k}}$

Prove the identity: $$n(n-1)2^{n-2}=\sum_{k=1}^n {k(k-1) {n \choose k}}$$ I tried using the binomial coefficients identity $2^n = \sum_{k=1}^n {n \choose k}$ but got stuck along the way.
1
vote
1answer
19 views

Proof of identity involving binomial coefficient

My homework assignment was essentially to prove the following binomial coefficient identity: Prove $$\begin{pmatrix} -n \\ k\end{pmatrix} = (-1)^k \begin{pmatrix} n+k-1 \\ k\end{pmatrix}$$ ...
2
votes
2answers
26 views

Solve easy sums with Binomial Coefficient

How do we get to the following results: $$\sum_{i=0}^n 2^{-i} {n \choose i} = \left(\frac{3}{2}\right)^n$$ and $$\sum_{i=0}^n 2^{-3i} {n \choose i} = \left(\frac{9}{8}\right)^n.$$ I guess I could ...
4
votes
1answer
65 views

Tricky binomial coefficients problem

Let $k$ be a positive integer and let $n = 6k - 1$. Let $$S(n)=\sum_{j=1}^{2k-1} (-1)^{j+1} {{n}\choose{3j-1}}$$ How do you prove that $S(n)$ is never zero?
0
votes
0answers
22 views

Can one interchange the limit and summation in this example?

Let $L$ be a positive real number and $a$, $b$ and $x$ real numbers strictly between $0$ and $L$. For integers $m$ and $n$, define $$ A_{m,n} := \sum_{k=1}^{[\frac{\sqrt{n}(b-a)}{2}]} \frac{1}{2^n} ...
0
votes
2answers
26 views

Clarification of a proof of an identity for binomial coefficients, $\binom{n}{k}= \binom{n-1}{k-1}+\binom{n-1}{k}$

I am studying analysis 1 (first term). So there is this definition in our textbook: for every $n \in \mathbb{N} \ge 1$ and every k $\in \mathbb{Z}$ there is $\binom{n}{k}= ...
0
votes
1answer
25 views

Finding the Binomial Coffecient

Is there a way to find the binomial coefficient of $x^{14}$ in $$(x^0+x^1+x^2+x^3+x^4)^6$$ I tried to use sum of G.P form but it did'nt help.
3
votes
0answers
38 views

Nice formula for $\sum_{m=0}^n{2m\choose m}{2(n-m)\choose n-m}$? [duplicate]

I am trying to find a nice formula for \begin{align}\sum_{m=0}^n{2m\choose m}{2(n-m)\choose n-m}\tag{1}.\end{align} After failing to simplify it, I asked WolframAlpha (see link), and apparently, it ...
1
vote
5answers
122 views

Calculate $\lim_{n\rightarrow +\infty}\binom{2n} n$

Calculate $$\lim_{n\rightarrow +\infty}\binom{2n} n$$ without use Stirling's Formula. Any suggestions please?
0
votes
0answers
44 views

What is known about this Pascal's Triangle problem?

Suppose for the $k$th row of Pascal's Triangle, you want to take each of the integers $1..k$ and multiply it by a different number in the row, then take the sum. For example, for $k=4$, we have ...
0
votes
0answers
23 views

Tricky Negative Binomial example

Let $Y$ count the number of widgets succesfully produced before $r$th failure. We are told that machine shuts down when $30$th failure has occured, that is $r=30$. Then probability of producing $y$ ...