Question

help please
show that 2^n divides (n+1)(n+2)...(2n)

Answer 1

How many terms are in (n+1)(n+2)...(n+n)

Answer 2

what is the base case?

Answer 3

does n starts at 0?

Answer 4

n terms i think, yes n >= 0

Answer 5

sorry it says to prove for n>=1

Answer 6

ok, use induction. Show me the base case is true

Answer 7

okay induction !

n = 1 : 2^1 = 2, (1+1) = 2
2 divides 2 so the statement is true for n=1

assume n=k : 2^k divides (k+1)(k+2)...(2k)
show that 2^(k+1) divides (k+2)(k+3)...(2(k+1))

Answer 8

lol i have tried everything except induction for the last couple of hours !

Answer 9

2^(k+1) = 2*2^k

Answer 10

yes, the inductive step is always the hardest step.

Answer 11

So start with 2^(k+1) = 2 * 2^k

Do you notice the inductive step is embedded that equation above?

Answer 12

embedded *in*

Answer 13

what do we know about 2^k ?

Answer 14

2^k divides (k+1)(k+2)...(2k)

Answer 15

2^k divides (k+1)(k+2)...(2k)


should i multiply 2 both sides ?

Answer 16

yes but before that, you should write it in terms of equation first.
what does 2^k divides (k+1)(k+2)...(2k) mean if expressed in an equation?

Answer 17

oh would that be
(k+1)(k+2)....(2k) = t*2^k ?

Answer 18

yes, there exist an integer, and you call it t, so that
2^k (t) = (k+1)(k+2)....(2k)

now multiply both sides by 2, what do you get?

Answer 19

2^(k+1)t = (k+1)(k+2)...(4k)

Answer 20

that's mathematical correct, but not helpful

Answer 21

i think (k+1)(4k) needs to be written as (2(k+1))

Answer 22

how about this,
2^(k+1)t = [2(k+1)] (k+2)...(2k)

see it?

Answer 23

BINGO ! we're done ? xD

Answer 24

haha yeah, just move the 2(k+1) to the last position
2^(k+1)t = (k+2)...(2k) 2(k+1)

Answer 25

Got it completely ! thanks a lot :D

Answer 26

no problem.

Answer 27

notice that (k+2)...(2k) 2(k+1) reall means
you start at (k+2) and multiply all the integers in between un till 2(k+1).
In other words, (k+2) (k+3) ... 2(k+1)

Answer 28

yeaap (k+1 + 1) all the way to 2(k+1)
earlier i was trying to factor out 2's from (n+1)(n+2)... (2n) and was hopeless, not sure why it was getting so complicated lol... thank you very much ! induction looks just perfect for this xD

Answer 29

so u got it ?

Answer 30

yes lol got it by induction,
still a little curious if we can see it directly

Answer 31

directly like
2^n | (n+1)(n+2)...(2n)
then
(n+1)(n+2)...(2n) mod 2^n =0 ?

Answer 32

yes exactly ! show that \((n+1)(n+2)...(2n) \equiv 0 \mod 2^n\)

Answer 33

let me think , i'll grab coffee lol

Answer 34

sure :) i got all day... nothing to hurry :)

Answer 35

by any chance, you thinking of using WIlson's thm ?

Answer 36

m back :)

Answer 37

i was thinking of somthing more dumb than welson lolz

Answer 38

im not sure if wilson is useful here lol

Answer 39

wilson is about
if p is prime then (p-1)=-1 mod p
well i would think of wilson lol
since u mention him ( i wasn't think of this method at all lol )

Answer 40

how many tems we wud get by add 1 to reach 2n ?

Answer 41

Wilson : \((p-1)! \equiv -1 \mod p\)

Answer 42

yeah made a typo :)

Answer 43

like for example
if n=5
6*7*8*9*10
5 terms .. =n

Answer 44

\((n+1)(n+2)(n+3)... (n+n)\)

so there are \(n\) terms in the product ?

Answer 45

(n+1)(n+2)...(2n)
what i ment is the terms count is n

Answer 46

yep n terms :)

Answer 47

so we wud have 2 cases :-
1- n is odd
2- n is even

Answer 48

okay

Answer 49

im thinking :D

Answer 50

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

Answer 51

\((n+1)(n+2)(n+3)... (n+n) \)


even : \(n = 2k\)
\((2k+1)(2k+2)(2k+3) .... (2k+2k) \equiv (2k)^{n} \equiv 0 \mod 2^n\)

odd : \(n = 2k+1\)
\((2k+1+1)(2k+1+2)(2k+1+3) .... (2k+1 +2k+1) \equiv (2k)^{n} \equiv 0 \mod 2^n\)

QED

Answer 52

Oh yes thats get interesting i think :

\((n+1)(n+2)(n+3)...(2n) = \dfrac{(2n)!}{n!}\)

Answer 53

you meant that right ?

Answer 54

your methd i think its wrong
how would you geranty that
1/2k .... n/2k would be integer


the second one yess i ment that since there is a theorm about 2^n

Answer 55

\((2k+1)(2k+2)(2k+3) .... (2k+2k) \)

multiply all the first terms, you wud get : \((2k)^n\), since you have \(n\) terms right ?

Answer 56

do you know this theorm ?