1
vote
0answers
21 views

Bound the expression with Stirling approx.

I already compute 2 expressions of one problem, but they are so complicated as below. My prof requests me to reduce them or upper bound them by Stirling approximation but I have not succeeded. 1/ ...
5
votes
1answer
110 views

Combinations mod $n$ property

So after some "fooling around" I came across this property in Pascal's triangle (which seems to repeat, and makes a lot of sense): $\begin{pmatrix} n \\ k \end{pmatrix} \mod n = \begin{cases} n ...
0
votes
0answers
41 views

A sum of powers of binomials

For $n$ and $k$ non-negative integers, let $$F(n,k) = \sum_{i=0}^{n}\binom{n}{i}^k.$$ For example, $F(n,0)=n+1$, $F(n,1)=2^n$ and $F(n,2)=\binom{2n}{n}$. Does there exist a general formula for ...
2
votes
2answers
30 views

highest power of prime $p$ dividing $\binom{m+n}{n}$

How to prove the theorem stated here. Theorem. (Kummer, 1854) The highest power of $p$ that divides the binomial coefficient $\binom{m+n}{n}$ is equal to the number of "carries" when adding $m$ ...
1
vote
1answer
44 views

How to simplify $F(x)=\sum_{n}^{\infty}\sum_{k}^{\infty}{n-k-1\choose k}x^n$?

This generating function is equivalent to $$\sum_{n}^{\infty}F_n x^n=\dfrac{x}{1-x-x^2}$$ where $F_n$ is a fibonacci number. To show this, I need to simplify the above generating function with ...
0
votes
0answers
55 views

$\sum_{k=1}^{n}\dfrac{(-1)^{k+1}}{k}{n\choose k}=\sum_{k=1}^n\dfrac{1}{k}$

If $n$ is a positive integer, then the above identity holds. I tried to solve this question using generating function. $$A(x)=\sum_n\left(\sum_{k=1}^n\dfrac{1}{k}\right)x^n=-\dfrac{\log(1-x)}{1-x}$$ ...
1
vote
1answer
60 views

Binomial Coefficient Even or Odd? [duplicate]

How to check whether the value of binomial coefficient nCr is even or odd ?
1
vote
1answer
35 views

Help with this hard recurrence relation question

Please help with this. Suppose $\{a_n\}$ satisfies $$a_n=(n+1)a_{n-1}-(n-2)a_{n-2}-(n-5)a_{n-3}+(n-3)a_{n-4},$$ and $a_0=a_1=1,a_2=a_3=0$. Please sort out the general form of $a_n$. I guess $a_n$ ...
1
vote
1answer
35 views

Proof on Divisibility of Binomial Coefficients

Prove that $\exists \ i$ $(0 \lt i \lt n)$ such that $$ n \nmid {n \choose i} $$ $\forall \ n$ such that $n \gt 0$ and $n$ is a composite Number.
8
votes
2answers
238 views

Computing the last non-zero digit of ${1027 \choose 41}$?

I am working on the following problem: Let $x_n$ be a sequence of positive odd numbers. If $N$ is the number of ordered pairs $(x_1, x_2, x_3, \dots, x_{42})$ such that $$x_1 + x_2 + x_3 + \dots + ...
5
votes
2answers
568 views

Proving $\sum_{k=1}^n{2k-1\choose k}{2n-2k+1\choose n-k+1}=4^n-{2n+1\choose n+1}$

Some background. I was asked to find an arithmetic function $f$ such that $f*f=\mathbf 1$ where $\mathbf 1$ is the constant function 1 and $*$ denotes Dirichlet convolution. I was able to prove that ...
0
votes
1answer
39 views

Why can't C(n,k) have a prime factor that is larger than n?

let C be the choose function, defined as: $C(n,k)=\frac{n!}{k!(n-k)!)}$ Why can't C(n,k) have a prime factor larger than n? I don't know much about the relationship between the binomial coefficient ...
4
votes
1answer
84 views

Simple method for $\frac{(2n+1)!}{(n!)^{2}}$ divide $lcm(1,2,\ldots,2n+1)$

The question is to prove that $\frac{(2n+1)!}{(n!)^{2}}$ divides $lcm(1,2,\ldots,2n+1)$. This seems like it should be a simple question, but try as I might, I can't seems to find any way that does ...
4
votes
3answers
120 views

How many numbers $k$ of $200 \choose k$ are divisible by $3$? $k \in \{0,1,2,\cdots 200\}$

"How many of the numbers (200 Choose k), where k is an element of the set {0,1,2,3,4,....,200} are divisible by 3? " Here is my thinking: (200 Choose 0,1, and 2) are not multiples of 3 but every ...
10
votes
2answers
118 views

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $\sum_{k=1}^n\frac{a_k-b_k}k$

Let $a_k=\frac1{\binom{n}k}$, $b_k=2^{k-n}$. Compute $$\sum_{k=1}^n\frac{a_k-b_k}k$$ By computing some partial sums, the answers are 0. It seems an inductive argument is possible.
3
votes
3answers
122 views

How prove this $\binom{n}{m}\equiv 0\pmod p$

let $p$ is prime number,and such $p\mid n,p\nmid m,n\ge m$ show that $$p\>\Big|\>\binom{n}{m}$$ I know that: if $p$ is prime number,then $$\binom{n}{p}\equiv \left[\dfrac{n}{p}\right] \pmod ...
1
vote
2answers
61 views

${{p^k}\choose{j}}\equiv 0\pmod{p}$ for $0 < j < p^k$

$${{p^k}\choose{j}}\equiv 0\pmod{p}.\ \ \ \text{for $0 < j < p^k$ and p is prime}$$ I can show this for $k=1$ using the fact that in denominator all numbers are less than $p$. I need hint ...
2
votes
2answers
58 views

If $n = mp^e$ where $e$ is maximal, then $\binom{n}{p^e}$ is not divisible by $p$.

Let $n \geq 2$ be an integer, $p$ a prime with $p^e$ the highest power of $p$ dividing $n$. Then $\binom{n}{p^e}$ is not divisible by $p$. I think you can do it using this formula for ...
3
votes
2answers
80 views

Arithmetical proof of $\cfrac{1}{a+b}\binom{a+b}{a}$ is an integer when $(a,b)=1$

When $(a,b)=1$, $\cfrac{1}{a+b}\binom{a+b}{a}$ refers to the number of paths from one corner to its opposite corner of an $a\times b$ lattice that lies completely above (or below) the diagonal. ...
3
votes
2answers
83 views

For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$

Let $A:=\sum_{k=0}^{\infty}x^{2^k}$. For what $n$ is it true that $(A+1)^n+A^n\equiv1\mod2$ (here we are basically working in $\mathbb{F}_2$.) The answer is all powers of 2, and it's fairly simple ...
3
votes
1answer
79 views

Bertrand's postulate proof

Regarding http://michaelnielsen.org/polymath1/index.php?title=Bertrand%27s_postulate I think the last inequality should be $4^{n/3}\le(2n+1)(2n)^{\sqrt{2n}}$. But even when the RHS is decreased from ...
2
votes
2answers
37 views

Finding the correct statements about $(5+2\sqrt{6})^{2n+1} = S + t$ with $S$ integer and $0 \leq t < 1$

Problem: If $n$ is a positive integer and $(5+2\sqrt{6})^{2n+1} = S + t$, where $S$ is an integer and $0 \leq t < 1$, then (a) $S$ is an odd integer (b) $S + 1$ is not divisible by ...
2
votes
0answers
38 views

Characterization of $\lambda,\mu\vdash n$ for which $\displaystyle{n\choose\mu}\mid{n\choose\lambda}$

In view of this question, I was wondering about general characterizations of $\mu,\lambda\vdash n$ for which $${n\choose\mu}\,\left|\,{n\choose\lambda}\right.,$$ (see multinomial coefficient and ...
0
votes
2answers
167 views

How to show $\binom{2p}{p} \equiv 2\pmod p$?

how to prove $\forall p$ prime : $\binom{2p}{p} \equiv 2 \pmod p$ we have: $\binom{2p}{p} = \frac{2p (2p-1)(2p-3)...1}{p!p!}$ but how to continue?
6
votes
2answers
232 views

Combinatorial proof: $p^{r-n}$ divides $\binom{p^{r-2}}{n}$

Let $p$ be an odd prime. Then if $1<n<r$, $$p^{r-n}\,\left|\,\binom{p^{r-2}}{n}\right.$$ Does anyone have a clever combinatorial proof of this fact? There's an easy argument just by counting ...
1
vote
1answer
144 views

Inequality for binomial coefficients

Let $m \leq n, n \leq N$ and $0\leq k \leq m$. I am wondering what is the dependence of $n$ and $N$ that for all $m, k$ $$ \frac{{N-m \choose n-k}}{{N \choose n}}\leq 1. $$ Thank you for your help.
4
votes
2answers
724 views

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides: $$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$ Writing these choice functions in ...
2
votes
1answer
75 views

Criterion for Wolstenholme Primes

Wolstenholme Theorem is a nice theorem that states that every prime $p >3$ satisfies: $$\binom{2p}{p} \equiv 2 \pmod {p^3}$$ A Wolstenholme prime is a prime $p$ such that $\binom{2p}{p} \equiv 2 ...
4
votes
1answer
179 views

Primes Not Dividing $\binom{2n}{n}$

Let $n \geq 3$, show ${2n \choose n}$ is not divisible by $p$ for all primes $\frac{2n}{3} <p\leq n$ Note: This fact along with other facts about ${2n \choose n}$ are used in a proof of Bertrand's ...
3
votes
0answers
129 views

Prove: $\frac{(2px)!}{((px)!)^2}\equiv\frac{(2x)!}{((x)!)^2}\pmod{p^2}$

How can I prove the following, where $p$ is a prime and $x$ a positive integer? $$\dfrac{(2px)!}{((px)!)^2}\equiv\dfrac{(2x)!}{((x)!)^2}\pmod{p^2}$$ I'm not sure if it is actually true, but I tested ...
6
votes
4answers
581 views

Fractional Binomial Coefficients

I recently examined the binomial coefficient $\binom{\frac{1}{2}}{k}$ and found that the denominator was always a power of two. The same is true of $\binom{\frac{1}{3}}{k}$, where the denominator is ...
1
vote
1answer
71 views

Does $k$-th power of $p$ divide ${}_n\!C_r$ if the previous divides $n$?

Does $p^k$ divide ${}_n\!C_r$ for all integer r if $p^k|n$ where $0\leq r \leq n$ and $p$ is prime?
4
votes
2answers
356 views

Proving ${p-1 \choose k}\equiv (-1)^{k}\pmod{p}: p \in \mathbb{P}$ [duplicate]

Possible Duplicate: Prove $\binom{p-1}{k} \equiv (-1)^k\pmod p$ The question is as follows: Let $p$ be prime. Show that ${p \choose k}\bmod{p}=0$, for $0 \lt k \lt p,\space ...
5
votes
2answers
456 views

Odd Binomial Coefficients?

By Newton's Formula: $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k $$ Proof that every $\dbinom{n}{k}$ is odd if and only if $n=2^r-1$. I have already shown that if $n$ is of the form $2^r-1$, ...
3
votes
0answers
166 views

proof of formula and calculation sum

Show that following formula is true: $$ \sum_{i=0}^{[n/2]}(-1)^i (n-2i)^n{n \choose i}=2^{n-1}n! $$ Using formula calculate $$ \sum_{i=0}^n(2i-n)^p{p \choose i} $$
1
vote
2answers
142 views

Hundreds’ place digit of $1993^3 – 913^3 – 1083^3$

How can I find the hundreds’ place digit of the following number: $$1993^3 – 913^3 – 1083^3$$ I have not tried this one since I don't know how to begin. I can tell the units digit of this but ...
-4
votes
2answers
289 views

Find the last digit of this series, for any value of $n$ and $m$,

Find the last digit of this number: $$({}_{4n+1} C_0 )^{4m+1} + ({}_{4n+1} C_1 )^{4m+1} +({}_{4n+1} C_2 )^{4m+1} + \cdots + ({}_{4n+1} C_{4n+1} )^{4m+1}\;,$$ where $n$, $m$ belong to the holy set of ...
0
votes
0answers
45 views

Solving the equation $n(n-1)\cdot\cdot\cdot(n-k+2)(n-k+1) = a$ [duplicate]

Possible Duplicate: How to reverse the $n$ choose $k$ formula? I want to calculate reverse binomial coefficients. Given a number $m$, I want to compute all possibilites how $m$ could be ...
3
votes
2answers
315 views

Number of nonnegative integral solutions of $x_1 + x_2 + \cdots + x_k = n$

To find all solutions greater than or equal to $1$ of a linear equation in the form $$x_1+x_2+x_3+\cdots+x_k=n ,$$ the number of them is $\binom{n-1}{k-1}$. If I need all solutions to be greater or ...
20
votes
6answers
4k views

prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer

Prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer. For clarity: the denominator is the only part being squared. My thought process: The numerator is the product of the first n even ...
0
votes
1answer
122 views

Divisibility question

Let $r$ be an integer greater than $2$. Is there a simple way of showing that $2^r$ divides $\left(\begin{array}{c} {2}^{r-2} \\ k \end{array}\right) 2^{2k}$ but it does not divide ...
2
votes
1answer
1k views

Proving that $n \choose k$ is an integer [duplicate]

Possible Duplicate: Proof that a Combination is an integer I can't think how to prove that ${n\choose k} \in\mathbb{Z}$. I've played with it for a while, using the factorial definition for ...
10
votes
3answers
2k views

Elementary central binomial coefficient estimates

How to prove that $\quad\displaystyle\frac{4^{n}}{\sqrt{4n}}<\binom{2n}{n}<\frac{4^{n}}{\sqrt{3n+1}}\quad$ for all $n$ > 1 ? Does anyone know any better elementary estimates?
6
votes
1answer
794 views

Relation between different ways of accessing bernoulli numbers with matrices

First Variant: Bernoulli numbers can easily be expressed by linear algebra equations. For example just using the recursion formula $$\sum_{k=0}^{n-1}{n\choose k}B_k=0$$ which is equation (34) from ...
16
votes
7answers
3k views

Prime dividing the binomial coefficients

It is quite easy to show that for every prime $p$ and $0<i<p$ we have that $p$ divides the binomial coefficient $\large p\choose i$; one simply notes that in $\large \frac{p!}{i!(p-i)!}$ the ...