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
1answer
323 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
37 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 ...
1
vote
1answer
57 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
166 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
252 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
51 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
28 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
55 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
35 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
97 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
55 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
39 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
100 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
48 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
37 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
48 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
28 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
37 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
113 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
74 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
61 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
128 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
98 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
40 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 ...
4
votes
3answers
142 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
277 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
56 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
43 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
102 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.
4
votes
1answer
140 views

Calculating a sum which includes binomial coeffeicients

Some formula for calculating the probablity that the difference between the number $6$ and the average of accidentally selected $100$ points among $10000$ points which are distributed in the interval ...
0
votes
1answer
51 views

Binomial coefficient, adding further 'combinations'

As a programmer, discovering the binomial theorem has helped me with alot. I want to solve something using maths as source and I wonder if you can help me define this one: Regarding this question and ...
1
vote
3answers
70 views

How to calculate ratio of two binomial coefficient

I'm working through the book Probability and Statistics by DeGroot, 3rd edition. In section 1.8 #2 It asks which of the following is larger: $\binom{93}{30}$ or $\binom{93}{31}$ In the solutions ...
-1
votes
0answers
74 views

Prove that ${{n}\choose{k}} = {{n - 2}\choose{k}} + 2{{n - 2}\choose{k - 1}} + {{n - 2}\choose{k - 2}}$. [duplicate]

I'm looking for some guidance in solving this. I have read through my text multiple times trying to find something similar to this and I'm coming up with nothing. I'm not really sure where to start on ...
0
votes
2answers
25 views

Clarification on a binomial summation

I need to use the following sum in a homework problem: $\sum\limits_{i=1}^k (-1)^i {n \choose i}, 0\leq k \leq n.$ In the problem it says that the sum is equal to the following: ...
1
vote
1answer
25 views

A question regarding modified binomial summation

We know that $$ \sum_{k=0}^N\binom {N} {k}a^N b^{N-k} = (a+b)^N $$ Do we have a formula for the following formula? $$ \sum_{k=0}^N k\cdot\binom {N} {k}a^{k} b^{N-k} $$ It looks very similar to compute ...
6
votes
2answers
66 views

Find 2 sums with the binomial newton

Find the sum of: i)$\displaystyle\sum_{k=0}^{n} k^2$ $\left(\begin{array}{c} n\\k\end{array}\right)$ ii) $\displaystyle\sum_{k=1}^{n} \frac{2k+5}{k+1}$$\left(\begin{array}{c} ...
2
votes
1answer
67 views

Formula for a variation of Pascal´s Triangle

So recently I came across a math problem, which states the following: You play a game with a fair coin. You start with zero points, and you throw the coin. If you throw heads, you add 1 point to the ...
1
vote
3answers
44 views

Combinations Equation to prove (possibly with Pascal's relation?)

Can this equation be proved? $${n \choose p} = {n-2 \choose p} + 2 {n-2 \choose p-1} + {n-2 \choose p-2}$$ Here is what I've tried: $${ {n!\over (n - p)! p!} = {(n - 2)! \over (n - p -2)! p!} + ...
0
votes
1answer
47 views

Recursive formula for an inverted binomial table

This is an inverted binomial table: $$ \begin{array}{ccccccccccc} &&&&&&1&&&&&&\\ &&&&&1&&1&&&&&\\ ...
1
vote
5answers
135 views

Why can $ \frac {n!}{k!(n-k)!}$ be used as binominal coefficient?

I am having trouble grasping how $ \frac {n!}{k!(n-k)!}$ could possibly equal the binominal coefficient. As far as I can tell, $ \frac {n!}{k!(n-k)!}$ tells us how many combinations that are ...
1
vote
1answer
107 views

Another binomial coefficients sum

Is there a closed form of the sum $$\sum_{k=0}^{n-1} {n-k\choose k}\frac {(-1)^k}{n-k}$$? I cannot even guess what the sum will be. (We assume, here, that $i\choose j$=0 if $i < j$.)
-1
votes
2answers
96 views

General Formula for Number of Terms in an Expansion

Suppose one is looking at the general expansion of $$ (a_1 + a_2 + a_3\,\, +\,\, ...\,\, +\,\, a_k)^n $$ where $a_k > 0 \,\,\,\,\forall k \in \mathbb{Z}$ Is there a formula that will yield the ...
1
vote
2answers
56 views

Finding Summation with Binomial Expansion

Having trouble figuring out this question. Any help would be appreciated! Thanks. $\sum_{k=2}^n k(k-1)\binom{n}{k}$