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.

When , you have



but when , you have



so is the base case.

Assume the relation holds for , i.e.



To show that it holds for , notice that



Since , it must be the case that





where the last line follows from the fact that the numerator is necessarily smaller than the denominator in .