Question

prove that :
C(2n,n) / 4^n <= 1/sqrt(3n +1)

Answer 1

first part is a combination, right? \[\large C(2n,n) = \frac{ (2n)! }{ n! (2n-n)! }\]

Answer 2

yes

Answer 3

@mukushla

Answer 4

proof by induction works

Answer 5

oh I tried couldn't make much progress. Please give me any hint ?

Answer 6

hold on i am trying

Answer 7

start with the LHS

write \[{2(n+1)\choose n+1}\] in terms of \[{2n\choose n}\]

Answer 8

I'll be back in ~30 min or so..time to walk the dog ;)

Answer 9

after letting C(2k,k) /4^k <= 1/sqrt(3k +1) to be true.

now we check for k+1,

in the end we get on LHS

(2k+1)/(2k+2) * C(2k,k)/4^k right ?

Answer 10

hm alright I'll wait

Answer 11

yes, since (2k+1)/(2k+2) is always <1, hence the statement for k+1 is always true whenever it is true for k
thanks a lot sire
that was quite easy actually..

Answer 12

not quite

Answer 13

\[{2(n+1)\choose n+1}/4^{n+1}=\frac{(2n+2)!}{(n+1)!(2n+2-(n+1))!4^{n+1}}\]
\[=\frac{(2n+2)(2n+1)}{(n+1)(n+1)}\frac{1}{4}{2n\choose n}/4^{n}\]

Answer 14

\[\le\frac{(2n+2)(2n+1)}{(n+1)(n+1)}\frac{1}{4}\frac{1}{\sqrt{3n+1}}=\frac{(n+1)(2n+1)}{(n+1)(n+1)}\frac{1}{2}\frac{1}{\sqrt{3n+1}}\]

Answer 15

thats what I had said ?

Answer 16

\[=\frac{(2n+1)}{(n+1)}\frac{1}{2}\frac{1}{\sqrt{3n+1}}\]

Answer 17

but you need to compare it to \[\frac{1}{\sqrt{3(n+1)+1}}\]

Answer 18

ooh :P
yes o yes

Answer 19

maybe I got carried away :|

Answer 20

\[=\frac{(2n+1)}{(n+1)}\frac{1}{2}\frac{1}{\sqrt{3n+1}}\frac{\sqrt{3n+4}}{\sqrt{3n+4}}\]

Answer 21

\[=\frac{(2n+1)}{(n+1)}\frac{1}{2}\frac{\sqrt{3n+4}}{\sqrt{3n+1}}\frac{1}{\sqrt{3n+4}}\]

Answer 22

now show \[\frac{(2n+1)}{(n+1)}\frac{1}{2}\frac{\sqrt{3n+4}}{\sqrt{3n+1}}\] is less than 1 for \(n\ge1\)

Answer 23

why less than one?
surely (2n+1)/(2n+2) is less than one
but sqrt(3n+4)/sqrt(3n+1) is greater than 1, how did you know there product is less than 1 ?

Answer 24

because I can show it to be true

Answer 25

if you show it is less than 1 then you have your proof

Answer 26

yes. i understand till here

Answer 27

compute this \[\left[\frac{(2n+1)}{(n+1)}\frac{1}{2}\frac{\sqrt{3n+4}}{\sqrt{3n+1}}\right]^2\]

Answer 28

then use the fact that if \(a>0\) and \(a^2<1\) then \(a<1\)

Answer 29

not too sure what difference will it make ?
should I open up the brackets ?

Answer 30

square everything on the inside...

Answer 31

\[=\frac{(2n+1)^2}{(n+1)^2}\frac{1}{2^2}\frac{{3n+4}}{{3n+1}}=\frac{12n^3+28n^2+19n+4}{12n^3+28n^2+20n+4}\]

Answer 32

ohh cool.. how did it ever strike you this pattern will come up? :O

Answer 33

clearly the denominator is bigger

Answer 34

experience

Answer 35

well thats great.. surely..
thanks a loads..

Answer 36

np