Question

What is the value of n for which the relationship "2n choose n" < 2^(2n-2) holds? Use induction to prove that it holds for every n larger than that value as well.

Answer 1

When
`n=4`, you have


`\dbinom84=70>64=2^6`

but when
`n=5`, you have


`\dbinom{10}5=252<256=2^8`

so
`n=5` is the base case.

Assume the relation holds for
`n=k`, i.e.


`\dbinom{2k}k<2^(2k-2)`

To show that it holds for
`n=k+1`, notice that


`\dbinom{2(k+1)}{k+1}=((2k+2)!)/((k+1)!(k+1)!)=((2k+2)(2k+1)(2k)!)/((k+1)^2k!k!)`

Since
`\dbinom{2k}k=((2k)!)/(k!k!)`, it must be the case that


`\dbinom{2(k+1)}{k+1}<((2k+2)(2k+1))/((k+1)^2)2^(2k-2)`

`\dbinom{2(k+1)}{k+1}<(2k+1)/(k+1)2^(2k-1)`

`\dbinom{2(k+1)}{k+1}<(k+\frac12)/(k+1)2^(2k)<2^(2k)`

where the last line follows from the fact that the numerator is necessarily smaller than the denominator in
`(k+\frac12)/(k+1)`.