# Questions tagged [binomial-coefficients]

For questions involving the coefficients involved in the binomial theorem. $\binom{n}{k}$ counts the subsets of size $k$ of a set of size $n$.

7,243 questions
Filter by
Sorted by
Tagged with
42 views

### On a quick proof to the following congruence relation

Let $n$ be a positive integer and $p$ be a prime number. Let $v_p(n)$ represent the exponent of the highest power of $p$ that divides $n$. I wonder if there is a simple way to prove the congruence ...
• 39
57 views

### Convergence of a weighted alternating binomial series

Consider the alternating series $$S_n = \sum_{k=0}^{n} (-1)^k {n\choose k} a_k$$ where the weights $a_k$ are non-negative, bounded and monotonically decreasing ($a_{k+1} < a_k$). Can it be shown ...
• 123
93 views

### Conjecture: Shallow diagonals in Pascal's triangle form polynomials whose roots are all real, distinct, and in $(-2,2)$.

Here are the first few "shallow diagonals" in Pascal's triangle. We can use these shallow diagonals to make polynomials. Note that the even degree polynomials have an extra $\pm x$ at the ...
• 8,418
80 views

### Is there a $q$-analog for the product of binomial coefficients?

The $q$-analog of the binomial coefficient $\binom{n}{k}$ may be defined as the coefficient of $x^k$ in $\prod_{i=0}^{n-1}(1+q^ix)$. Classical arithmetic identities tend to have $q$-analogs. I am ...
• 1,594
1 vote
63 views

### Explanation of $\sum_{k}[x^k]f(x)g(y)^k=f(g(y))$

In the book "Mathematics for the Analysis of Algorithms" by Daniel H. Greene and Donald E. Knuth, they cover the example, $$S=\sum_{k}\binom{m}{k}\left(-\frac{1}{2}\right)^k\binom{2k}{k}$$ ...
• 151
1 vote
73 views

### How to prove that $\sum_{k=0}^n (-1)^k k^p \binom{n}{k}$ is non-zero for p>1

Let $p\in \mathbb{N}_0$ and consider $\sum_{k=0}^n (-1)^k k^p \binom{n}{k}$. For $p=0$, this clearly vanishes as the sum then equals $(1-1)^n$. For $p=1$ and $n$ even, this sum also vanishes as one ...
50 views

### The limit of a Nasty Summation

I'm trying to evaluate the limit as h approachs 0 of the sum from k = 0 to n of: $\frac{1}{h^n}(-1)^{k+n}\binom{n}{k}\frac{1}{(x+kh)^2-2(x+kh)+17}$ If it helps, it's the limit definition of the nth ...
• 65
201 views

### Series of polynomials very nearly follows binomial coefficients but doesn't quite

I'm modelling a system using a Markov chain and by a few iterations of the transition matrix I can see a pattern emerging in the resulting polynomial that really looks like Pascal's triangle, but isn'...
61 views

### Sum of squares of combinations having value of n different from index of sum

Two sums are - $$\sum_{r=0}^n [{2n+1 \choose 2r}] ^2$$ $$\sum_{r=0}^n [{2n+1 \choose 2r+1}] ^2$$ The question basically asks to simplify these sums such that the final expression is only in terms ...
121 views

### Collatz Conjecture 1-cycles and Pascal's triangle.

Question: Is there a pattern in Pascal's triangle that precludes the existence of non-trivial 1-cycles in the Collatz conjecture? Efforts to Answer the Question: I did a search engine query for "...
• 343
114 views

### Binomial Coefficient through multiplication only

Is there any method to obtain $n \choose k$, for all $n, k \in \mathbb{N}$, using only products of natural numbers without using recursion on binomial coeffcients? A method that allows one to compute ...
• 39
168 views

### Partial sum of alternating series involving binomials

I ran across an interesting expression that I cannot prove (but tested numerically): $$1 = \sum_{j=0}^{n} (-1)^j \binom{n+i}{n-j-1} \binom{n+j}{n-i-1} \binom{i+j}{i}$$ for any $0 \leq i < n$. In ...
• 181
51 views

### How to get this lower bound for $C(m^2,m-1)$?

While applying Nechiporuk’s Theorem to get a lower bound on the formula size of Element distinction function, the following inequality is used: (ref here) $C(m^2,m-1) \geq (m^2-m+1)^{m-1}$. Is there a ...
• 214
74 views

### Combinatorially proving $F_{n} = \sum_{i=0}^{\left\lfloor n/2 \right\rfloor}\binom{n-i}{i}$, where $F_n$ is the $n$-th Fibonacci number [duplicate]

Prove the following combinatorially: $$F_{n} = \sum_{i=0}^{\left\lfloor n/2 \right\rfloor}\binom{n-i}{i}$$ So, I know that the Fibonacci number counts the number of ways to cover a $1 \times n$ ...
• 55
1 vote
70 views

1 vote
55 views

### Summation of series involving binomial coefficients : $\sum_{r=1}^n {n\choose r}r^{n-r}$.

I was trying to find the sum of the following series: $\sum_{r=1}^n {n\choose r}r^{n-r}.$ Actually, this series came out as the answer to the question : Find the number of functions $f(n)$ on set $A,$ ...
1 vote
53 views

• 125
1 vote
33 views

1k views

### Is this a new discovery in the diagonals of Pascal's triangle?

To preface, I am a senior in high school and my knowledge of combinatorics and its notation is quite limited. I came across Pascal's triangle while drilling the binomial expansions into my head, and I ...
• 381
78 views

### Number of ways to invest $\$20,000$in units of$\$1000$ if not all the money need be spent

Working through a combinatorics section currently and am working on this $2$-part problem. I have solved part $a$ quickly and will provide my work below but am having some trouble with part $b$ and ...
1 vote
72 views

### A certain sum of multinomial coefficients

I would like to know if there is a nice expression for the sum $$S(n)=\sum_{i+j=n}\binom{3i}{i,i,i}\binom{3j}{j,j,j}$$ where $n$ is a non-negative integer. I have entered in the first few values of ...
• 35
76 views

### Find the values of $\sum_{k=0}^{n} \frac{{n\choose k }}{k+1}$

Let m be a positive integer.Find the values of $$\sum_{k=0}^n \frac{{n\choose k }}{k+1}$$. Leave your answer in terms of n where appropriate. Remark. There is an alternative method for computing the ...
• 21
1 vote
52 views

• 197
32 views

### How to prove $\sum_{k=0}^{n-1}(-1)^k\binom{n+k}{2k+1}C_k=1$? [duplicate]

How to prove the following identity? $$\sum_{k=0}^{n-1}(-1)^k\binom{n+k}{2k+1}C_k=1$$ where $C_k$ is the $k$th Catalan number, $C_n=\frac{1}{k+1}\binom{2k}{k}$. This question is similar to this but ...
69 views

### Expectation of the max number of times an element is chosen, if repeatedly randomly choosing a subset out of a set

Given a set of $n$ elements. For a total of $s$ times, you randomly choose exactly $m$ elements among them. (i.e. each $m$-element set has $p=\frac{1}{\binom{n}{m}}$ of being chosen) Here $n\gg m$ and ...
1 vote
59 views

### Sum of products of binomial coefficients.

If $(1+x+x^2)^n= \Sigma_{r=0}^{2n}a_r x^r$ then $a_r- \binom n1 a_{r-1}+\binom n2 a_{r-2}-\binom n3 a_{r-3}+....+(-1)^r\binom nr a_{0}$ is equal to (r is not a multiple of 3) Options a)0 b) $^nC_r$ c)...
• 37
69 views

### Prove that $\sum_{k=0}^{n}\binom{n}{k}\frac{1}{2n-2k+1}=\frac{(2n)!!}{(2n+1)!!}$ [closed]

Prove that \begin{equation} \sum_{k=0}^{n}\binom{n}{k}\frac{1}{2n-2k+1}=\frac{(2n)!!}{(2n+1)!!} \end{equation} This sum appears in the orthogonalization of Legendre polynomials.
263 views

### primes and binomial coefficients

Lets us denote by $\mathbb{P}$ the set of prime numbers. It is well known that, given an integer $p>1$ : $$\boxed{p\in\mathbb{P}\Leftrightarrow\forall k\in\{1,\cdots,p-1\},\,p\mid\binom pk}$$ I ...
• 7,176
131 views

### Can one expand $(a + b)^{{i}}$?

I'm solving a transcendental equation and I currently have: $$-i\ln(ix + \sqrt{1 - x^2}) = \frac{1}{(i\ln(x) + \sqrt{1 - \ln(x)^2})^i}$$ I don't know how to binomially expand the bottom denominator ... 68 views

### Sum of binomial coefficient equation

I am trying to show the following equation using binomial expansion but it's not getting me anywhere. How should I set it up? I've tried expanding $(2+2)^{n}$ and using the fact that but it's not ...
• 173
Let $n\in \mathbb{N}$, $k\in \mathbb{N}$, $k<n$, I want to prove $\log{\left(\sum_{i=0}^k \binom{n}{i}\right)} = O\left(k\log(\frac{n}{k})\right)$. I tried to use the approximation for the ...