Ok, so the question is to prove by induction that:
$${n \choose k} \le n^k$$
Where $N$ and $k$ are integers, $k \le n$;
How do I approach this? Do i choose a $n$ and a $k$ to form my base case?
Asked
Active
Viewed 85 times
0
-
1hint: ${n\choose k} = \frac{n(n-1)\cdots (n-k+1)}{k!}$ – mookid Mar 05 '14 at 06:18
2 Answers
2
While there are various ways to approach this, I would recommend fixing (an arbitrary) $n$ and inducting on $k$. So your base case would then be to show that $\binom{n}{0} \leq n^0$. To do the inductive step, figure out what you would need to multiply $\binom{n}{k-1}$ by to get $\binom{n}{k}$.
RghtHndSd
- 7,715
0
You need to prove this for all $n$ and all $k$, right? Then, to do it by induction, you must take an arbitrary $n$ and then induct on $k$.
Stella Biderman
- 31,155
-
There is no need to induct on both $k$ and $n$. Actually induction on $n$ seems pretty difficult. – Marc van Leeuwen Mar 05 '14 at 06:51
-
1