Question

Show that r! | n(n+1)...(n+r-1) Here n,r are positive integers.....

Answer 1

@Marki

Answer 2

lol no its ok i miss read

Answer 3

ok

Answer 4

familiar with residues\mod ?

Answer 5

no i havent heard about them...

Answer 6

ok remainder ?

Answer 7

yes

Answer 8

whaen we divide 12 by 5 remainder is 2 ok?

Answer 9

lets assume n leaves 1 as remainder when divided by r
(without lose of generality )

Answer 10

ok

Answer 11

so
n leaves 1 as remainder
n+1 leaves 2 as remainder
n+3 leaves 3 as remainder
.
.
.
n+r-1 leaves r-1 as remainder
agree ?

Answer 12

yes...

Answer 13

wait sorry typo at last step
so
n leaves 1 as remainder
n+1 leaves 2 as remainder
n+3 leaves 3 as remainder
.
.
.
n+r-1 leaves r as remainder

Answer 14

r as remainder means no remainder.... right?

Answer 15

now u can assume n have r remainder or anything u want ... this is what it means W.L.O.G

Answer 16

yes but also means it divides r , so we can write it as r instead of 0

Answer 17

ok

Answer 18

hey let me prove...!

Answer 19

now
n(n+1)...(n+r-1) is equivalent to 1.2.3.4......r (multiple of remainders , right )

Answer 20

Thank you so much...

Answer 21

ok go

Answer 22

n mod r=r
n+1 mod r=r+1
.......
(n+r-1) mod r=2r-1

Answer 23

oh no i think i messed up... @Marki

Answer 24

hmm
n+r-1=r-1 mod r

Answer 25

so it would be equivalent to
1.2.3....(r-1) r mod r , (r)! which divide r!

Answer 26

how can we say that n(n+1)...(n+r-1) is equivalent to 1.2.3...r?

Answer 27

like this
\(n(n+1)...(n+r-1) \equiv 1.2.3.....r \mod r\)

Answer 28

sorry :-( i didnt get that....

Answer 29

\(n<r\)? Clearly the thing won't work if n=10 and r=2...

Answer 30

no it works :)

Answer 31

n=10 , n+1=11,n+2=12|2!

Answer 32

Did I read it backwards? Are you looking for n(n+1)(n+2)...(n+r-1) divides r! or r! divides n(n+1)(n+2)...(n+r-1)?

Answer 33

haha my bad xD

Answer 34

Something is wrong here.
Let n=10, r=2
10*11=110
2!=2
Clearly 110 does not divide 2.

Answer 35

Is my question wrong?

Answer 36

i love wilson theorem xD i also like below combinatoric proof as it looks short and neat\[\binom{n}{r} = \dfrac{n!}{(n-r)!r!} \in \mathbb{Z}\]

Answer 37

i was proving
r!| n(n+1)...(n+r-1)

Answer 38

yes ^

Answer 39

i have edited the question, see if it looks good now :)

Answer 40

One of my textbook wrote a divides b as b|a so I am not surprised that there are some notation confusion.

Answer 41

\(a ~|~ b\) is read as \(a\) divides \(b\)

Answer 42

examples :
2 | 6

5 | 25

7 | 28

@amilapsn

Answer 43

Yeah my textbook is full of errors.

Answer 44

ok my bad.... ><

Answer 45

No, it was a good catch @thomas5267 :) i overlooked that mistake in the question earlier haha

Answer 46

Is it a proof by induction?

Answer 47

refering to combinotoric proof, @thomas5267 ?

Answer 48

I don't understand your proof to be honest. Could you elaborate?

Answer 49

sure, do we agree that the binomial coefficient is an integer because it simply represents the number of ways of choosing "r" different things from a set of "n" things ?

Answer 50

\[\binom{n}{r} = \dfrac{n!}{(n-r)!r!}\]
is an integer because this represents the "count" of number of ways of choosing "r" things from "n" things

Answer 51

But OP is asking for r!|n(n+1)(n+2)...(n+r-1) not r!|n(n-1)(n-2)...(n-r+1)...

Answer 52

wait does that mean my solution was right ?

Answer 53

Right, see below :
\[n(n+1)(n+2)\ldots (n-r+1) = \dfrac{n(n+1)(n+2)\ldots (n-r+1)\color{red}{(n-r)(n-r-1)\ldots 3 .2. 1}}{\color{red}{(n-r)(n-r-1)\ldots 3 .2. 1}} \]

Answer 54

\[ = \dfrac{n!}{(n-r)!}\]

Answer 55

from the binomial coefficient you know that \(\dfrac{n!}{(n-r)!r!}\) is an integer
that means \(r! ~\Bigg| ~\dfrac{n!}{(n-r)!}\)

Answer 56

its nice one

Answer 57

yes marki, your proof looks good to me !

Answer 58

haha no im saying its nice one about urs >.<

Answer 59

I am totally confused lol.

Answer 60

let me break this for you into 2-3 steps :)

Answer 61

do you agree that `n(n+1)...(n+r-1)` can be written as `n!/(n-r)!`

?

Answer 62

I don't get this part.

Answer 63

I see..
remember the permutation formula ? nPr ?

Answer 64

lets prove this

` n(n+1)...(n+r-1) = n!/(n-r)!`a

Answer 65

lets start with the right hand side :

\[\dfrac{n!}{(n-r)!}\]

Answer 66

expand the factorial down to n-r+1 term :

\[\dfrac{n!}{(n-r)!} = \dfrac{n(n-1)(n-2)\cdots (n-r+1)(n-r)!}{(n-r)!}\]

Answer 67

we're done! just cancel the (n-r)! top and bottom

Answer 68

for example :

\[\dfrac{10!}{(10-3)!} = \dfrac{10(10-1)(10-2)(10-3)!}{(10-3)!} = 10(10-1)(10-2)\]

Answer 69

(n+r-1)!=1.2.3.....(n-1)n(n+1)....(n+r-1)
n(n+1).....(n+r-1)=(n+r-1)!/(n-1)!

hehehe

Answer 70

another example :
\[\dfrac{14!}{12!} = \dfrac{14\cdot 13\cdot 12!}{12!} = 14\cdot 13 \]

Answer 71

Yes but how does n(n+1)(n+2)...(n+r-1)=n(n-1)(n-2)(n-3)...(n-r+1)?

Answer 72

Oops! i see what you're asking now :|

Answer 73

n!/(n-r)!=1.2.3..(n-r)(n-r+1)...n/1.2.3....(n-r) =(n-r+1)(n-r+2)....n hmm

Answer 74

I am too tired to continue. I have to go eat my dinner. Cya.

Answer 75

n!/(n-r)!=n(n-1)(n-2)....(n-r+2)(n-r+1)

Answer 76

i agree

Answer 77

it doesnt matter however, just consider (n+r-1)!/(n-1)! and argue the same