We have to prove that  $$p\mid\binom{p}{k}$$ for $1\le k\le p-1$.  My approach was to expand $\binom{p}{k}$ and simplify as  $$\binom{p}{k}=\frac{1\cdot 2\cdot\ldots\cdot p}{1\cdot 2\cdot\ldots\cdot k\cdot 1\cdot 2\cdot\ldots\cdot (p-k-1)\cdot (p-k) }=$$  $$=\frac{(p-k+1)\cdot\ldots\cdot (p-1)\cdot p}{k!}=p\cdot\frac{(p-k+1)\cdot\ldots\cdot (p-1)}{k!}.$$  Now (because of combinatorial reasons) $\binom{p}{k}$ is an integer so the last expression above has to be an integer as well. This means that $\frac{(p-k+1)\cdot\ldots\cdot (p-1)}{k!}$ is eighter an integer self (we have then $\binom{p}{k}=p\cdot n, n\in\mathbb{Z}$) and then we are done or it becomes an integer after multiplication by $p$. Now we simplify in this expression so that the nominator and denominator is relative primes so we get  $$\frac{(p-k+1)\cdot\ldots\cdot (p-1)}{k!}=\frac{a}{b}$$  with $\gcd(a,b)=1$. Now $p$ wasn't a factor in $k!$ since $k\le p-1$ and $p$ is prime and after the simplification we only can have less factors in the denominator so $p$ cannot  be one of the factors. This means that $p=b\cdot m, m\in\mathbb{Z}$ but since $p$ was prime this implies eighter $b=1$ or $b=p$. Now if $b=1$ then the expression is an integer and we are done. And $b=p$ means that the product of all the factors left after the simplification gives $p$ and  since it was prime this means that one of the factors was $p$ itself which is a contradiction because we already saw that all the factors in the denominator has to be smaller than $p$. Q.E.D  This feels like a standard problem that one should tackle with induction but I still would like to know whether this is correct. Any help? Thanks.
20547
Prove if $p$ is a prime then $p \mid \binom pk$ for $k\in\{1,\ldots,p-1\}$  I don't really know where to begin with this one.   I can see that I have to use the fact that $p$ is prime somewhere - the same is not true for composite numbers, for example $4\nmid 6=\binom42$.  I have checked that this is true for the first few primes:    $3$ divides $\binom 31=\binom32=3$ $5$ divides both $\binom 51=\binom 54=5$ and $\binom 52=\binom 53=10$ $7$ divides $\binom71=\binom76=7$, $\binom72=\binom75=21$ and $\binom73=\binom74=35$.
107978
I am doing mathematical induction. I am stuck with the question below. The left hand side is not getting equal to the right hand side. Please guide me how to do it further.     $1\cdot 3 + 2\cdot 4 + 3\cdot 5 + \cdots + n(n+2) = \frac{1}{6}n(n+1)(2n+7)$.   Sol:  $P(n):\ 1\cdot 3 + 2\cdot 4 + 3\cdot 5 + \cdots + n(n+2) = \frac{1}{6}n(n+1)(2n+7)$.  $P(1):\ \frac{1}{6}(2)(9) = \frac{1}{2}(2)(3)$.  $P(1): 3$.  Hence it is true for $n=n_0 = 1$.  Let it be true for $n=k$.  $P(k):\ 1\cdot 3 + 2\cdot 4 + \cdots + k(k+2) = \frac{1}{6}k(k+1)(2k+7)$.  We have to prove  $P(k+1):\ 1\cdot 3 + 2\cdot 4 + \cdots + (k+1)(k+3)= \frac{1}{6}(k+1)(k+2)(2k+9)$.  Taking LHS: $$\begin{align*} 1\cdot 3 + 2\cdot 4+\cdots + (k+1)(k+2) &amp;= 1\cdot 3 + 2\cdot 4 + \cdots + k(k+2) + (k+1)(k+3)\\ &amp;= \frac{1}{6}(k+1)(k+2)(2k+9) + (k+1)(k+3)\\ &amp;= \frac{1}{6}(k+1)\left[(k+2)(2k+9) + 6k+18\right]\\ &amp;= \frac{1}{6}(k+1)\left[2k^2 + 13k + 18 + 6k + 18\right]\\ &amp;= \frac{1}{6}(k+1)\left[2k^2 + 19k + 36\right]. \end{align*}$$
104266
Please give me feedback on my answer to this question. Question: For all $ n\geq1:\binom{2n}{0}+\binom{2n}{2}+\binom{2n}{4}+\cdots+\binom{2n}{2k}+\cdots+\binom{2n}{2n} $   is equal to $ \binom{2n}{1}+\binom{2n}{3}+\binom{2n}{5}+\cdots+\binom{2n}{2k+1}+\cdots+\binom{2n}{2n-1} $. Answer: False, since;  Let $a=1,  b=-1$  and $n=1$  ,$k=0$   , using Binomial expression.  $$(a+b)^n=  \sum   \binom{n}{k}  a^{k}b^{n-k}$$  Then $(1+-1)^{2(1)}=\binom{2}{0}1^{0}(-1)^{2-0}+\binom{2}{1}1^{1}(-1)^{2-1}+\binom{2}{2}1^{2}(-1)^{2-2}=\binom{2}{0}-\binom{2}{1}+\binom{2}{2}$  Thus :For all $n\geq1:  \binom{2n}{0}+\binom{2n}{2}+\binom{2n}{4}+\cdots+\binom{2n}{2k}+\cdots+\binom{2n}{2n}   \ne \binom{2n}{1}+\binom{2n}{3}+\binom{2n}{5}+\cdots+\binom{2n}{2k+1}+\cdots+\binom{2n}{2n-1}$  .
7557
Let $p$ be an odd prime number. Prove that $$\left( \frac{1 \cdot 2}{p} \right) + \left( \frac{2 \cdot 3}{p} \right) + \left( \frac{3 \cdot 4}{p} \right) + \cdots + \left( \frac{(p-2)(p-1)}{p} \right) = -1$$ where $\left( \frac{a}{p}\right)$ is the Legendre symbol.  This seems to be a tricky one! I've tried using the property $\left( \frac{ab}{p} \right)=\left( \frac{a}{p}\right) \left( \frac{b}{p} \right)$ and prime factoring all the non-primes but to no avail. I had a quick thought of induction haha, but that was silly. I tried factoring the common Legendre symbols like $\left( \frac{3}{p}\right) \left[ \left( \frac{2}{p} \right) + \left( \frac{4}{p} \right) \right]$ but that didn't bring anything either. And I've been looking for pairwise cancellation with $1$ term leftover, but that does not seem to work.  Can you help?
9540
Fix integer $n\geq 1$. Consider the number $$1-\binom{n}{2}+\binom{n}{4}-\binom{n}{6}+\cdots$$where the sum continues as long as the lower number in the binomial is $\leq n$. Is there a way to simplify this sum?   The first few values are $1, 0, -2, -4, -4$.
111661
How do we know that $(p_1 \cdot \ldots \cdot p_k)+1$ is always prime, for $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $\ldots$ (i.e., the first $k$ prime numbers)?  Euclid's proof that there is no maximum prime number seems to assume this is true.
57759
I need to prove the following:  If $n,m,k\in \mathbb{N}$ and $k\leq m \leq n$, then  $$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$.  I did the following steps:   \begin{align} \require{cancel} \binom{n}{m}\binom{m}{k} &amp;= \binom{n}{k}\binom{n-k}{m-k} \\ \frac{n!}{m!(n-m)!}\cdot \frac{m!}{k!(m-k)!} &amp;= \frac{n!}{k!(n-k)!}\cdot \frac{(n-k)!}{(m-k)!(n-k-m+k)!}\\ \frac{n!}{\cancel{m!}(n-m)!}\cdot \frac{\cancel{m!}}{k!(m-k)!} &amp;= \frac{n!}{k!\cancel{(n-k)}!}\cdot \frac{\cancel{(n-k)}!}{(m-k)!(n-k-m+k)!} \\ \frac{n!}{k!(n-m)!(m-k)!} &amp;= \frac{n!}{k!(n-m)!(m-k)!} \end{align}  The question is: is my proof correct? Are all my steps valid?  Thanks
53752
So I'm trying to do a proof for this problem:  If $\displaystyle{k \le \left\lfloor \frac{n}{2} \right\rfloor}$ then $$\displaystyle{\binom{n}{k-1} &lt; \binom{n}{k}}$$  I can do it algebraically but my professor asked for a combinatorial proof.  How would one does it?
71474
Prove $$\sum_{k = 0}^{n}(-1)^{n - k} \binom{n}{k} \cdot k^n = n! \qquad\text{and}\qquad \sum_{k = 0}^{n}(-1)^{n - k} \binom{n}{k} \cdot k^m = 0,$$ where $m \in \{0, 1, 2, \cdots, n - 1\}$.  To be honest, I tried to use some combinatorial ideas but was not able to see interconnections. Also, I had an idea to prove it using induction but failed to do that either. Help will be much appreciated! I just got stuck and don't see any continuation of solution for this problem
52987
I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated.    Question Let the number of partitions be given by the function $p(n)$, i.e. the number of ways of writing the integer $n$ as a sum of positive integers. Prove that that if $g$ is any polynomial function in $n$, then there exists an integer $N$ such that $g(n)&lt;p(n)$ for all $n&gt;N$. Do not use the asymptotic Hardy-Ramanujan formula.    Provided Proof.    Enough to show $n^a&lt;p(n)$ for fixed positive integer $a$. (This is just saying that we want to show $p(n)$ grows faster than any degree polynomial of $n$, right?) We have that $(i_1,i_2,\ldots,i_{a+1},1^{n-i_1-\cdots -i_{a+1}})$ is a partition of $n$ as long as $i_{a+1}\leq i_a\leq \cdots i_1 \leq \lfloor\frac{n}{a+1}\rfloor$. (I really don't understand this step. What is this partition? Of the coefficients or terms of polynomial $p(n)$? And how do we know this is $\leq \lfloor\frac{n}{a+1}\rfloor$?) The number of partitions $n$ of this form is multiset binomial coefficient $$\left(\dbinom{\lfloor \frac{n}{a+1}\rfloor}{a+1}\right)=\frac{\lfloor\frac{n}{a+1}\rfloor(\lfloor\frac{n}{a+1}\rfloor+1)\cdots(\lfloor\frac{n}{a+1}\rfloor+a-1)}{(a+1)!}$$ (I'm assuming that if I can understand (2.) then I can understand this line) This means $p(n)&gt;\left(\binom{\lfloor \frac{n}{a+1}\rfloor}{a+1}\right)$ for all $n&gt;0$. Since $a$ is constant, the given fraction grows with order $n^{a+1}$, which means $p(n)&gt;n^a$ for $n$ sufficiently large. (Why does it grow with order $n^{a+1}$?)   Thanks all again in advance!
31902
Question : If $p$ is prime, and $0&lt; k&lt; p$ show that $ p \mid {p \choose k}$  ${p \choose k}$ can be rewritten as:  $${p(p-1)(p-2)\dots(p-(k-1))(p-k)! \over (p-k)!\cdot k(k-1)(k-2)\dots3\cdot2\cdot1}$$  Now the $(p-k)!$ cancels out. Since in the numerator we have k consecutive  integers, k divides one of them (not p as p is prime and $k &lt;p$). Then k-1 divides another one or two terms in the k consecutive terms (again not p). This reasoning continues until  3 and 2.   This means that ${p \choose k}$ can be rewritten as pq implying $p | {p \choose k}$  What if any of this proof is wrong. I am worried about any 'overlaps', i.e. say k-6 divides terms that k-3 divides invalidating the argument.  P.S. I hope the above is legible as I am new to this site. Thank you!
15094
Not sure if this is the right proof (i found it online):   Since $n\mid m$, if we factor $m = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, then $n = p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k} $ with $\beta_i \leq \alpha_i$. On the other hand, by the Chinese Remainder Theorem: $$(\mathbb Z_m)^\times \cong (\mathbb Z_{p_1^{\alpha_1}})^\times \times (\mathbb Z_{p_2^{\alpha_2}})^\times \times\dots \times (\mathbb Z_{p_k^{\alpha_k}})^ \times $$  $$(\mathbb Z_n)^\times \cong (\mathbb Z_{p_1^{\beta_1}})^\times \times (\mathbb Z_{p_2^{\beta_2}})^\times \times \dots \times(\mathbb Z_{p_k^{\beta_k}})^\times$$   Now, if we define: $$\pi: \mathbb Z_m \longrightarrow \mathbb Z_n,\,\,\, a+(m) \mapsto a+(n)$$  then: $$\pi: \mathbb Z_{p_1^{\alpha_1}} \times \mathbb Z_{p_2^{\alpha_2}} \times \dots \times\mathbb Z_{p_k^{\alpha_k}} \longrightarrow \mathbb Z_{p_1^{\beta_1}} \times \mathbb Z_{p_2^{\beta_2}} \times \dots \times\mathbb Z_{p_k^{\beta_k}}$$ has map: $(a+p_1^{\alpha_1},a+p_2^{\alpha_2}, \dots, a+p_k^{\alpha_k}) \mapsto (a+p_1^{\beta_1},a+p_2^{\beta_2}, \dots, a+p_r^{\beta_k})$  It suffices to show that the statement holds for $n =p^{\beta}$ and $m = p^{\alpha}$ with $\beta \leq \alpha.$ First, we notice that $(a,p^{\alpha})=1 \Leftrightarrow (a, p^{\beta}) =1$, both means that $p \nmid a$. Now, the projection: $$\pi: \mathbb Z/p^{\alpha}\mathbb Z \longrightarrow \mathbb Z/p^{\beta}\mathbb Z$$ maps $(\mathbb Z/p^{\alpha}\mathbb Z)^ \times$ to $(\mathbb Z/p^{\beta}\mathbb Z)^\times$, but $a+(p^{\alpha}) \in (\mathbb Z/p^{\alpha}\mathbb Z)^ \times$ iff $(a,p^{\alpha})=1 \Rightarrow (a, p^{\beta}) =1 $, that is $a+(p^{\beta}) \in (\mathbb Z/p^{\beta}\mathbb Z)^ \times$.  Now it is onto since if $\pi(a+(p^{\alpha})) = a+(p^{\beta}) \in (\mathbb Z/p^{\beta}\mathbb Z)^ \times$, then $(a, p^{\beta}) =1$ and this implies that $(a,p^{\alpha})=1$, so $a+(p^{\alpha}) \in (\mathbb Z/p^{\alpha}\mathbb Z)^ \times$  Then the natural surjective ring projection is also surjective on the units.
1749
Suppose that $p$ is a prime. Suppose further that $h$ and $k$ are non-negative integers such that $h + k = p − 1$.   I want to prove that $h!k! + (−1)^h \equiv 0 \pmod{p}$  My first thought is that by Wilson's theorem, $(p-1)! \equiv -1 \pmod{p}$, and $h!k!$ divides $(p-1)!$ (definition of a binomial). Where would I go from here?
39985
Prove by induction:   $$\sum_{i=1}^{n} i \cdot 2^i = (n-1) \cdot 2^{n+1} +2$$   Basis: let $p(n)$ be the predicate.  Let $n=1$ this gives $(1-1) \cdot 2^1+1+2 = 2$ and $1 \cdot 2^1 = 2$ so its true for $p(1)$  Induction: assume $n=k$ thus $$\sum_{i=1}^{k} i \cdot 2^i = (k-1) \cdot 2^{k+1} +2$$  when $n=k+1$:  $$\sum_{i=1}^{k+1} i \cdot 2^i = \sum_{i=1}^{k} i \cdot 2^i + ((k+1)-1) \cdot 2^{(k+1)+1} +2$$  $$ =(k-1) \cdot 2^{k+1} +2 + ((k+1)-1) \cdot 2^{k+2} +2$$  $$= 2^{k+1}k - 2^{k+1} +2 +2^{k+2}(k+1) - 2^{k+2}+2$$  $$=\frac{2^{k+1}k-2^{k+1}+2 \cdot 2^{k+1}(k+1)-2 \cdot 2^{k+1} +4}{2}$$  $$=2^{k+1}k-2^{k+1}+2^{k+1}(k+1)-2^{k+1}+2$$  $$= (k-1) \cdot 2^{k+1}+((k+1)-1) \cdot 2^{k+1} +2$$  I've been messing around with the arithmetic part of this for a while now and it's getting frustrating, I'm thinking that I've possibly made a mistake at the beginning of the induction step and that's why I cant get this to work, or maybe I'm just missing something in the algebra, either way can someone please help.
56958
I don't really see too many sites explaining how this is done. Does anyone know how this works? I'm trying to find $\binom{n}{k}\bmod m$, where $n$ and $k$ are large and $m$ is not prime. I think it can be done with the Chinese remainder theorem, but I don't understand how it is all put together.
5523
(a)For $m,n \in \mathbb{N}$, $m&lt;n$ and $k=0, ..., m$: $$\frac{1}{m^k} \binom{m}{k} \leq \frac{1}{n^k} \binom{n}{k}$$ (b)For $n\in \mathbb{N}$ and $k=1, ..., n:$ $$\frac{1}{n^k}  \binom{n}{k} \leq \frac{1}{k!} \leq \frac{1}{2^{k-1}}$$ (c)Show that for $n \in \mathbb{N}:$ $$2 \leq (1+ \frac{1}{n})^n &lt; 3$$ Use (a) and the binomial theorem for (b). Use the following for (c): $$\sum_{j=0}^{n}q^j=\frac{1-q^{n+1}}{1-q}$$  I've already proven (a) thanks to @trancelocation. Now I got stuck on (b) and (c). (b) I don't know how to use (a) and the binomial theorem here. $\frac{1}{n^k}  \binom{n}{k} \leq \frac{1}{k!} \leq \frac{1}{2^{k-1}} \Leftrightarrow \frac{n!}{n^k*(n-k)!* k!}\leq \frac{1}{k!} \leq \frac{1}{2^{k-1}} \Leftrightarrow \frac{n!}{n^k*(n-k)!}\leq 1 \leq \frac{k!}{2^{k-1}}$ Now I have to show: $\frac{n!}{n^k*(n-k)!}\leq 1$ and $1 \leq \frac{k!}{2^{k-1}}$ $\frac{n!}{n^k*(n-k)!} = \frac{n*(n-1)*...*(n-k+1)*[(n-k)*...*1]}{n^k*[(n-k)*...*1]}=\frac{n*...*(n-k+1)}{n^k}=\frac{n}{n}*\frac{n-1}{n}*...*\frac{n-k+1}{n} \leq 1$. The first factor is $1$. Starting from the second factor their value gets smaller, so the entire term gets smaller then $1$. I tried to do it like this: for $i=0, ..., n$:  $\frac{n-i}{n} \leq 1 \Leftrightarrow n-i \leq n \Leftrightarrow 0 \leq i$ For the second part: $\frac{k!}{2^{k-1}} \geq 1 \Leftrightarrow \frac{k!}{2^k*2} \geq 1 \Leftrightarrow \frac{k!}{2^k} \geq 2\Leftrightarrow \frac{k}{2}*\frac{k-1}{2}*\frac{k-2}{2}*...*\frac{1}{2} \geq 2$ So for $\frac{k-j}{2} \geq 2$, with $j=0, ..., k-1$ $\frac{k-j}{2} \geq 2 \Leftrightarrow k-j \geq 4$ This doesn't seem to help at all. (c)$2 \leq (1+ \frac{1}{n})^n &lt; 3$ I didn't know how to start at c) at all. The provided formula doesn't help me.
67925
Show that the product of any $m$ consecutive positive integers is divisible by $m!$.   Note that we have that $\frac{n!}{m!(n-m)!} \in \mathbb{Z}$ for $0 \leq m \leq n$.  $\require{cancel} \frac{n!}{m!(n-m)!} = \frac{n\cdot(n-1)\cdot\cdot\cdot(n-m+1)(n-m)!}{m!(n-m)!} = \frac{n\cdot(n-1)\cdot\cdot\cdot(n-m+1)\cancel{(n-m)!}}{m!\cancel{(n-m)!}} = \frac{n\cdot(n-1)\cdot\cdot\cdot(n-m+1)}{m!}$ where $n\cdot(n-1)\cdot\cdot\cdot(n-m+1)$ are $m$ consecutive integers divisible by $m!$  Of course, I'm using the fact that I know the combinations formula is an integer but given that, is the proof this simple? Or did I make an error here. Appreciate help!