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)

1
vote
0answers
22 views

coefficients of polynomial and binomial expressions

Let us say we are given a polynomial p(x)=$\sum_k a_k x^k$. In order to find $\sum_k a_k$ we simply need to evaluate p(1), and similarly there are many other tricks. Is there any trick to evaluate ...
2
votes
2answers
45 views

Find the coefficient of $x^4$ in the expansion of $(1 + 3x + 2x^3)^{12}$?

I have not learnt the multinomial theorem yet, and was trying to approach this using the binomial theorem. I divided the terms as $a$ being $(1+3x)$ and $b$ being $2x^3$. I then used $${12\choose ...
1
vote
2answers
49 views

When is $n\choose k$ a multiple of $n$

While working through a question, the solution states that in the finite field $\mathbb{F}_p$ for $p$ prime, we have $(u+v)^p=u^p + v^p$ and since $(u+v)^p={p\choose 0}u^pv^0+{p\choose ...
0
votes
0answers
25 views

Final step of a random walk proof

I am working through the last bit of a random walk proof to show that a 3-d random walk is transient. The result I am looking for states that: $\frac {1}{2}^{2s} {{2s}\choose{s}} \sum_{j+k\leq{n}} ...
2
votes
3answers
48 views

Inequality of factorial - Binomial coefficient

my name is Rafał and I decided to create this thread because of my inability to find a solution. I have been fighting with this inequality for 1.5 week and I have a hope that you will give me any hint ...
0
votes
0answers
28 views

Is the given binomial sum almost everywhere negative as $K\to\infty$?

The binomial sum is as follows: $$\mathcal {L}^K(\theta)= \sum_{i=\lceil{K/2}\rceil}^K \binom{K}{i}\theta^i\left((1-\theta)^{K-i}-\frac{1}{2}(1-\theta)^{-K}(1-2\theta)^{K-i}\right)$$ It can be found ...
2
votes
5answers
88 views

How to sum $\sum_{k=1}^n (k+1)(k)(k-1)$

Is there an intelligent way to do this sum without using sums of cubes and sums of squares? $$\sum_{k=1}^n (k+1)(k)(k-1)$$
0
votes
1answer
31 views

Tree addtion has to do with Pascal's Triangle, why?

Let me define tree addition of a list of numbers as follows: 4 3 2 1 7 5 3 12 8 20 I conjecture that it is true that the tree addition of n numbers ...
0
votes
1answer
59 views

Proving $\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$

Prove the identity: $\displaystyle\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$ It looks a bit similar to the "no gets their own hat back" problem or inclusion exclusion ...
5
votes
0answers
58 views

Combinatorial Interpretation of these two identities

Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently: \begin{equation} ...
1
vote
1answer
40 views

Relationship between Factorial and Binomial coefficients

Over at this link, there is a claim that $(2n)! = n!n! {{2n} \choose {n}}$ - see Tom Boardman's answer, the second one down. I'm wondering why this is the case and if anyone can provide a proof. Is ...
1
vote
1answer
27 views

Why can I not include unused cards into a second binomial coefficient?

In trying to count the number of 13-card hands where there is at least one ace and no J, Q, K, we can see one way is $$ \sum_{k=1}^4 \binom{4}{k}\binom{36}{13-k} = 9722433280. $$ However, I cannot ...
1
vote
2answers
51 views

What will be the sum of the series of binomial co-efficients?

What will be the sum of the following binomial co-efficent series $$\binom{z+1}{z} + \binom{z+2}{z} + \binom{z+3}{z} + \dots + \binom{z+r}{z} = \sum\limits_{i=1}^r \binom{z+i}{z}$$ Thank you
1
vote
3answers
39 views

Finding the formula for summation of the series

I was just solving a competitive programming question, wherein I found out that a formula can be used for solving it efficiently. Problem statement: http://www.spoj.com/problems/TOHU/ I tried a lot to ...
0
votes
2answers
45 views

Solving inequality equation involving sum of binomial coefficients

I have a function $f(k,\,i)$ involving binomial coefficients: $$f(k,\,i)\,=\left(\begin{matrix}k+i \\ k\end{matrix}\right)=\frac{(k+i)!}{k!\,i!}$$ And the following sum over this function (expansion ...
0
votes
1answer
17 views

Formula for combinatorial series sum [duplicate]

As a part of one computer algorithm, I want to find sum for $$n+ \frac{n(n+1)}{2!} + \frac{n(n+1)(n+2)}{3!}+....+ \frac{n(n+1)(n+2)...(n+r-1)}{r!} $$. I looked at $$\frac1{(1-x)^n}$$. But it is ...
0
votes
1answer
55 views

Where does this equation come from: $ (1+mx)^n = 1 + \sum_{n=1}^{\infty} {\binom{2n}{n} \over 4^n } x^n $

I have found the following problem here: https://brilliant.org/problems/intriguing-sum/?group=Km7yEIDGtHDa&ref_id=709399 In the solution a solver directly started with the equation given in the ...
3
votes
2answers
61 views

A reference for a combinatorial identity

I have come across this identity from study of species. I am not posting my method but I am interested in knowing whether it arises in some other contexts as well. The identity is: $$\sum ...
0
votes
1answer
31 views

Does this sum of products of binomial coefficients have a simple closed form?

Let $c,m,k$ be positive integers. Is there a simple closed form for the following sum? $$ \sum_{i=1}^{c-1} (-1)^i {c \choose i} {im \choose k} $$ Mathematica finds nothing, and Maxima's implementation ...
0
votes
1answer
76 views

Where is my formula false??

I wrote a formula that returned how many numbers in a given row of pascals triangle are divisible by a given prime. This formula was created to answer https://projecteuler.net/problem=148. I was ...
4
votes
3answers
132 views

Find the limit of $4^n\cdot\binom{2n}{n}/\binom{4n}{2n}$

I am trying to prove that $$f(n)=4^n\frac{\dbinom{2n}{n}}{\dbinom{4n}{2n}}$$ converges as $n\rightarrow\infty$. I have already tried to use the fact that, if $n, k \in\mathbb{N}, n\geq k\geq1,$ then ...
1
vote
1answer
17 views

Growth of modified binomial recurrence

The binomial coefficients $\binom{n}{r}$ satisfies $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$. This means it is a solution of the equation $f(n,r)=f(n-1,r)+f(n-1,r-1)$, with initial conditions ...
0
votes
1answer
18 views

Growth of binomial recurrence with different initial conditions

The binomial coefficients $\binom{n}{r}$ satisfies $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$. This means it is a solution of the equation $f(n,r)=f(n-1,r)+f(n-1,r-1)$, with initial conditions ...
2
votes
2answers
28 views

How can I prove this property of binomial coefficients?

I was playing around with binomial coefficients and binomial expansions and I came across an interesting identity: $$ \sum_{k=0}^n\frac{1}{k+1}{n \choose k}x^k=\frac{(x+1)^{n+1}-1}{(n+1)x}$$ I have ...
1
vote
1answer
62 views

Binomial Series. Product series of coefficients

How to solve this question? Please provide hints only.
0
votes
1answer
61 views

Sum of binomial coefficients $\sum_{k=n}^{r}\binom{k}{n}$

Is is possible to find the sum of a binomial coefficient series like: $\sum_{k=n}^{r}\dbinom{k}{n}$? Just a random thought.
0
votes
1answer
13 views

bounds on binomial coefficients

Do the standard upper bounds on the binomial coefficient $\binom{n}{k}$ still work well if $k=f(n)$ (by standard i mean for example $(\frac{en}{k})^{k}$ and $\frac{n^{k}}{k!}$)? In particular if ...
2
votes
2answers
26 views

Which rule is applied to define the operator precedence for factorial

Please apologize the question, I struggled with finding a good formulation in the first place: Looking at $\binom{2n}{k}$ it is very clear that for n,k integer and n>k we can solve it by calculating: ...
3
votes
2answers
57 views

Finding a combinatorial argument for an interesting identity.

Consider the following identity $${{n}\choose{0} }{m\choose n} + {n\choose 1}{{m+1} \choose n}+ \cdots {n\choose n}{{m+n} \choose n} =\sum_{i=0}^{\min (m ,n)} {n\choose i}{m\choose i}2^i$$ The ...
1
vote
1answer
98 views

How to calculate sum of combinations with different n and k

Input: $[X,Y]$ and $L$ Output : no of increasing sequence of length L and all elements should be $X\le i \le Y$ e.g: for $[6,7]$ and $2$ sequences are $6,66,67,7,77.$ For the above question my ...
2
votes
1answer
42 views

Showing that this sum is equal to the fibonacci numbers

How do I show that the following sum is equal to the fibonacci numbers? Atleast numerical evaluation suggests it is $$ \sum_{k=0}^{\lceil n/2\rceil}\binom{n+1-k}{n+1-2k} $$ The image below shows how ...
0
votes
1answer
32 views

Calculate $\binom{n}{k}\pmod{10^6+3}$

I want to calculate the value of the following: $$\binom{n}{k}\pmod{10^6+3}$$ $10^6+3$ is prime if it may help. What is the math behind this? I can only understand basic modular arithmetic.
1
vote
1answer
35 views

combinatorial of $\binom{10^9} {r}$ while $1 \leq r \leq10^9 \pmod {10^6+3}$

How to calculate $ \binom{n}{r} \mod m$ when $1\leq n,\: r\leq 10^9$ and $m=10^6+3$. I have tried by making Sieve of factorial and multiplicative inverse $10^6+3 \mod m$. is there any solution in ...
1
vote
0answers
22 views

how to represent a binomial coefficient in terms of a series?

I have to find the power series for (n+m C m) or (n+m C m ) - 1 i.e representing it in some sort of power . Is it even possible ? P.S. :- Thanks in advance .
2
votes
3answers
74 views

Compact form of sum $\sum\limits_{k=0}^m (-1)^k \binom{n}{k} \binom{n}{m-k}$

How to find compact form of the sum $$\sum\limits_{k=0}^m (-1)^k \binom{n}{k} \binom{n}{m-k}$$ It looks like it's connected with Vandermonde's identity but I couldn't get to the solution.
-3
votes
2answers
39 views

Summation Of Series of $\binom{x+k}{k+1}$ where $k$ is $0$ to $n$ [duplicate]

Want The formula or to find The Sum of Series where $$S=\sum_{k=0}^n \binom{x+k}{k+1}$$ where $x$ is any constant $\geq 1$ and $n$ is another constant.
2
votes
2answers
116 views

How to calculate $\sum_{m=1}^{N}\binom{m+k-1}{m}$. [closed]

What would be a simplified formula for $\displaystyle \sum_{m=1}^{N}\binom{m+k-1}{m}$ for a given number $k$ and any number $N$?
0
votes
1answer
74 views

Summation of binomial coefficients [duplicate]

Is there a closed formula for: $\sum_{i=1}^{N}{\binom{i+k}{i}}$ ( k is a constant whole number )
1
vote
1answer
26 views

$\sum^n_{r=0} (-1)^r C_r(1/2^{r}+3^r/2^{2r}+7^r/2^{3r}+\cdots\infty)$

$$\sum^n_{r=0} (-1)^r C_r(1/2^{r}+3^r/2^{2r}+7^r/2^{3r}+\cdots\infty)$$ is equal to? How to approach this problem?Hints please!!! BTW $C(r)$ stands for $(n)C(r)$
0
votes
2answers
25 views

What will be the value of $C_1/C_0+2C_2/C_1+3C_3/C_2+…+15C_{15}/C_{14}$ is [closed]

What will be the value of $C_1/C_0+2C_2/C_1+3C_3/C_2+...+15C_{15}/C_{14}$ ? $C(r)$ stands for $(15)C(r)$ How to approach this problem?Hints please!!!
0
votes
2answers
64 views

Bonferroni Inequalities

Let $k$ and $m$ be positive integers with $k>m$. Then the partial sums of $$ 1-\binom{k}{1} + \binom{k}{2} - \cdots (-1)^m\binom{k}{m} $$ has alternating signs. (The partial sums of the ...
4
votes
1answer
112 views

Complex Analysis proof of multinomial expression

I've recently come across the following identity $$ \displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n} $$ A nice complex analysis proof (by Felix Marin, here) follows as: ...
5
votes
2answers
104 views

Which term of the binomial expansion of $\left(1+\sqrt{2}\right)^{50}$ is the greatest?

Which term of the binomial expansion of $\left(1+\sqrt{2}\right)^{50}$ is the greatest? How can I find it, without comparing all 51 values? Is there a quicker way to do it? (The solution says ...
2
votes
2answers
46 views

Prove that $\frac{1}{(1-x)^k}$ is a generating function for $\binom{n-k-1}{k-1}$

On my discrete math lecture there was a fact that: $\frac{1}{(1-x)^k}$ is a generating function for $a_n=\binom{n-k-1}{k-1}$ I'm interested in combinatorial proof of this fact. Is there any simple ...
1
vote
1answer
39 views

binomial identity with negatives

Prove that $$\sum_{k=0}^n(-1)^k\binom{n+1}{k+1}(k+1)^n=0\;.$$ I tried finding a combinatorial interpretation but to no avail. Here is a combinatorial statement, however crappy. Suppose we have $n$ ...
9
votes
1answer
163 views

Interpretation of a combinatorial identity

I am trying to find an combinatorial interpretation for the following combinatorial identity involving iterated binomial coefficients, which appeared in the November 1980 edition of The American Math ...
0
votes
3answers
39 views

Does $^nC_{n+1}$ exist? [duplicate]

is there any value assigned to $^nC_{n+1}$? My teacher wrote it equal to $0$, but what will negative factorial mean? $$^nC_{n+1} = \frac{n!}{(n+1)!\cdot(n-n-1)!} = \frac{n!}{(n+1)!\cdot(-1)!}$$ ...
2
votes
0answers
51 views

Birthday problem, I'm confused by this formula

I've given the following statement (n is given, and equals 100) : Now, I'm quite confused by the second binomial coefficient: how can that represent the days for the birthdays of the remaining 98 ...
2
votes
4answers
66 views

Evaluate $\int_{0}^{1}(1-x)^ndx$ by expanding the bracket.

I'd like to get a hint on this exercise. I believe I'm somewhat close to the answer. I used the binomial theorem to get: $\displaystyle\int_{0}^{1}(1-x)^ndx = \int_{0}^{1}\sum_{k=0}^{n}{n\choose ...
1
vote
1answer
29 views

Show that $r_k^n/n \le \binom{kn}{n} < r_k^n$ where $r_k = \dfrac{k^k}{(k-1)^{k-1}}$

Show that for $n \ge 2$, $\dfrac{r_k^n}{n+1} \le \binom{kn}{n} < r_k^n$ where $r_k = \frac{k^k}{(k-1)^{k-1}}$. This is a generalization of How to prove through induction which asks for a proof ...