I have to prove the following theorem:     Prove that the product of $r$ consecutive positive integers in divisible by $r!$   I am having a hard time getting a generalization down for the full set of real numbers, if I start from 1 and work up to r, I have the following:  $$r!k=\prod_{i=1}^{r}n_i$$  Can easily prove the base case of this, (n=1), and then go in to prove:  $$(r+1)!k=\prod_{i=1}^{r+1}n_i$$  Expand that out and get:  $$(r+1)r!k=n(n+1)(n+2).....(n+r)(n+r+1)$$  Can say that the product of the first $r$ elements in equal to $r!k$ by our base case. Leaving using with:  $$(r+1)k=(n+r+1)$$  Not sure where I can go from here, n is the integer that we start at, so how can I get it to work out to be equal to our induction hypothesis?
28821
How can we prove that the product of $n$ consecutive integers is divisible by $n$ factorial?     Note: In this  and the comments here the OP has clarified that he seeks a proof that "does not use the properties of binomial coefficients". Please post answers in said newer thread so that this incorrectly-posed question may be closed as a duplicate.
123871
Actually, I posted this long ago in MO but did not get a reply as it was unfit.   Now this is an exercise in some textbook (I think Apostol), and I would be happy to receive some answers.  Let $P(n)$ be the product of positive integers which are $\leq n$ and relatively prime to $n$.  Prove that $$ \displaystyle P(n) = n^{\phi(n)} \prod\limits_{d \mid n} \left(\frac{d!}{d^d} \right)^{\mu(n/d)}.$$
86253
Prove that $n&lt;3^n$ where $n \in \mathbb N$,  when $ n=1 $, I have proved it's true. And assumed when $n = p$ , $p&lt;3^p$ is true. Can any body help me in showing that it is true for $n =p+1$
19561
I am trying to prove that the product of three consecutive positive integers is never a perfect power. Can anyone point to gaps in my proof and/or post an alternate solution?  Let the three positive consecutive integers be $n - 1$, $n$ and $n + 1$ and let $(n - 1)n(n + 1) = h^k, k \ge 2$. Note that $\gcd(n - 1, n) = 1$ and $(n, n + 1) = 1$ implies that $n$ itself must be a perfect power and of the form $z^k$ (which is apparent once we look at the canonical representation of $h^k$). That means $n^2 - 1$ must be a perfect power itself and of the form $a^k$. If $n$ is odd, $n = 2m + 1$ for some $m \in \mathbb{N}$ i. e. $(n - 1)(n + 1) = 2m(2m + 2) = 2^2m(m + 1) = a^k$. Using the fact that $(m, m + 1) = 1$, $m$ and $m + 1$ must be perfect powers themselves and so $k\leq 2$. Coupled with fact that $k &gt; 1$, we infer $k = 2$. So, $n^2 - 1 = a^2$ which implies $n$ is not a natural number. We are left with the case when $n$ is even. Let $n = 2t + 1$. $(n + 1, n - 1) = 1$ as both are of (by the Euclidean algorithm). That means $n - 1$ and $n + 1$ are perfect powers. So, let $(n - 1) = b^k$ and $(n + 1) = l^k$. So, $l^k - b^k = 2$ for natural $l$ and $p$ and $k&gt;1$. I will prove that the diophantine equation has no solutions. Consider the function $f(k) = l^k - b^k - 2$. $f'(k) = \frac{1}{l}e^{k\log l} - \frac{1}{b}e^{k\log b}&gt;0$ if and only if $e^{k(log\frac{l}{b})}&gt;\frac{l}{b}$. Taking logarithm again, we get an equivalent condition $(k - 1)\log\frac{l}{b}&gt;0$ which is true as $k&gt;1$ and $l&gt;b$ as log is a monotonically increasing function.  Is my proof correct? Please feel free to chip in with your own solutions!
69970
The main question is :  Prove that $n^n&gt;1\times3\times5\times7\times\dots\times(2n-1)$  My approach :  We can write the R.H.S as,  $$\frac{(2n-1)!}{2\times4\times6\times\dots\times2(n-1)}$$ We can write $(2n-1)!$ as $(2n-3)!(2n-1)2(n-1)$  Thus, in this manner we can cancel out even terms till $n$ appears. I'm having trouble doing this. What I intend to do is say that any positive number's factorial is less than the number raised to itself. I welcome any alternate method. Please help.  P.S. I am still in high school and do not understand binomial theorem and induction.
28684
let $a_{i},i=1,2,\cdots,n$ be postive integer ,show that $$1^{n-1}2^{n-2}\cdots (n-2)^2(n-1)|\prod_{1\le i&lt;j\le n}(a_{i}-a_{j})$$  I know this $\prod_{1\le i&lt;j\le n}(a_{i}-a_{j})$ is  Vandermonde  determinants,and I found $$1^{n-1}2^{n-2}\cdots (n-2)^2\cdot (n-1)=1!2!3!\cdots (n-1)!=\prod_{1\le i&lt;j\le n}(j-i)$$ we only prove $$\prod_{1\le i&lt;j\le n}\dfrac{a_{j}-a_{i}}{j-i}$$ is integer  maybe consider Vandermonde determinants ? But I can't prove this
109324
Can anyone find a hole in my proof or tell me how to make it stronger or simpler? The &quot;lemma above&quot; referenced in the fourth paragraph is a small but solid proof showing that $r$ is strictly less than $b$ in the division algorithm if it's written $a=bq+r$.  $\mathbf {Theorem}$ If $m$ and $n$ are positive integers that are relatively prime, then there are integers $a$ and $b$ such that $am+bn=1$. $\mathbf {Proof}$ Let $D = \{d \in \Bbb Z : am+bn&gt;0\}$. Then there is a least element $l$ in D. Since $m$ and $n$ are relatively prime, we need only show that $l$ divides $m$ and $n$. Suppose $l$ does not divide $m$. Then there are integers $q$ and $r$ such that $m=ql+r$. Rewritten, we have that $r=ql-m=q(am+bn)-m=qam-m+qbn=m(qa-1)+n(qb)$. Thus, $r \in D$. By the lemma above, $r&lt;l$, contradicting that $l$ is the least element of $D$. We conclude then that $l$ divides $m$. Switching $m$ for $n$ gives the same result for $n$. Since $m$ and $n$ are relatively prime, $l=1$ and it follows that there are integers $a$ and $b$ such that $am+bn=1$.
38959
So I started with a base case $n = 1$. This yields $5|0$, which is true since zero is divisible by any non zero number. I let $n = k &gt;= 1$ and let $5|A = (k^5-k)$. Now I want to show $5|B = [(k+1)^5-(k+1)]$ is true....  After that I get lost.   I was given a supplement that provides a similar example, but that confuses me as well.   Here it is if anyone wants to take a look at it:  Prove that for all n elements of N, $27|(10n + 18n - 1)$.  Proof:  We use the method of mathematical induction. For $n = 1$, $10^1+18*1-1 = 27$.  Since $27|27$, the statement is correct in this case.  Let $n = k = 1$ and let $27|A = 10k + 18k - 1$.  We wish to show that $27|B = 10k+1 + 18(k + 1) - 1 = 10k+1 + 18k + 17$.  Consider $C = B - 10A$ ***I don't understand why A is multiplied by 10. $= (10k+1 + 18k + 17) - (10k+1 + 180k - 10)$    $= -162k + 27 = 27(-6k + 1)$.  Then $27|C$, and $B = 10A+C$. Since $27|A$ (inductive hypothesis) and $27|C$, then $B$ is the sum of two addends each divisible by $27$. By Theorem 1 (iii), $27|B$, and the proof is complete.
57867
Let $x_1,...,x_n$ be distinct integers. Prove that  $$\prod_{i&lt;j} \frac{x_i-x_j}{i-j}\in \mathbb Z$$   I know there is a solution using determinant of a matrix, but I can't remember it now. Any help will be appreciated.
53252
Use mathematical induction to prove that 6(n+2) + 7(2n+1) is divisible by 43 for n >= 1.  So start with n = 1:  6(1+2) + 7(2(1)+1) = 63 + 73 = 559 -> 559/43 = 13. So n=1 is divisible  Let P(k): 6(k+2)+7(2k+1) , where k>=1  Show that P(k+1): 6((k+1)+2) + 7(2(k+1)+1) is true  = 6(k+1+2) + 7(2k+2+1)  = 6(k+3) + 7(2k+3)  I'm unsure where to go from here, I've tried several directions after this but have got nowhere. I don't know how to get the 43 or 559 out the front.  Any help would be great
18019
I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$.  I suppose I could use the counting rules in probability, perhaps combination= ${{n} \choose {r}}=\frac{n!}{r!(n-r!)}$.  I want to see an actual proof behind this equation.  Does anyone have any ideas?
114927
I'm trying to freshen up for school in another month, and I'm struggling with the simplest of proofs!     Problem:      For any natural number $n , n^3 + 2n$ is divisible by $3.$   This makes sense      Proof:      Basis Step: If $n = 0,$ then $n^3 + 2n = 0^3 +$   $2 \times 0 = 0.$ So it is divisible by $3.$      Induction: Assume that for an arbitrary natural number $n$,   $n^3+ 2n$ is divisible by $3.$       Induction Hypothesis: To prove this for $n+1,$ first try to express $( n + 1 )^3 + 2( n + 1 )$ in terms of $n^3 + 2n$ and use   the induction hypothesis. Got it      $$( n + 1 )^3+ 2( n + 1 ) = (  n^3 + 3n^2+ 3n + 1 ) + ( 2n + 2 ) \{\text{Just some simplifying}\}$$      $$ = ( n^3 + 2n ) + ( 3n^2+ 3n + 3 ) \{\text{simplifying  and regrouping}\}$$   $$ = ( n^3 + 2n ) + 3( n^2 + n + 1 ) \{\text{factored out the 3}\}$$      which is divisible by $3$, because $(n^3 + 2n )$ is divisible by $3$   by the induction hypothesis. What?   Can someone explain that last part? I don't see how you can claim $(n^3+ 2n ) + 3( n^2 + n + 1 )$ is divisible by $3.$
49807
Let $m_1,m_2,\ldots,m_k$ be $k$ positive integers such that their reciprocals are in AP. Show that $k&lt;m_1+2$. Also find such a sequence.     Whatever way I tried, whichever formula I used, I could not eliminate the $m_k$ term, which I reckon would be the ideal scenario to find the solution. I am exhausted of any further ideas, please help. Thank you.
115524
The problem is following, prove that:  $$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$    I've tried solving this problem using mathematical induction, but I don't think that i did it correctly. Here's what i've done  $1.\ b=1\ (Basis)$  $$b!| (a+1)(a+2)...(a+b)$$ $$1 | a+1 \text{, which is true}$$  $2.\ b=k\ (Induction\ Hypothesis)$  $$k! | (a+1)(a+2)...(a+k)\text{, we assume it's true}$$ $$k!*n = (a+1)(a+2)...(a+k)\text{, n is some positive integer}$$  $3.\ b=k+1\ (Inductive\ Step)$  In order to prove I should get:  $$(k+1)!*m = (a+1)(a+2)...(a+k)(a+k+1)\text{, where m is some positive integer}$$ $$(a+1)(a+2)...(a+k)(a+k+1) = k!*n*(a+k+1)$$ $$(a+1)(a+2)...(a+k)(a+k+1) = (k+1)!*n + k!*n*a$$ $$(a+1)(a+2)...(a+k)(a+k+1) - a(a+1)(a+2)...(a+k) = (k+1)!*n$$ $$(a+1)(a+2)...(a+k)(k+1) = (k+1)!*n$$  And as you can see I'm returning at the beginning.  Also I've tried to use the fact that in b consecutive numbers, there must be at least one that divides b, but since i eliminate that number (because I couldn't be sure that the quotient is divisible with (b-1) or (b-2) or ... or 2. And after this i can't continue with (b-1) using this method, because it's not necessary for the other (b-1) to be consecutive.
40340
Prove that for any positive integers $m$ and $n$ , there exists a set of $n$ consecutive positive integers each of which is divisible by a number of the form $d^m$, where $d$ is some positive integer not equal to $1$.  I don't know how to approach this question.
15333
How to prove that $ 2&lt;(1+\frac{1}{n})^{n}$ for every integer $n&gt;1$. I was thinking by induction, it works for $n=2$ but then I couldn't move forward.
7647
Theorem. If the identity is written as the product of $r$ transpositions, $id=τ_1τ_2\dots τ_r$, then $r$ is an even number. Proof. We will employ induction on $r$. A transposition cannot be the identity; hence, $r &gt; 1$. If $r = 2$, then we are done. Suppose that $r &gt; 2$. In this case the product of the last two transpositions, $τ_{r−1}τ_r$, must be one of the following cases: $(ab)(ab) = id\\ (bc)(ab) = (ac)(bc)\\ (cd)(ab) = (ab)(cd)\\ (ac)(ab) = (ab)(bc),$ where $a$, $b$, $c$, and $d$ are distinct. The first equation simply says that a transposition is its own inverse. If this case occurs, delete $τ_{r−1} τ_r$ from the product to obtain $id=τ_1τ_2···τ_{r−3}τ_{r−2}$. By induction $r − 2$ is even; hence, $r$ must be even. In each of the other three cases, we can replace $τ_{r−1} τ_r$ with the right-hand side of the corresponding equation to obtain a new product of $r$ transpositions for the identity. In this new product the last occurrence of $a$ will be in the next-to-the-last transposition. We can continue this process with $τ_{r−2} τ_{r−1}$ to obtain either a product of $r − 2$ transpositions or a new product of $r$ transpositions where the last occurrence of $a$ is in $τ_{r−2}$. If the identity is the product of $r − 2$ transpositions, then again we are done, by our induction hypothesis; otherwise, we will repeat the procedure with $τ_{r−3}τ_{r−2}$. At some point either we will have two adjacent, identical transpositions canceling each other out or $a$ will be shuffled so that it will appear only in the first transposition. However, the latter case cannot occur, because the identity would not fix $a$ in this instance. Therefore, the identity permutation must be the product of $r − 2$ transpositions and, again by our induction hypothesis, we are done. Question: That is the proof written in the book, but unfortunately after more than $10$ times reading I don't understand the last two paragraph (i.e., from &quot;In each of the other three cases&quot;). Is there another simpler proof or could someone please clarify what is going on? Thank you.