# Tagged Questions

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

46 views

### Tricky question involving binomial expansion

For a fixed m, what is the highest power of $2$ that divides $[(\sqrt3 +1)^m]+1$? where $[x]$ denotes the greatest integer less than or equal to $x$. I have no clue how to proceed.
120 views

### Prove that ${2^n-1\choose k}$ is always odd.

How can I prove that ${2^n-1\choose k}$ always returns odd numbers? It is possible to prove this by congruence? by the way : $0 <= k <= (2^n-1)$
79 views

19 views

### How do I find the terms of an expansion using combinatorial reasoning?

From my textbook: The expansion of $(x + y)^3$ can be found using combinatorial reasoning instead of multiplying the three terms out. When $(x + y)^3 = (x + y)(x + y)(x + y)$ is expanded, all ...
30 views

### Notation for binomial coefficient set

I've been searching for a way to express "the set of all combinations generated by taking $\binom{n}{k}$ items". For example, if I have the set $\{3,7,6,5,9\}$, and I want the set of all sets that ...
33 views

75 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.
113 views

76 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 ...
80 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 ...
50 views

### Closed formula for ${r \choose 1}+{r \choose 2}\cdots{r \choose w}$ where $w < r$ [on hold]

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$?
74 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. ...
33 views

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, ...
33 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 ...
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.
166 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 ...
175 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 ...
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 $... 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 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 ... 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(\... 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 ... 2answers 808 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}{... 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 ... 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 ... 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 ... 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 \... 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 ... 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 ... 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+\... 1answer 75 views ### Can someone help me to prove this identity?$$\sum_{i=0}^{n-1} \binom{4n}{4i+1}=2^{4n-2}$$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 \sum_{k = 0}^K C_k \... 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 ... 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 ... 4answers 122 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 + \... 0answers 40 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$... 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 $$\sum_{k= 0}^{n} k \binom{n}{k} = n \cdot 2^{n - 1}$$ with the Binomial Theorem. I know that the B.T. states that (x + y)^n = ...