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
1answer
41 views

Prove that (n + 1) (n choose m) = (n + 1 − m) ((n + 1) choose m) [closed]

Let m and n be integers with $0 ≤ m ≤ n$. There are $n + 1$ students in Carleton’s Computer Science program. The Carleton Computer Science Society has a Board of Directors, consisting of one president ...
4
votes
1answer
62 views

Prove $\sum_{k=0}^n\binom{2n+1}{2k}=4^n$

I once had to show that $\cos(x)\sin(x)=\frac{1}{2}\sin(2x)$ using the Cauchy product and relied on $$\sum_{k=0}^n\binom{2n+1}{2k}=4^n.$$ However I never came up with a proof why this is true - is ...
2
votes
1answer
32 views

show that $\sum\limits_{k=0}^n \binom{n}{k}2^k=\sum\limits_{k=0}^n \binom{n}{k}2^k\cdot 1^{n-k}= 3^n$

Show that $$\sum\limits_{k=0}^n \binom{n}{k}2^k=\sum\limits_{k=0}^n \binom{n}{k}2^k\cdot 1^{n-k}= 3^n$$ I know this true but i really having a hard time arrive there. Is it just that $(2+1)^n = ...
2
votes
2answers
57 views

Binomial coefficients inequation problem

Can anyone help me solve this: $$5\binom{13}{x} < \binom{x + 2}{4}$$ After turning it to factorial I don't know what to do nothing seems to cancel out. $x$ is a positive integer. I end up with this ...
1
vote
3answers
23 views

Calculating limit involving binomial coefficient

$$\lim_{n\rightarrow \infty} \binom{n}{k} h^{(n-k)} , |h| < 1$$ I'm trying to evaluate this limit, but like the $h$ messes me up each time. What I'm doing is trying to prove that the infinite ...
1
vote
1answer
59 views

Binomial transform of Catalan numbers formula

How to prove that OEIS A007317 Binomial transform of Catalan numbers $a_{n}: 1, 2, 5, 15, 51, 188, 731, 2950, 12235, 51822, .. (n = 1, 2, ..)$ has a recurrence formula: $(n+2)a_{n+2} = (6n+4)a_{n+1} - ...
2
votes
5answers
72 views

What is the coefficient of $x^3 y^4$ in the expansion of $ (2x-y+5)^8$

I was thinking of doing $\binom{8}{4}$ but not sure if right.
0
votes
1answer
22 views

Find the coefficient of the given term when (u^2 - v^2 ) ^10 expanded by the binomial theorem?

The term is u^16 v^4 When (u^2 - v^2 ) ^10 is exanded by the binomial theorem. My book uses Combinations, but I'm not sure if it works if u and v are squared?
5
votes
2answers
100 views

How do we prove the following binomial identity?

I tried to prove it by expanding the left hand side, but to no avail. Can you please explain me how to prove this statement? I'm thinking calculus(differentiation) can be used to prove this, as ...
2
votes
1answer
82 views

Help Show Binomial Identity: $\sum_{j=0}^{n} {n \choose j}{m+j \choose n} = \sum_{j=0}^{n} {n \choose j}{m \choose j}2^j$ [duplicate]

I have been trying to solve this problem that I found in my old course notes for some time, but I have not been successful. Can anyone suggest a strategy or provide a hint? ...
-2
votes
3answers
73 views

Trying to prove $\sum\limits_{k=0}^{n}\binom{n}{k}=(1+1)^n$ [duplicate]

I am trying to show in the following equality that the left hand side equals the right hand side. I tried expanding out the summation but that didn't get me anywhere. Could somebody provide a hint? ...
6
votes
1answer
65 views

$\frac{2n\choose n}{n+2}\not\in\mathbb N$ and $n\neq3k+1$ and $n\neq4k+2$

Are there any natural numbers $n\not\equiv1\bmod3$, and $n\not\equiv2\bmod4$, so that $~\dfrac{\displaystyle{2n\choose n}}{n+2}\not\in\mathbb N$ ? Since $C_n=\dfrac{\displaystyle{2n\choose ...
3
votes
2answers
70 views

$\binom nk=\sum_{j=0}^{\lfloor\frac k2\rfloor}(-1)^j\binom nj\binom{n+k-2j-1}{n-1}$

Prove combinatorially (using inclusion-exclusion) that$ \binom nk=\sum_{j=0}^{\lfloor\frac k2\rfloor}(-1)^j\binom nj\binom{n+k-2j-1}{n-1}$ Hi, everyone. I'm at a loss here. I've been trying ...
1
vote
1answer
34 views

Divisibility test using perhaps binomial thorem

I have to determine if $17^{21} + 19^{21}$ is divisible by any of the following numbers (a) 36 (b) 19 (c) 17 (d) 21. I am trying to find using binomial expansion but getting stuck up with one or two ...
0
votes
1answer
144 views

Give a combinatorial proof that $\sum_{k=1}^{n} {{k} {n \choose k}^2 ={ n} {{2n-1} \choose {n-1}}}$ [duplicate]

$$\sum_{k=1}^{n} {{k} {n \choose k}^2 ={ n} {{2n-1} \choose {n-1}}}$$ How would I approach this problem to make a combinatorial proof?
2
votes
2answers
51 views

Prove that using induction that $\binom22+\dots+\binom n2 = \binom{n+1}2$ [duplicate]

so I have this math problem where I have to prove this using induction. ...
3
votes
2answers
55 views

What's the property of this series? Is it special? Coefficients of $\left(x\frac{d}{dx}\right)^n f(x) $

I am think about this expression : $e^{\lambda x \frac{d}{dx}}f(x)$. Let us look at each term in the expansion of the exponential operator $e^{\lambda x \frac{d}{dx}}$, $$\left(x\frac{d}{dx}\right)^n ...
0
votes
1answer
33 views

Number of Lattice paths through some point

I have a problem about lattice paths. Here, I mean we can only use (1,0) or (0,1) as steps. We know the number of lattice paths on an $n\times n$ grid that go through $(i,j)$ is equal to ...
0
votes
1answer
53 views

Fun Proof! Show that there are ${m+n \choose n}$ allowable paths from $(0,0)$ to $(m,n)$ for all $m, n \in Z$

Define an ``allowable path" from a point $(x,y) \in R^2$ to a point $(x',y') \in R^2$ to be a path from $(x,y)$ to $(x',y')$ consisting of a finite sequence of positive, length $1$, horizontal and ...
0
votes
1answer
75 views

Is there a closed formula for $\binom{a}{k}+\binom{b}{k}-\binom{c}{k}$?

For integers $c > b > a > k \ge 1$, consider the binomial sum $$\binom{a}{k}+\binom{b}{k}-\binom{c}{k}. \tag{$\star$}$$ Does ($\star$) have other closed-form representations?
2
votes
2answers
34 views

Proof of Identity Involving Binomial Coefficients

I am new to stack exchange. I can't find a duplicate of this problem (some similar but I am stuck at a specific place!). I need to prove: $\binom{n}{r} = \frac{n-r+1}{r} \binom{n}{r-1}$ I know that ...
3
votes
5answers
73 views

What is the sum of the series with binomial sequences: $\sum_{k=0}^{n} k \binom{n}{k}$? [duplicate]

compute this sum: $\sum_{k=0}^{n} k \binom{n}{k}$ I tried but I got stuck
1
vote
2answers
82 views

Stirling's Approximation for binomial coefficient

In this proof, it is assumed that, for $k << n$, ${n \choose k} \approx \frac{n^k}{k!}$, given Stirling's approximation. How does Stirling's Approximation, in either form $\ln n! \approx ...
2
votes
2answers
48 views

Intuitive explanation of binomial coefficient formula

Regarding the formula for binomial coefficients: $\binom{n}{k}=\frac{n(n-1)(n-2)...(n-k+1)}{k!}$ the professor described the formula as first choosing the k objects from a group of n, where order ...
0
votes
0answers
25 views

Lower bounds/upper bounds for Qbinomials

Is there any lower bound or upper bound known for Q-binomials? I know that number of partitions function p(n)>2^(\sqrt n). But, I don't know any lower bounds for Q-binomials which are the generating ...
0
votes
1answer
53 views

Multiplying series and Binomial coefficient

I shall multiply two series and the result should then be in terms of a binomial coefficient. On the web I found this 'rule': $$ \Bigg(\sum_{k=0}^\infty a_k \frac{t^k}{k!}\Bigg) * ...
0
votes
1answer
32 views

Binomial coefficients products maximum

Is there anyone that can told me the solution to this problem? Given two fixed non negative integers $n_1$ and $n_2$, and a non negative integer $k$, with $0 \le k \le \min(n_1,n_2)$. For what ...
5
votes
1answer
94 views

How did this result come about?

I was reading Chebyshev polynomials Wiki page and I could not understand one thing $$ T_n(x) = x^n \sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \binom{n}{2k} \left (1 - x^{-2} \right )^k ...
1
vote
1answer
46 views

Stirling’s approximation and Big O

How to prove that $2n \choose n$ = $\frac{2^{2n}}{\sqrt{\pi n}}(1 + O(1/n))$ using Stirling’s approximation? I know how to prove that $2n \choose n$ = $\frac{2^{2n}}{\sqrt{\pi n}}$ but I am having ...
2
votes
1answer
37 views

Finding $i$ such that $\sum_{j=0}^i\binom{n}{j}\left(1-\frac1k\right)^j\left(\frac1k\right)^{n-j}\approx\frac1k$

Let $n,k$ be positive integers. From the binomial theorem, we know that ...
-1
votes
3answers
88 views

Stirling approximation of $\binom{2n}{n}$

How do I approximate ${2n \choose n}$ using Stirling's formula (which approximates ${n!}$ with $\pi$ and $e$?
0
votes
1answer
44 views

Is there a known closed form for $\sum_{k=0}^n k\binom{n}{k}^2$? [duplicate]

I know that there are closed forms for $\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$ and a similar one for $\sum_{k=0}^n k \binom{n}{k}$. Is there a known closed form for $\sum_{k=0}^n ...
2
votes
0answers
36 views

how to simplify this binomial expansion

Is there any way to simplify this term: $$\sum_{v=1}^m v(1-\frac{1}{v})^u\binom{m}{v}p^v(1-p)^{m-v}$$ The term $(1-\frac{1}{v})^u$ is really annoying. This expansion appear in a specific version of ...
0
votes
1answer
44 views

Coefficients in binomial expansions of $(x+y)^n$ [duplicate]

Is it true that if we expand $(x+y)^n$ where $n$ is a prime number, then all the coefficients are divisible (except the first and last term) by $n$? Note. There are many examples of when $n$ isn't ...
2
votes
1answer
25 views

Find a lower bound for the size of a binomial coefficient. [duplicate]

I'd like to show that $${n \choose k} \ge \left( \frac{n}{k} \right) ^ k$$ I understand that $\forall \delta \ge 0$, $$\frac{n}{k} \le \frac{n-\delta}{k-\delta}$$ since as $k \le n$, then $k - \delta ...
1
vote
3answers
34 views

Find the radius of convergence of the series $y=\sum_{n=0}^{\infty}\binom{p}{n} x^{n}$

Let $p\in R$ Find the radius of convergence of the series: $$y=\sum_{n=0}^{\infty}\binom{p}{n} x^{n}$$ Show that y satisfies the differential equation $(1+x)y'=py$ and initial condition ...
2
votes
5answers
101 views

Prove $n\binom{p}{n}=p\binom{p-1}{n-1}$

Let $p\in \mathbb{R}$ and $n\in \mathbb{N}$ and $$\binom{p}{n}=\frac{p(p-1)(p-2)...(p-n+1)}{n!}$$ b) Prove $$n\binom{p}{n}=p\binom{p-1}{n-1}$$ Thanks for all the help with a! I definitely understand ...
1
vote
4answers
68 views

How to prove an identity containing binomial coefficients

I am trying to prove the identity $$\sum_{k=1}^n (3^k - 1) \binom{n}{k} = 4^n - 2^n$$ where $\binom{n}{k}$ is the binomial coefficient n over k or n choose k.
1
vote
1answer
49 views

How to rewrite binomial coefficient as polynomial?

I have a binomial coefficient $\binom{n + 2}{3}$ and I need to rewrite it as a polynomial. I understand polynomials use addition, subtraction and multiplication of non-negative integers.
7
votes
1answer
125 views

Solutions for the equation $ \tbinom n3=m^2$

From 'Proofs from the book', it stated that $ \tbinom n3=m^2$ has the unique solution n=50,m=140. But how do we prove this is so? Expansion of the equation above yields $n(n-1)(n-2)=6m^2$ which can ...
4
votes
1answer
92 views

Find all natural solutions for $\binom mn=1984$

Find all positive integers $m$ and $n$ such that $${m \choose n}= 1984$$ My approach: It is easy to define $m=1984$ and $n=1$ or $1983$. But how to show that there are no other solutions or, if ...
1
vote
1answer
38 views

Prove that $\begin{pmatrix} 2n \\ n \end{pmatrix}$ is not divisible by $p$

Let $n$ be an integer greater than $5$. I would like to prove that if $p$ is a prime such that $\displaystyle \frac{2}{3}n < p \leq n$ then $\displaystyle \begin{pmatrix} 2n \\ n \end{pmatrix}$ is ...
0
votes
0answers
67 views

combinatorics problem - bins and stars

assume i have 7 numbered bins, 5 green stars and 14 yellow stars. in how many different ways can i place the stars in the bins? note : 1) The only difference between the balls is the color. 2) The ...
3
votes
2answers
116 views

Coefficient of the generating function $G(z)=\frac{1}{1-z-z^2-z^3-z^4}$

I am seeking the coefficient $a_n$ of the generating function $$G(z)=\sum_{k\geq 0} a_k z^k = \frac{1}{1-z-z^2-z^3-z^4}$$ The combinatorial background of this question is to solve the recurrence ...
4
votes
11answers
215 views

Proving the combinatorial identity ${n \choose k} = {n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k}$

Prove the combinatorial identity $${n \choose k} = {n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k} .$$ I understand the left side, which is obvious, but I'm struggling to get anywhere on ...
0
votes
0answers
48 views

Prime Factors in Pascal's Triangle

The question about reversing n choose k made me look a little further into Pascal's triangle, but my curiosity is not satiated. I am now curious of the following: Given $ n > k > 1 $, show ...
1
vote
1answer
38 views

Need to compute/approximate a summation of the quotients of binomial coefficients

In my research I need to calculate the expected value of a particular distribution. The summation involved is relatively nasty; it's not something I've ever seen before. Assume $m > t$. $$ ...
4
votes
3answers
100 views

What is the sum $\sum_{k=0}^{n}k^2\binom{n}{k}$? [duplicate]

What should be the strategy to find $$\sum_{k=0}^{n}k^2\binom{n}{k}$$ Can this be done by making a series of $x$ and integrating?
4
votes
2answers
90 views

A meaningful sum of multinomials

Consider paths that touch $n$ nodes of a complete graph, and let's number these nodes from $1$ to $n$. The number of paths that pass $m_1$ times through node $1$, $m_2$ times through node $2$, etc., ...
0
votes
0answers
19 views

Finding the values of $a$ and $b$ if $(2x-3)^n=32^a+bx^{a-1}+…$

Find the values of a and b if $(2x-3)^n=32^a+bx^{a-1}+...$ Can anyone help me out with this question? I am supposed to solve this with the Pascal triangle.