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)

3
votes
3answers
56 views

Combinatorial identity's algebraic proof without induction. [duplicate]

How would you prove this combinatorial idenetity algebraically without induction? $$\sum_{k=0}^n { x+k \choose k} = { x+n+1\choose n }$$ Thanks.
5
votes
6answers
102 views

Proving that ${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k} $

How can I prove that $${x +y+n- 1 \choose n}= \sum_{k=0}^n{x+n-k-1 \choose n-k}{y+k-1 \choose k} $$ I tried the following: We use the falling factorial power: $$y^{\underline k}=\underbrace{y(y-1)(...
4
votes
1answer
22 views

Find an explicit map with certain combinatorial properties

The following combinatorial problem popped up in a totally uncombinatorial context: Let $\mathcal{P}$ denote the power set of a set and let $k \in \mathbb{N}$. Is there a map $c: \mathcal{P}(\{1,2,\...
1
vote
1answer
17 views

Find a map on a power set with certain combinatorial properties

The following combinatorial problem popped up in a totally uncombinatorial context: Let $\mathcal{P}$ denote the power set of a set and let $k \in \mathbb{N}$. Is there a map $c: \mathcal{P}(\{1,2,\...
-1
votes
0answers
26 views

Bound on binomial summation

The bound for $\sum_{i=1}^n\binom{n}{i}2^i$ is $O(3^n)$ but what will be the bound for $\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i$. Any idea how should I proceed.
1
vote
1answer
34 views

A sum involving binomial coefficients and its evaluation using the Gamma function [duplicate]

Does anyone know how to prove (or a reference for) the following identity for positive integers $r$: $$\sum_{i=0}^r (-1)^i{r\choose i}\frac{1}{ir+1}= \frac{\Gamma(1+1/r)\Gamma(r+1)}{\Gamma(r+1+1/r)}$$
1
vote
0answers
53 views

Combinatorics problem involving binomial coefficient

I found this interesting problem in a Romanian mathematical magazine while preparing for the USAMO. Let $k$ be a non-zero natural number. Determine $x,y,z \in \Bbb N$ such that $$\binom {z+k}{x+y} - \...
1
vote
2answers
72 views

Is there a closed form for this binomial sum?

I am looking for a closed form of this sum:$\sum\limits_{j=k}^n\binom{j}{k}(-1)^j$ I know that this sum has a closed form: $\sum\limits_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}$ I can get this closed ...
2
votes
2answers
70 views

Finite summation including binomial coefficients and double factorials

I came across the following summation: $$ \sum_{k=0}^n\frac{(-1)^k(2k)!!}{(2k+1)!!}\dbinom{n}{k}\,\,\,\,(n\in\mathbb{N}). $$ $\tbinom{n}{k}$ are binomial coefficients, $n!/k!(n-k)!$. Mathematica told ...
0
votes
1answer
43 views

Closed formula for ${r \choose 1}+{r \choose 2}\cdots{r \choose w}$ where $w < r$

Let $r,w \in \mathbb{N}$. Are there some formula for the next sum? $${r \choose 1}+{r \choose 2}\cdots{r \choose w}$$ where $w<r$?
5
votes
2answers
73 views

How to find$\sum_{i,j,k\in \mathbb{Z}}\binom{n}{i+j}\binom{n}{j+k}\binom{n}{i+k}$ for $n \in \mathbb{N}$

Yeah, it's $$\sum_{i,j,k\in \mathbb{Z}}\binom{n}{i+j}\binom{n}{j+k}\binom{n}{i+k}$$ and we are summing over all possible triplets of integers. It appears quite obvious that result is not an infinity. ...
2
votes
1answer
33 views

Binomial identity for bijection $\mathbb N\times\mathbb N\to\mathbb N$

In a book I'm currently reading it is said (without proof) that, for an enumeration $d$ of $\mathbb N\times\mathbb N$ defined by $$d(0)=(0,0),\ d(1)=(0,1),\ d(2)=(1,0),\ d(3)=(0,2),\ d(4)=(1,1),\ d(5)=...
11
votes
2answers
466 views

Differentiating the binomial coefficient

I took a lecture in combinatorics this semester and the professor did the following step in a proof: He showed that function $f: x \mapsto \binom{x}{r}$ is convex for $x > r - 1$ (in order to use ...
3
votes
1answer
32 views

How to find number of integral solutions, containing large number of cases?

Number of positive unequal integral solutions of the equation $x+y+z=12$ can be found out knowing the cases it involves: $(1, 2, 9) , (1,3,8), (1,4,7), (1,5,6), (2,3,7), (2,4,6) and (3,4,5)$. Thus, ...
5
votes
5answers
118 views

Prove that $\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$

Prove that $$\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$$ I've tried multiple things that didn't work. Maybe this would help $$\sum_{k=0}^n \binom{3n-k}{2n}=\sum_{k=0}^n \binom{3n-(n-k)}{2n}=\...
1
vote
2answers
108 views

Combinatorial proof of $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!$, using inclusion-exclusion

If $l$ and $n$ are any positive integers, is there a proof of the identity $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$ which uses the Inclusion-Exclusion Principle? (If necessary, ...
0
votes
0answers
31 views

Given $n$ heads out of $n$ tosses. What is the posterior probability that coin is fair? [closed]

I am given an $\sigma$-fair coin with the probability of head $(\theta)$ being in the interval $[\frac{1}{2} - \sigma, \frac{1}{2} + \sigma]$. Also I am given: For a Bayesian analysis of the ...
2
votes
2answers
71 views

Show that $\sum_{k=0}^n \frac{(2n)!}{{k!^2(n-k)!}^2}= \binom{2n}{n}^2$

Show that $$\sum_{k=0}^n \frac{(2n)!}{k!^2(n-k)!^2} = \binom{2n}{n}^2.$$ I tried canceling $2n!$ from both sides then moving $k!$ to right but still not sure how to proceed.
6
votes
4answers
163 views

Proof of the summation $n!=\sum_{k=0}^n \binom{n}{k}(n-k+1)^n(-1)^k$?

I was going through a Number Theory book the other day and found this question. It asked for the proof of the following equation: $$n!=\sum_{k=0}^n \binom{n}{k}(n-k+1)^n(-1)^k$$ I tried hard but ...
3
votes
4answers
174 views

How to prove: $\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$

Show that if $m$ and $n$ are integers with $0\leq m<n$ then $$\sum_{k=m+1}^{n} (-1)^{k} \binom{n}{k}\binom{k-1}{m}= (-1)^{m+1}$$ Attempts: $(-1)^{k}\binom{n}{k}$ is the coefficient of $x^{k}$ in ...
5
votes
2answers
62 views

About “The product of the six numbers surrounding any interior number in Pascal’s triangle is a perfect square”

The current Futility Closet has this statement: "The product of the six numbers surrounding any interior number in Pascal’s triangle is a perfect square." Here is the link with a nice illustration: ...
3
votes
3answers
92 views

Coefficient of $x^{r}$

I was willing to find the coefficient of $x^{49}$ in the expression $(x+1)(x+2)...(x+100)$ But is there any kind of generalisation of finding the coefficient of $x^r , 0<r<n$ in the expression $...
2
votes
1answer
46 views

If $f(n) =\displaystyle\sum_{r=1}^{n}\Biggl(r^n\Bigg(\binom{n}{r}-\binom{n}{r-1}\Bigg) + (2r+1)\binom{n}{r}\Biggr)$, then what is $f(30)$?

Please give me hints on how to solve it. I tried 2-3 methods but it doesn't go beyond two steps. I am out of ideas now. Thank you
1
vote
0answers
21 views

Median poker hand (Texas Hold’em)

I try to find the median poker hand (Texas Hold’em). The following is given: 1) There are 52 cards 2) Assuming seven of them are chosen randomly 3) Create the best possibility with 5 of these 7 ...
3
votes
3answers
140 views

Coefficient of $x^{41}$ in $(x^5 + x^6 + x^7 + x^8 + x^9)^5$

What is the coefficient of coefficient of $x^{41}$ in $(x^5 + x^6 + x^7 + x^8 + x^9)^5$? Using summation of G.P., this is equivalent to finding the coefficient of $x^{41}$ in $$\left(x^5 \left(\...
1
vote
2answers
27 views

Number of routes

Suppose there is an ant on the point $(0,0)$ that can move one step right ($(x,y)\mapsto(x+1, y)$), one step up ($(x,y)\mapsto(x, y+1)$) or one step diagnolly ($(x,y)\mapsto(x+1, y+1)$). How many ways ...
27
votes
2answers
804 views

Proof or derivation of this identity $\lim_{n\to \infty}{\frac1{2^n}\sum_{k=0}^n\binom{n}{k}\frac{an+bk}{cn+dk}}\;\stackrel?=\;\frac{2a+b}{2c+d}$?

I just came up with the following identity while solving some combinatorial problem but not sure if it's correct. I've done some numerical computations and they coincide. $$\lim_{n\to \infty}{\frac{1}{...
0
votes
0answers
28 views

Show $\sum_{k=0}^n b_r(n,k) = (r-1)!\frac{x^{\bar{n}}}{(x+1)^{\bar{r-1}}}$ [duplicate]

Let's define $b_r(n,k)$ as $n$-permutations with $k$ cycles where numbers $1\dots r$ belong to one cycle. I tried to first define closed form for $b_r(n,k)$. My idea: We need to put $1 \dots r$ into ...
1
vote
1answer
44 views

What is the coefficient of the following

I got the question on a midterm and got it wrong. I'd like to know where I went wrong. We were supposed to find the coefficient of $x^{15}$ of$$(1-x^2)^{-10}(1-2x^9)^{-1}$$ My answer The only way to ...
-1
votes
2answers
56 views

Compute this sum $\sum\limits_{i=3}^n \binom{n}{i} \frac{i!2^{i-3}}{(i-3)!}$ [closed]

I'm having problems calculating this: $$\sum_{i=3}^n \binom{n}{i} \frac{i!2^{i-3}}{(i-3)!}$$ I got that it equals to $3^n$ but it's not the correct answer. P.S. If it is necessary I can provide my ...
7
votes
3answers
109 views

Inverse of the Pascal Matrix

Let $P_n$ be the $(n+1) \times (n+1)$ matrix that contains the numbers of Pascal's triangle in the upper triangle. For example in the case of $n=3$ $$ P_3 = \begin{pmatrix} 1 & 1 & 1 & 1 \...
1
vote
2answers
36 views

How do you write a polynomial as a linear combination of binomial coefficients?

So here Prove by induction that $n^5-5n^3+4n$ is divisible by 120 for all n starting from 3 in a proof, the needed polynomial is written as a linear combination of binomial coefficients, and I just ...
1
vote
2answers
47 views

How to use the generalized binomial theorem to produce the power series of $(1-x)^{1/2}$ [duplicate]

I am trying to see how to get from $\sqrt{1-x}$ to the power series $\displaystyle\sum_{m=0}^\infty\frac{-1}{2m-1}\,{2m \choose m}\,\frac{x^m}{4^m}$, ideally using the generalized binomial theorem. I ...
0
votes
3answers
54 views

Prove that $a_n-10a_{n-1}+a_{n-2}=0$.

Let $a_n = (5+2\sqrt{6})^n+(5-2\sqrt{6})^n$. Prove that $a_n-10a_{n-1}+a_{n-2}=0$. I think this depends on whether $n$ is even or odd so in the case $n$ is even we have $a_n = 2(\binom{n}{0}5^n+\...
0
votes
1answer
75 views

Can someone help me to prove this identity?

$$\sum_{i=0}^{n-1} \binom{4n}{4i+1}=2^{4n-2}$$
2
votes
0answers
65 views

Identity involving the Catalan numbers and binomial coefficients

Let $C_k := \frac{1}{k + 1} \binom{2k}{k}$ be the $k$-th Catalan number and let $K$ be a positive integer. I am looking for an identity or simplification of \begin{equation} \sum_{k = 0}^K C_k \...
1
vote
1answer
55 views

Function $f: \mathbb{Z} \to \mathbb{Z}^n$ related to $\sum_{k=1}^{x} k^n$.

The sequence $\{a_0,a_1,...a_x\}$ has closed form $a_n=\sum_{i=0}^{\infty} \Delta^i(0) {n \choose i}$ where $\Delta a_n$ denotes the operation mapping $a_n$ to $a_{n+1}-a_n$ and $\Delta^i(0)$ is ...
2
votes
2answers
59 views

Finding maximum value of ${n \choose r}$ for given value of n [duplicate]

While I was solving some binomial theorem chapter questions I encountered many questions which asked me me to find maximum value of ${n \choose r}$ for given value of n. Example: Find n for which $...
6
votes
4answers
121 views

Express $1 + \frac {1}{2} \binom{n}{1} + \frac {1}{3} \binom{n}{2} + \dotsb + \frac{1}{n + 1}\binom{n}{n}$ in a simplifed form

I need to express $$1 + \frac {1}{2} \binom{n}{1} + \frac {1}{3} \binom{n}{2} + \dotsb + \frac{1}{n + 1}\binom{n}{n}$$ in a simplified form. So I used the identity $$(1+x)^n=1 + \binom{n}{1}x + \...
1
vote
0answers
39 views

Binomial identity in a finite field

Suppose we have a prime $p$ and consider $\mathbb{F}_q$ where $q=p^s$ for some $s$. Fix a positive integer $m \geq 2$ and let $t \leq m-1$. Let $r$ be a positive integer such that $0 \leq r \leq q^t-1$...
0
votes
4answers
48 views

Prove $\sum_{k= 0}^{n} k \binom{n}{k} = n \cdot 2^{n - 1}$ using the binomial theorem

I'm trying to prove that \begin{equation} \sum_{k= 0}^{n} k \binom{n}{k} = n \cdot 2^{n - 1} \end{equation} with the Binomial Theorem. I know that the B.T. states that \begin{equation} (x + y)^n = ...
4
votes
3answers
67 views

Pattern with the the tetration of summations.

While dealing with a question with finding an explicit form for a sequence I noticed something: $$\sum_{x_0=0}^{n-1} 1=\frac{n}{1!}$$ $$\sum_{x_0=0}^{n-1} \sum_{x_1=0}^{x_0-1} 1=\frac{n(n-1)}{2!}$$ ...
2
votes
0answers
35 views

Is this quantity divisible by $p$?

Let $p$ be a prime. Let $$x_{1} = \binom{2p-1}{p}-1$$ $$x_{2}=\binom{3p-1}{2p}-\binom{2p-1}{p}$$ $$x_{3} = \binom{4p-1}{3p}-\binom{3p-1}{2p}$$ and I observed that for small values of $p$ $x_{1}$, $x_{...
2
votes
2answers
42 views

Trinomial Pascal's Triangle

I know that there's a trinomial theorem (and a multinomial theorem), but I was wondering if there was a similar structure for trinomials as there is for binomials, like Pascal's triangle. Thanks in ...
1
vote
1answer
56 views

Closed form for $\sum_{k=0}^{m} {\binom {m}{k}} a^{k} (b+ck)^N$

Is there a closed form for the following? $$\sum_{k=0}^{m} {\binom {m}{k}} a^{k} (b+ck)^N$$ how about a pretty limit for large $b$. I have tried using the binomial expansion for the $(b+ck)^...
11
votes
6answers
210 views

Proving $\sum_{k=1}^{n}{(-1)^{k+1} {{n}\choose{k}}\frac{1}{k}=H_n}$

I've been trying to prove $$\sum_{k=1}^{n}{(-1)^{k+1} {{n}\choose{k}}\frac{1}{k}=H_n}$$ I've tried perturbation and inversion but still nothing. I've even tried expanding the sum to try and find ...
3
votes
1answer
94 views

What is $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor \binom{n}{i}$?

Since both $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor$ and $\sum_{i=0}^n \binom{n}{i}$ have simple closed-form evaluations, it is natural to consider the evaluation of the binomial sum $\sum_{...
0
votes
1answer
74 views

Binomial coefficient paths?

Here's a problem and my attempt to answer it: We want to get a binomial coefficient identity depending on grid walking. Starting from the bottom left corner and going to the top right corner. You can ...
1
vote
1answer
63 views

binomial coefficients difference? [closed]

I need a difference of 2 binomial coefficients that would be equivalent to the following sum: $12\choose5$+$11\choose5$+$10\choose5$+$9\choose5$+$8\choose5$ How to answer this?
1
vote
1answer
84 views

Decomposition of $ \binom {n} {j-1}j^k $

It is easy to check that: $$ \binom {n} {j-1}j = \binom {n-1} {j-1}+\binom {n-1} {j-2}(n+1) $$ and $$ \binom {n} {j-1}j^2 = \binom {n-2} {j-1}+\binom {n-2} {j-2}(3n+2)+\binom {n-2} {j-3}(n+1)^2 $$ We ...