Question

show that
\(\dfrac{n!}{(n-r)!r!}\) is integer , w/o saying
"is an integer because this represents the "count" of number of ways of choosing "r" things from "n" things"

Answer 1

@ganeshie8 ........

Answer 2

lol this looks like an insult to my previous proof haha!

Answer 3

na :|

Answer 4

i really likes it xD

Answer 5

lets start with the inequality of greatest integer function since i know you're excited about legendre formula :)

for any two real numbers \(a, b\) we have :
\[\lfloor a+b \rfloor \ge \lfloor a\rfloor + \lfloor b \rfloor \]

Answer 6

aha

Answer 7

for example
\[\lfloor 2.6+0.6 \rfloor = 3 \ge \lfloor 2.6\rfloor + \lfloor 0.6 \rfloor = 2\]

Answer 8

ok i agree

Answer 9

next consider \(r + (n-r)\) :
\[\left\lfloor\dfrac{r+(n-r)}{p^k} \right\rfloor \ge \left\lfloor\dfrac{r}{p^k}\right\rfloor + \left\lfloor\dfrac{n-r}{p^k}\right\rfloor \]

where \(p\) is a prime factor of \(r!(n-r)!\)

Answer 10

which is same as
\[\left\lfloor\dfrac{n}{p^k} \right\rfloor \ge \left\lfloor\dfrac{r}{p^k}\right\rfloor + \left\lfloor\dfrac{n-r}{p^k}\right\rfloor \]

Answer 11

wid me so far ?

Answer 12

yess

Answer 13

recall legendre formula
left hand represents the highest exponent of prime \(p\) in \(n!\) , yes ?

Answer 14

could u type it ? i dont memorize it xD

Answer 15

wait yes i agree

Answer 16

Are you and @ganeshie8 going to keep doing this or something ?

Answer 17

yes yes

Answer 18

let me ask you a side question
whats the highest exponent of "7" in 20! ?

Answer 19

[20/7]=2

Answer 20

OK i see you still remember ;)

Answer 21

yeah like went through my memory xD
but 7 seems easy

Answer 22

we simply interpret the previous inequality for number of primes in the factoriol and conclude our proof

Answer 23

let me do it in one reply

Answer 24

k

Answer 25

@Conqueror ??

Answer 26

\[\left\lfloor\dfrac{n}{p^k} \right\rfloor \ge \left\lfloor\dfrac{r}{p^k}\right\rfloor + \left\lfloor\dfrac{n-r}{p^k}\right\rfloor \]

Left hand side gives the highest exponent of \(p\) in \(n!\)
Right hand side gives the highest expone of \(p\) in \(r!(n-r)!\)

So the inequality says that the exponent of \(p\) in \(n!\) is greater than the exponent of \(p\) in \(r!(n-r)!\)

this is true for all \(p\)
consequently \( r!(n-r)! ~| ~n!\)

Answer 27

\(\blacksquare \)

Answer 28

wow ! never seen this proof before ! loved it

Answer 29

:)

Answer 30

i was thinking of this
\(\Large \text{ you can see that }\\ \Large
\frac{n!}{(n-r)!}=n(n-1)(n-2)(n-3)\dots (n-r+1)\\ \Large
\text{ so we need to show }\\\Large
r! |n(n-1)(n-2)(n-3)\dots (n-r+1)\\ \Large
\text{W.L.O.G assume } n=r \mod r \text{ thus}\\ \Large

n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv r(r-1)(r-2)\dots 2.1 \mod r\\ \Large
n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv r! \mod r\\ \Large
n(n-1)(n-2)(n-3)\dots (n-r+1)=mr+r!\ \Large \)

Answer 31

hehe but i wasn't able to end it xD

Answer 32

we can use this fact :
any set of "r" consecutive integers form a complete set of residues "mod r"

Answer 33

yes this is what i have done

Answer 34

so one of them will be congruent to 0 mod r making the entire product vanish

Answer 35

as simple as that !

Answer 36

what do you mean, you're not able to conclude ?

Answer 37

vanish w.r to r

Answer 38

from here :-
\(n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv r! \mod r\\ \Large \)

Answer 39

Consider the product of \(r\) consecutive integers starting from \(x\) : \[x(x+1)(x+2)\cdots (x+r-1)\]

Answer 40

haha ok ok

Answer 41

they give you complete set of residues mod r in some order :
\[0\cdot 1\cdot 2\cdot 3\cdots (r-1) \pmod r\]

Answer 42

ok

Answer 43

that means \(r\) divides the product in question, yes ?

Answer 44

ok i agree huh

Answer 45

but you also have (r-1) consecutive integers
wid the same reasoning r-1 also divides the product in question, yes ?

Answer 46

ok got it

Answer 47

consider 6 consecutive integers :
`3,4,5,6,7,8`

Answer 48

just see that you also have 5 consecutive integers in them
so, 5 divides their product

Answer 49

similarly other integers less than 5 also divide that product

Answer 50

In general :

product of "r" consecutive integers is divisible by r!

Answer 51

once you know congruences, proofs become short and simple :)

Answer 52

\(
n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv r! \mod r\equiv 0 \mod r\\
n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv (r-1)!\mod r-1 \equiv 0 \mod r-1\\
n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv (r-2)! \mod r-2\equiv 0 \mod r-2\\
n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv (r-3)! \mod r-3\equiv 0 \mod r-3\\
\vdots
n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv (3)! \mod 3\equiv 0 \mod 3\\
n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv (2)! \mod 2\equiv 0 \mod 2\\
n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv (1)! \mod 1\equiv 0 \mod 1\\



n(n-1)(n-2)(n-3)\dots (n-r+1)\equiv 0 \mod r!\\
\)

Answer 53

thats right! but why not keep the proof simple

Answer 54

hehe :P

Answer 55

statement : \(r!~ | ~ n(n+1)(n+2)\cdots (n-r-1)\)

proof : Clearly the terms in the product represent \(r\) consecutive integers. So they form a complete set of residues in \(\mod r\). That means one of the term in that product is congruent to \(0 \mod r\) making the product divisible by \(r\). Inductively we conclude that the product is divisible by \(r!\) by noticing that the terms in product can form a complete set of resdidues for any integer < \(r\).

Answer 56

see if that looks good :)

Answer 57

it is :)
btw this is the only proof i have :|

Answer 58

you also have that combinatoric proof right ?

Answer 59

combinatoric ?

Answer 60

\(\large \binom{n}{r}\) is an integer, so \(r! ~|~ n(n-1)(n-2)\cdots (n-r-1)\)

Answer 61

thats the combinatoric proof ^

Answer 62

just one line

Answer 63

haha :P

Answer 64

ok , i'll force myself to agree :P

Answer 65

lol almost all combinatoric proofs involve using this binomial coefiicient being integer stuff..

Answer 66

it is easy to see that the binomial coefficient is integer if you believe in binomial theorem

Answer 67

I believe that binomial coefficient is triangle integer number then believe in binomial theorem

Answer 68

not all binomial coefficients are triangular numbers

Answer 69

triangular numbers are of form n(n+1)/2

Answer 70

ugh ok

Answer 71

so you can represent them using binomial coefficient :
\[t_n = \binom{n+1}{2}\]

Answer 72

got it

Answer 73

ok too much number theory for one day, go prepare for ur exams :)

Answer 74

i need to understand Hensel's lemma more
maybe you can help me after ur exams

Answer 75

for what u need it ?

Answer 76

hehe yeah after exams i'll write NT manual solution for burton

Answer 77

i thought hensel's lemma allows you to solve conruences of type \(r^3+r \equiv a \pmod{p^2}\) ?

Answer 78

yeah it do

Answer 79

okay after ur exams teach me then

Answer 80

k

Answer 81

i found a funny fact

Answer 82

?`

Answer 83

we know that
\(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\)

Answer 84

pascal's rule

Answer 85

keep simplifying it until we got it w.r to
\(\binom{m_i }{k-k}=1 ,~~~ s.t ~~~ m_i\le n\)

Answer 86

\(\binom{n}{k} =\) sum of integer combination

Answer 87

you will reach the first row of paslacl's triangle

Answer 88

yes yes and simplify more :)

Answer 89

\[ \sum \limits_{k=0}^n\ \binom{n}{k} = 2^n\]

you're not refering to this, right ?

Answer 90

nope

Answer 91

can u explain more, i don't get it

Answer 92

i'll show u

Answer 93

ok

Answer 94

\(\begin{align*}
\binom{n}{k}&= \binom{n-1}{k}+\binom{n-1}{k-1} \\
&=\binom{n-2}{k-2} +2\binom{n-2}{k-1}+\binom{n-2}{k}\\
&=\binom{n-3}{k-3} +3\binom{n-3}{k-2} +3\binom{n-3}{k-1}+\binom{n-3}{k} \\
&= \binom{n-4}{k-4} +4\binom{n-4}{k-3}+6\binom{n-4}{k-2} +4\binom{n-4}{k-1}+\binom{n-4}{k} \\

&= \dots \text{ so far until we reach all term have } \binom{m_i}{k-k} \text { for some } m_i\le n
\end{align*}\)

Answer 95

so we would have something like this :-

Answer 96

I know this property, it is called horshow identity or something xD
it is easy to see this in pascal triangle

Answer 97

its called "hockey stick pattern", not horse shoe haha