contestada

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.

Respuesta :

LammettHash
When [tex]n=4[/tex], you have

[tex]\dbinom84=70>64=2^6[/tex]

but when [tex]n=5[/tex], you have

[tex]\dbinom{10}5=252<256=2^8[/tex]

so [tex]n=5[/tex] is the base case.

Assume the relation holds for [tex]n=k[/tex], i.e.

[tex]\dbinom{2k}k<2^{2k-2}[/tex]

To show that it holds for [tex]n=k+1[/tex], notice that

[tex]\dbinom{2(k+1)}{k+1}=\dfrac{(2k+2)!}{(k+1)!(k+1)!}=\dfrac{(2k+2)(2k+1)(2k)!}{(k+1)^2k!k!}[/tex]

Since [tex]\dbinom{2k}k=\dfrac{(2k)!}{k!k!}[/tex], it must be the case that

[tex]\dbinom{2(k+1)}{k+1}<\dfrac{(2k+2)(2k+1)}{(k+1)^2}2^{2k-2}[/tex]
[tex]\dbinom{2(k+1)}{k+1}<\dfrac{2k+1}{k+1}2^{2k-1}[/tex]
[tex]\dbinom{2(k+1)}{k+1}<\dfrac{k+\frac12}{k+1}2^{2k}<2^{2k}[/tex]

where the last line follows from the fact that the numerator is necessarily smaller than the denominator in [tex]\dfrac{k+\frac12}{k+1}[/tex].

Otras preguntas