Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [binomial-coefficients]

Coefficients involved in the Binomial Theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

2
votes
0answers
20 views

Explanation of the Wolstenholme theorem proof

I recently came accross the Wolstenholme theorem which says that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod {p^{3}}$$ On wikipedia, it gives a combinatorial proof of this theorem that involves ...
1
vote
4answers
53 views

Prove the identity $\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} = 3^n$

Prove the identity $\sum_{k=0}^{n}\sum_{r=0}^{k} \binom{k}{r} \binom{n}{k} = 3^n$. I believe I need to use the binomial theorem here, but I don't know how to deal with the double summations.
1
vote
4answers
65 views

What is the coefficient of $x^{11}$ in $(3x-9)^{19}$?

I am currently studying for finals, and I do not know how to do this problem from my study guide. I have tried to watch a few YouTube videos and I know that I will end up with $3x^{11} \times (-9)^8$, ...
1
vote
2answers
36 views

sum of $\sum^{n}_{k=0}(-1)^k\cdot \frac{\binom{n}{k}}{\binom{k+3}{k}}$

Finding sum of $\displaystyle \sum^{n}_{k=0}(-1)^k\cdot \frac{\binom{n}{k}}{\binom{k+3}{k}}$ Try: Using $$\int^{1}_{0}x^m\cdot (1-x)^ndx = \frac{m!\cdot n!}{(m+n+1)!}=\frac{1}{(m+n+1)\binom{m+n}{n}}...
-1
votes
1answer
15 views

Let n belongs to +ve integer and $(1+x+x^2)^n=\sum_{r=0}^{2n} {a_rx^r}$ prove that: $a_r=a_{0<r<2n}$

Let n belongs to +ve integer and $$(1+x+x^2)^n=\sum_{r=0}^{2n} {a_rx^r}$$ prove that: $$a_r=a_{2n-1},{0<r<2n}$$ as well as prove that $$\sum_{r=0}^{ n-1} a_r=\frac{1}{2}(3^n-a_n)$$. I tried to ...
4
votes
0answers
35 views

Root of a plynomial in (0,1)

Define $$f_K(x)=\sum_{i=K+1}^{2K} \binom{2K}{i}x^{i-1}(1-x)^{2K-i}.$$ How to show that $qf_K(x)-f_K(1-x)$ has exactly one real root in $(0,1)$ for any $q > 0$ and $K \geq 1$. The proof for $q=1$ ...
21
votes
2answers
2k views

A simple finite combinatorial sum I found, that seems to work, would have good reasons to work, but I can't find in the literature.

I was doing a consistency check for some calculations I'm performing for my master thesis (roughly - about a problem in discrete bayesian model selection) - and it turns out that my choice of priors ...
1
vote
3answers
56 views

value of $k$ in binomial expression

If $\displaystyle \binom{404}{4}-\binom{4}{1}\cdot \binom{303}{4}+\binom{4}{2}\cdot \binom{202}{4}-\binom{4}{3}\cdot \binom{101}{4}=(101)^k.$ Then $k$ is Iam trying to simplify it $\displaystyle \...
0
votes
0answers
19 views

Proof Ideas - Strong Induction, Pascal's Triangle and Fibonacci Numbers

I'm looking for attributes/characteristics/properties to prove about Pascal's Triangle or the Fibonacci numbers. Preferably something that requires a strong induction proof that is on the same level ...
2
votes
4answers
47 views

Prove that $(1-x)^n \leq 1 -xn+\frac{n(n-1)}{2}x^2$ when $0\leq x\leq 1$ and $n\geq2$

Reading a book I saw this inequality $$ (1-x)^n \leq 1 -xn+\frac{n(n-1)}{2}x^2 $$ when $0\leq x\leq 1$ and following the author it descended from the inclusion-exclusion principle. I don't understand ...
0
votes
2answers
38 views

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

I would like if possible to have a proof of yet another theorem of Binomial Coefficients. This time it is $$\sum_{k=0}^n{(-1)^k\over k+1}\binom{n}{k}={1\over n+1}$$ This arises in a proof of the ...
1
vote
0answers
60 views

Proof of a Binomial expression summation

Let $x,y$ be probabilities and $n$ is some integer. Show that: $\displaystyle \sum_{n_0=1}^n \sum_{m=0}^{min(n_0-1,n-n_0-1)} \binom{n_0-1}{m}\binom{n-n_0-1}{m}x^m(1-x)^{n_0-m-1}y^m(1-y)^{n-n_0-m-1} ...
3
votes
2answers
76 views

identities and binomial coefficients

I'm having some problems proving this identity. I tried using some formulas I found on the internet so I can turn that $2$ base number into something else but i'm not really sure how to do that. I ...
1
vote
2answers
36 views

Proof of Identity to Zero of the Sum of a Product of Binomial Coefficients & Pochhammer Numbers

It's well-know that the sum across an entire row of binomial coefficients (of degree, say, $n$) with alternating signs attached is 0; and it can easily be proven by demonstrating that it is the ...
-2
votes
2answers
36 views

A proving question based on binomial theorem [closed]

$$C_0-C1(a-1)(b-1)(c-1)_+C_2(a-2)(b-2)(c-2)+.... (-1)^nC_n(a-n)(b-n)(c-n) $$=0 I tried to solve this problem by using multinomial theorem but was not able to proceed further please help me out.
0
votes
5answers
79 views

Prove that if $\binom{n}{k}$ = $\binom{n}{k+1}$, then $n$ must be odd [closed]

Prove that if $\displaystyle\binom{n}{k}$ = $\displaystyle\binom{n}{k+1}$, then $n$ must be odd. I am having problems with manipulating factorials and just can't seem to get the grasp on how to ...
-1
votes
0answers
14 views

A proving question based on binomial theorem and complex numbers [closed]

Prove that: $$C_1+C_4+C_7+...=\frac{1}{3}(2^n-\cos\frac{n\pi}{3}+\sin\frac{n\pi}{3})$$ I try to solve this problem by taking a general equation $(1+x)^n$ and putting the value of $x$ as $w$ and using ...
-2
votes
0answers
26 views

Is $\sum_{r=1}^n (-1)^{n-r}\binom{n}{r}r^n$ equivalent to the factorial function, for whole numbers? [duplicate]

$$\sum_{r=1}^n (-1)^{n-r}\binom{n}{r}r^n$$ Can someone help prove or disprove whether the above series sum is equivalent to the factorial function, for whole numbers? original formula image
-1
votes
1answer
47 views

Question based on binomial theorem and complex numbers. [closed]

Prove that $$C_1+C_5+ C_9+... =\frac{1}{2}\bigg(2^{n-1}+2^{n/2}\sin\frac{n\pi}{4}\bigg)$$ Here $C_i$ denotes the binomial coefficient $\binom ni$. I tried to solve this problem by using de Moivre's ...
2
votes
3answers
68 views

Derive $\sum_{s=r}^{\infty} \binom{m}{s} \binom{s}{r}(-1)^s=0 $ using an identity $(1 + x)^ m (1 + x)^{ -(r+1)} = (1 + x)^{ m-r-1}$

To prove: $$\sum_{s=r}^{\infty}\binom{m}{s} \binom{s}{r}(-1)^s=0 $$ Use the identity: $$(1 + x)^ m (1 + x)^{ -(r+1)} = (1 + x)^{ m-r-1}$$ I have trouble understanding the hint, could somebody ...
0
votes
1answer
19 views

Proof number-partitions $P_n = \sum_{k=1}^{n} P_{n,k}$ in positive summands

Let $n \in \mathbb{N}$. Let $P_n$ be the number of number-partitions of $n$ in positive summands, i.e. $$P_n = \sum_{k=1}^{n} P_{n,k}$$ How can one prove the following? The amount of number-...
0
votes
2answers
54 views

One term of (2π+5)^n = 288000π^8, what's n?

Without using calculator what's the value of n? Using binomial expansion I get: nCp * 2n-p * πn-p * 5p = 288000π8 Easily I know that n-p=8, by the π's power Then the power of 2 is also 8, so I can ...
0
votes
2answers
43 views

Counting paths through a checkers board (only moving diagonally)

a) Imagine that a checker is placed in the bottom right corner of a 6 by 6 checker board. The piece mmay be moved one square at a time diagonally left or right to the next row up. Calculate the number ...
1
vote
2answers
62 views

Weighted sum of product of binomial coefficients

I am trying to evaluate the sum $\displaystyle \sum_{n=1}^N \sum_{k=1}^n k\binom{n}{k} \binom{N-n}{k}x^k$, Here $x$ is some positive real My approach so far has been to first to compute the ...
0
votes
1answer
48 views

Show there are $2^n$ forms a $n \times n$ matrix can take, preferably via Pascal's triangle

Where "a form" for some RRE matrix is its description in terms of the number of all-zero rows it has and the position of pivots in the non-zero rows. I've tried using induction, the base case is ...
7
votes
2answers
102 views

Is there a closed form for the sum of the cubes of the binomial coefficients?

We know that $$ \sum_{k=0}^n \binom{n}{k} = 2^n\;\; \text{ and }\;\; \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n} $$ hold for all $n\in \mathbb{N}_0$. Now I tried to find a similar expression for $$ \...
0
votes
2answers
34 views

Is it possible to show

As part of a larger proof I need the following to be true in order to make it work, $(a+1){b\choose a+1}x^{a+1}(1-x)^{b-a-1}=a{b\choose a}x^a(1-x)^{b-a}$ Can anyone give me a hand?
3
votes
4answers
52 views

Factorial Proof - ${n \choose r-1}+{n \choose r}={n+1 \choose r}$

${n \choose r-1}+{n \choose r}={n+1 \choose r}$ So what I tried to do was expand the first and second term. $\frac{n!}{(r-1)!(n+1-r)!}+\frac{n!}{(r)!(n-r)!}$ Then what I did was try to get common ...
-1
votes
1answer
71 views

Given that the coefficients of the $6^{th}$ term and $16^{th}$ term in the Expansion of $(x + y) ^n$ are equal. Find the value of $n$. [closed]

The Expansion gives me: $6^{th}$ term = $\displaystyle\binom{n}{5} x^{n-5}y^5$ and $16^{th}$ term = $\displaystyle\binom{n}{15} x^{n-15}y^{15}$. What do I do next?
2
votes
5answers
63 views

How to show that $2^n > n$ without induction

I'm solving exercises about Pascal's triangle and Binomial theorem, and this problem showed up, however I don't have any clue on how to solve it The sum of ${n\choose p}$ from $p=0$ to $n$ is the ...
5
votes
2answers
73 views

Showing $\sum\limits_{j=0}^M \frac{M \choose j}{N+M \choose j} = \frac{N+M+1}{N+1}$

In an answer to another question, I stated $$\sum\limits_{j=0}^M \frac{M \choose j}{N+M \choose j} = \frac{N+M+1}{N+1}.$$ It is clearly true when $N=0$ since you add up $M+1$ copies of $1$, and when $...
1
vote
2answers
76 views

Does there exist a similar identity to $\binom{n}{k} = \binom{n}{n-k}$?

I know that $$\binom{n}{k} = \binom{n}{n-k}$$ My question is does there exist a similar identity where you change the top of the choose function, o any similar to the identity above? An example: Can ...
1
vote
1answer
58 views

General method to find sum of binomial

Specifically I want to ask the method to solve $$\sum_{k=0}^n \binom{4n+b}{4k};\ b=[0,1,2,3]$$ And how to solve series of type $$\sum_{k=0}^n \binom{an+b}{ak};\ a=[1,2,3,...],\ b=[0,1,2,...,a-1]$$
0
votes
2answers
42 views

Find $\sum_{n=0}^\infty \frac{\sum_{r=0}^n \frac{n!}{(n-r)!\ r!}}{n!}$.

Find the value of $$\sum_{n=0}^\infty \frac{\sum_{r=0}^n \frac{n!}{(n-r)!\ r!}}{n!}.$$ I don't understand how to apply summation to the term that's obtained after simplifying by dividing with $n$ ...
0
votes
1answer
30 views

Serge Lang - Basic Mathematics - Sum of Binomial coefficients p.387 ex. 9

I can not understand the solution.How does the second step come about? How does the expression in brackets appear? solution image
0
votes
1answer
27 views

How does it follow from the Pascal's Triangle that binomial coefficient are integers

So I was reading this lemma which states: Let $m,n$ be natural numbers such that $1 \leq m \leq n$. Then \begin{equation*} {n\choose m-1} + {n\choose m} = {n+1\choose m}. \end{equation*} It follows ...
0
votes
1answer
35 views

Binomial coefficient from a double sequence $\{a_{n,k}\}$ of Pascal Triangle

I really need help with the 13-th prob. Chap. 2 in the book Kuratowski "Introduction to Calculus", it says: We consider the following table (i.e. double sequence $\{a_{n,k}\}$): \begin{array}{cccccc}...
2
votes
6answers
74 views

${x\choose 2}+{n-x\choose 2} \leq {n-1\choose 2}$

In a proof, the author states that it is clear that: Given $x\geq 1$ and $ n-x \geq 1$ and finally also $n\geq 2$ $${x\choose 2}+{n-x\choose 2} \leq {n-1\choose 2}$$ This is not immediately clear ...
4
votes
5answers
1k views

Binomial Theorem with Three Terms

$(x^2 + 2 + \frac{1}{x} )^7$ Find the coefficient of $x^8$ Ive tried to combine the $x$ terms and then use the general term of the binomial theorem twice but this does seem to be working. Does ...
1
vote
3answers
38 views

Probability that Santa will give $N$ different presents to exactly $N-1$ kids

Santa is randomly giving $N$ different presents to $N$ different kids. what is the probability that Samuel doesn't get a present? what is the probability that every kid got a present? what is the ...
2
votes
1answer
71 views

A mod 2 binomial identity

I would like to show the following identity: for all $n, q \geq 0$, $$\sum_k \binom{2k}{4k-2n} \binom{n+3q}{2k+2q+1} \equiv \binom{n+3q}{2q-1} \pmod{2}.$$ This has been computer-tested for all $n, ...
0
votes
1answer
32 views

Calculating $\sum_{k=0}^{\lfloor \frac{p}{2} \rfloor} \binom{p}{k}$

I'm trying to find the value of: $$\sum_{k=0}^{\left \lfloor \frac{p}{2} \right \rfloor} \binom{p}{k}$$ For even and odd $p$, the indication I was given suggests writing it as $$\frac{1}{2}\left (\...
1
vote
3answers
49 views

Calculate $\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k}$

Calculate $\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\frac{1}{k}$, I do not know hot get rid of that $k$, for me it is similar like $\binom{n}{k}=\frac{k}{n} \binom{n-1}{k-1}$, do you have some idea?
1
vote
4answers
39 views

Prove that $\binom{n}{1}^2+2\binom{n}{2}^2+\cdots +n\binom{n}{n}^2=n\binom{2n-1}{n-1}$

Prove that $$ \binom{n}{1}^2+2\binom{n}{2}^2+\cdots + n\binom{n}{n}^2 = n \binom{2n-1}{n-1}. $$ So $$ \sum_{k=1}^n k \binom{n}{k}^2 = \sum_{k=1}^n k \binom{n}{k}\binom{n}{k} = \sum_{k=1}^n n \binom{...
1
vote
1answer
20 views

Limiting sum of binomial coefficients multiplied by powers

I want to prove that: $$\lim_{n \rightarrow \infty} \sum_{k=1}^m {m \choose k} \Big( \frac{k}{m} \Big)^n = 1.$$ My progress so far: Define the function $F(x) \equiv (1+x)^m$ and the operator $\tilde{...
1
vote
0answers
39 views

Series involving squares of binomial coefficients

Does anyone know if this sum has a closed form formula ? $$\sum_{0 \leq k \leq n} \binom{n}{k}^2 x^k\\ n\in N$$
1
vote
1answer
35 views

Explanation for binomial sums $\sum_{n=0}^{\infty} \binom{-4}{n-1} (-1)^{n-1} x^n = \sum_{n=0}^{\infty} \binom{-4}{n} (-1) x^{n+1}$

I was looking at some negative binomial coefficient problems and I stumbled upon this explanation $$\sum_{n=0}^{\infty} \binom{n+2}{3} x^n = \sum_{n=0}^{\infty} \binom{n+2}{n-1} x^n= \sum_{n=0}^{\...
1
vote
1answer
34 views

Sum involving squares of binomial coefficients

Find the sum of $\sum_{r=1}^{n}r(^nC_r)^2$. I am attempting it as follows $(1+x)^n=C_0+xC_1+x^2C_2+x^3C_3+⋯+x^nC_n$. On differentiating we get following relation $n(1+x)^{n−1}=\sum_{r=1}^n rx^{r−1}...
3
votes
1answer
101 views

How to expand product of $n$ factors.

I have a product say \begin{equation} F(a,n,x) = \prod _{j=0}^{n}(1-{a}^{n-2\,j}x) \end{equation} I want to expand and hope to have general terms of the coefficients. I did for $n= 2,3,4,5,6,7,8...$ ...
0
votes
2answers
35 views

Solving for $n$

$$\binom{n}{0}+\binom{n}{1}+\binom{n}{2} = 22$$ I'm trying to solve this equation for $n$. If $$\binom{n}{0} = 1$$ Then we have that $$1+\binom{n}{1}+\binom{n}{2} = 22 \implies \binom{n}{1}+\...