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)

2
votes
0answers
45 views

Closed-form solution for $f(n) = \sum_{k>0}\binom{n}{2k}x^{k}$ without $\sqrt{x}$

Is it possible to reformulate the expression $$ (1+\sqrt{x})^n + (1-\sqrt{x})^n $$ in the form that contains no square roots of $x$ and no iterative sums (i.e. can be computed in constant time)? ...
2
votes
3answers
86 views

Showing ${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}$

Prove that for integers $n \geq 0$ and $a \geq 1$, $${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}.$$ I figured I'd post this question, ...
4
votes
3answers
59 views

Hypergeometric 2F1 with negative c

I've got this hypergeometric series $_2F_1 \left[ \begin{array}{ll} a &-n \\ -a-n+1 & \end{array} ; 1\right]$ where $a,n>0$ and $a,n\in \mathbb{N}$ The problem is that $-a-n+1$ is ...
3
votes
2answers
80 views

On ${-1 \choose 0}=1$, can I assume that $\frac{(-1)!}{(-1)!}=1$?

I've had to evaluate ${-1 \choose0}$ and then I discovered the following: $${-1 \choose0}=\frac{(-1)!}{(-1)!0!}=\frac{(-1)!}{(-1)!}=1$$ Can I assume that $\frac{(-1)!}{(-1)!}=1$?
1
vote
1answer
46 views

Binomial coefficients and cosin

In this question the user ask to prove the next identity: $$1 + 4\cos{2\theta} + 6 \cos{4\theta} +4\cos{6\theta}+ \cos {8\theta} =16\cos{4\theta} \cos^4 \theta$$ I realized the terms in the left ...
1
vote
1answer
33 views

What is the smallest value beside 1 of a binomial with two integer values > 0? [closed]

I'm searching for the smallest possible value of a binomial(a, b) where a >= b and both values are greater than ...
0
votes
1answer
30 views

sum of a binomial coefficient [duplicate]

Trying without success to solve the following: what is the sum of $\binom{80}{0}-\binom{80}{1}+\binom{80}{2}-\binom{80}{3}...-\binom{80}{79}+\binom{80}{80}$ any help will be greatly appreciated
1
vote
4answers
82 views

What is the coefficient of $x^{17}$ in the formula $(x^2+x)^{15} $?

What is the coefficient of $x^{17}$ in the formula $(x^2+x)^{15} $? Any idea how to solve this using the binomial coefficient formula?
1
vote
1answer
38 views

Calculating the sum of a binomial coefficient series

Calculate this: $$\bigl(\begin{smallmatrix} 80 \\0 \end {smallmatrix}\bigr)-\bigl(\begin{smallmatrix} 80 \\1 \end {smallmatrix}\bigr)+\bigl(\begin{smallmatrix} 80 \\2 \end ...
2
votes
3answers
59 views

Evaluate: $\sum_{k=2}^n\frac {n!}{(n-k)!(k-2)!}$

Evaluate: $$\sum_{k=2}^n\frac {n!}{(n-k)!(k-2)!}$$ Attempt $S_2=\frac {n!}{(n-2)!}$ $S_3=\frac {n!}{(n-3)!}$ $S_4=\frac {n!}{2(n-4)!}$ $\vdots$ $S_{n-1}=\frac {n!}{1!(n-3)!}$ $S_n=\frac ...
0
votes
0answers
40 views

Summation with Binomial Coefficients, $\sum (-1)^k \binom{m_1}{k} \binom{m_2}{k} $

I have trouble doing this summation: $$ \sum_{k=0}^{\min(m_1,m_2)} (-1)^k \binom{m_1}{k} \binom{m_2}{k} $$ where $m_1$ and $m_2$ are positive integers. Can someone help?
3
votes
4answers
61 views

Showing $\binom{2n}{n} = (-4)^n \binom{-1/2}{n}$

Is there a proof for the following identity that only uses the definition of the (generalized) binomial coefficient and basic transformations? Let $n$ be a non-negative integer. $$\binom{2n}{n} = ...
0
votes
1answer
29 views

How to find the value of the following items summed up together?

How to find the value of the following items summed up together? ...
13
votes
2answers
238 views

When $\frac{C(n, k)}{n^{k-1}} > 1$?

I came across this while considering the subset sum problem in relation to another problem. Define the ratio, $$R(n,k) = \frac{C(n, k)}{n^{k-1}} = \frac{\binom n k}{n^{k-1}}$$ and the integer ...
1
vote
2answers
82 views

Question about Binomial Sums [duplicate]

Prove that for any $a \in \mathbb{R}$ $$\sum_{k=0}^n (-1)^{k}\binom{n}{k}(a-k)^{n}=n!$$ I rewrote the sum as $$\sum_{k=0}^n \left((-1)^{k}\binom{n}{k} \sum_{i=0}^n (-1)^{i}a^{n-i} k^{i} ...
1
vote
3answers
64 views

Find the sum $\sum_{j=0}^{n}\binom{4n}{4j}$

Find the sum of the series $$\binom{4n}{0}+\binom{4n}{4}+\binom{4n}{8}+\ldots+\binom{4n}{n}=\sum_{j=0}^{n}\binom{4n}{4j}.$$ My approach is to consider $(1+x)^{4n} = \sum_{j=0}^{4n}\binom{4n}{j}x^j.$ ...
2
votes
0answers
45 views

Integers in the form $\sum_{j=0}^n a_j2^j3^{n-j}$

Let $n>0$ be an integer. Let also $a_j$ be some integer in the set $\{0,1,\ldots,\binom{n}{j}\}$ for all $j=0,1,\ldots,n$. Then, how many integers can be written in the form $$2^n ...
1
vote
1answer
29 views

Hillman and Hoggat's Binomial Generalization

In proving Gould's "Star of David" conjecture, Hillman and Hoggat generalized the binomial coefficient. First, they demand that $a_n$ be a sequence with the two properties that $$\gcd(a_m, a_n) \mid ...
2
votes
2answers
131 views

Combinatorial proof for $ \sum _{r=1} ^n r^3 \binom nr = n^2(n+3) 2^{n-3}$

Find the combinatorial proof for $$ \sum _{r=1} ^n r^3 \binom nr = n^2(n+3) 2^{n-3}$$ After proving it using algebra, I'm unable to find a combinatorial argument for the above statement. Help ...
0
votes
2answers
90 views

How many routes are there that pass through at most one congested intersection

I am trying to solve the following problem, but i am not quite sure how to attack. Problem Description A taxi drives from the intersection labeled A to the intersection labeled B in the grid of ...
1
vote
3answers
101 views

Finite summation with binomial coefficients, $\sum (-1)^k\binom{r}{k} \binom{k/2}{q}$

I came across the following finite sum involving (generalized) binomial coefficients: $$ 2^q \sum_{k=0}^r \binom{r}{k} \binom{k/2}{q} (-1)^k .$$ Putting this into Mathematica gives me: $$ (-1)^q ...
5
votes
5answers
154 views

How to find $ \binom {1}{k} + \binom {2}{k} + \binom{3}{k} + … + \binom{n}{k} $

Find $$ \binom {1}{k} + \binom{2}{k} + \binom{3}{k} + ... + \binom {n}{k} $$ if $0 \le k \le n$ Any method for solving this problem? I've not achieved anything so far. Thanks in advance!
0
votes
1answer
27 views

$X_n = \sqrt[k]{n^{p}+an^{q}+1}-\sqrt[k]{n^{p}+bn^{q}+1} $

For what given p and q below sequence is bounded? $X_n = \sqrt[k]{n^{p}+an^{q}+1}-\sqrt[k]{n^{p}+bn^{q}+1} $ where $0\leq q<p$ and $a\ne b$ My try ...
2
votes
4answers
44 views

Find the value of $ \sum _{r=0} ^{2n} r ( ^{2n}C _r) ( \frac 1{r+2} ) $

Find the value of $$ \sum _{r=0} ^{2n} r ( ^{2n}C _r ) ( \frac 1{r+2} )$$ In order to solve this I am trying to make the term(s) of the series independent of $r$. However I'm unable to solve ...
3
votes
3answers
88 views

A combinatorial identity: $\sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $

I proved this combinatorial identity while doing some linear algebra. For any positive integer $k$, $$ \sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $$ I was wondering what ...
3
votes
0answers
156 views

Sum problem involving Factorials

got the following problem to prove for $n \in \mathbb{N}$ and $1 \leq i \leq n$: \begin{equation} \sum_{k=1}^{n-i} \frac{(2n-1-i-2k)! 2^{2k}}{(n-i-k)! (n-k)! 2}=\sum_{k=1}^{n-i} \frac{(2n-1-i-k)! ...
1
vote
1answer
136 views

Need help finding a closed form for complicated sum

I'm trying to find a closed form expression for the following sequence: $$a_n=\sum_{i=1}^{n}\frac{(n-1-i+d)!}{(n-2i)!(i)!}=\sum_{i=1}^{\frac{n}{2}}\frac{(n-1-i+d)!}{(n-2i)!(i)!}$$ Where $n$ and $d$ ...
2
votes
2answers
145 views

Binomial coefficients identity: $\sum i \binom{n-i}{k-1}=\binom{n+1}{k+1}$

I am trying to prove $ \sum_{i=1}^{n-k+1} i \binom{n-i}{k-1}=\binom{n+1}{k+1} $ Whichever numbers for $k,n$ I try, the terms equal, but when I try to use induction by n, I fail to prove the ...
3
votes
0answers
49 views

An inequality concerning non-negative integer matrices with constant row and column sums

I'd appreciate any suggestions for how to prove (or disprove) the inequality described below. Some notation first: for positive integers $k$ and $M$, let ${\mathcal D}_{k,M}$ denote the set of all $k ...
0
votes
1answer
54 views

prove by inductive step [duplicate]

I have some problem to prove this statement by the Principle of mathematical Induction. $$\sum_{i=0}^{n} \binom{n}{i} = 2^n.$$ So I begin with the base step. For $n=0$, $$\sum_{i=0}^{0} \binom{0}{i} ...
1
vote
0answers
162 views

Sum concerning Catalan triangle and binomials

I am trying to prove the following relation. For $k \in \mathbb{N},k \geq 2$ and $i=1,\ldots,k-1$ \begin{equation} {2k-2-i \choose k-1-i}=\sum \limits_{l=0}^{k-1-i} 2^{2l} T(k-2-l,k-1-i-l)-2 \sum ...
3
votes
4answers
122 views

Closed form for a formula with a summation over $i\binom{n-i}{k-1}$, and combinatorial proof?

I was trying to simply an expression in an exercise related to randomized algorithms. Here is the expression which I have obtained at the end. $$ \displaystyle\frac{\displaystyle\sum_{i=1}^{n+k-1} i ...
1
vote
2answers
97 views

Using Binomial coefficient to solve a problem with unfair coins

I have 5 fair coins and 10 unfair coins in a bag. For the unfair coins, there is 80% chance of getting a head and 20% for tails. What's the probability of flipping 4 heads out of 6 flips? Each flip is ...
5
votes
1answer
106 views

Inequality with sum of Binomial coefficients.

Prove that for every positive integer $n \ge 2$$$\sum^n_{k=1}k \sqrt{\begin{pmatrix}n\\ k\end{pmatrix}}\leq\sqrt{2^{n-1}n^3}$$ I tried it by induction but I didn't know how to end it.
2
votes
1answer
141 views

Evaluate $\sum_{k=1}^{n} (2k-1){n \choose k}$ using calculus

Evaluate $\sum_{k=1}^{n} (2k-1) {n \choose k} $ using calculus I found out the value by the following method: $$T_r= (2r-1) {n\choose r}$$ $$S_r= \sum^n _{r=1} \left(2r {n\choose r} - {n\choose ...
1
vote
1answer
47 views

Inequality involving binomial coefficients

I recently stumbled upon an inequality involving binomial coefficients. There is reason to suspect that it holds for all $l\in\mathbb{N}$. It states that $$ (2l+1)^{2l+1} < \sum_{m = 0}^{l} ...
1
vote
0answers
37 views

Maximizing expected value when distribution is binomial

Consider the following problem: $$\max_{n\in\mathbb N}\;f(n)= \frac12 \left[v_0 \sum_{i=\lceil k_n \rceil}^n \binom{n}{i}p^i (1-p)^{n-i} + v_1\sum_{i=1}^{\lfloor k_n ...
10
votes
1answer
441 views

New Year Combinatorics

In the spirit of the festive period and in appreciation of the encouraging response to my X'mas Combinatorics problem posted recently, here's one for the New Year! Express the following as a ...
3
votes
1answer
58 views

Sum of squares of Binom(n,p) values

Let $x_{n,p}(j)$ be the probability that a random variable distributed according to a binomial distribution with parameters $n \in \mathbf{N}_+$ and $p \in (0,1)$ takes the value $j \in ...
0
votes
0answers
34 views

Closed form equation with binomial coefficients

I need a closed form for the sum $\sum\limits_{i=0}^{\infty}{n-iT-1 \choose i}x^i$ $n$, $T$ are constants and positive but may not be integers. However, they can take nearest integer values, if not ...
3
votes
1answer
65 views

Do these ratios of the Eulerian number triangle converge to the logarithm of x?

Consider the matrix $A_3$ with the definition if $n=k$ then $A_3(n,k)=\binom{n-1}{k-1}=1$, else if $n\ge k$ then $A_3(n,k)=\frac{\binom{n-1}{k-1}}{1-x}$ else $A_3(n,k)=0$. $\binom{n-1}{k-1}$ means the ...
9
votes
2answers
229 views

Number of ways to arrange $n$ items in $m$ positions having exactly $k$ items adjacent to each other

It was over 20 years since I studied maths and I am stuck. I'd really appreciate some help understanding this (probably quite simple) problem. I have $n$ items that I can place on $m$ positions. $m$ ...
0
votes
1answer
59 views

The limit of an infinite product involving the squares of $\binom{n}{j}x^j(1-x)^{n-j}/k$

Some months ago, me and a friend tried to solve the following $"~natural~"$ question: Given weights $p_{1},\ldots,p_{m}$ and distinct points in $S_{0} := \left\{\, x_{1},\ldots,x_{n}\,\right\}$ of ...
3
votes
0answers
78 views

Consecutive numbers in rows of Pascal's triangle …

The fourteenth row of Pascal's triangle has an interesting property. $$\begin{align} \binom{14}{4}+\binom{14}{5} &= 1001+2002 \\ =\binom{14}{6} &= 3003 \end{align}$$ This begs the ...
12
votes
7answers
1k views

How do I prove that there infinitely many rows of Pascal's triangle with only odd numbers?

This is exercise number $59$ from Chapter $2$ of Hugh Gordon's Discrete Probability. Show that there are infinitely many rows of Pascal's Triangle that consist entirely of odd numbers. ...
0
votes
2answers
50 views

How $(r-k){r \choose r-k}$ becomes $r{r-1 \choose r-k-1}$?

I'm reading Knuth/Graham/Patashnik's Concrete Mathematics: I don't understand how he goes from $(r-k){r \choose r-k}$ to $r{r-1 \choose r-k-1}$ using $(5.6)$. The mentioned property has a $k$ ...
6
votes
1answer
107 views

Is $(n+\ell)^{-1}\binom{kn}{n}$ an integer for only $(\ell,k)=(1,2)$?

Find all pairs $(\ell,k)$ of natural numbers, such that the number $\dfrac1{n+\ell}\dbinom{kn}{n}$ is an integer for all natural $n$. Is $(\ell,k)=(1,2)$ the only solution?
2
votes
1answer
54 views

How to use $\binom a k = \frac{\alpha(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}$ to check that ${-1\choose 0}=1$?

I'm trying to use the binomial coefficient: $$\binom{x}k=\begin{cases} \frac{x^{\underline k}}{k!},&\text{if }k\ge 0\\\\ 0,&\text{if }k<0\;, \end{cases}$$ To check that ${-1\choose 0}=1$. ...
1
vote
1answer
37 views

How to use $\binom a k = \frac{\alpha(a-1)(a-2)\cdots(a-k+1)}{k(k-1)(k-2)\cdots 1}$ to check that $ {-n \choose -n}=0$?

I am trying to use this definition of the binomial coefficient: $$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-[k-1])}{k(k-1)(k-2)\cdots 1}$$ To ...
1
vote
1answer
76 views

Why $ {-1\choose 3}=-1$?

Having the following definition: $$\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1}\tag{1}$$ Why $\bbox[1px,border:1px ...