13
$\begingroup$

i am learning maths so fast here in MSE, thank you guys so much for being here to help us!

so now, my next step towards proficiency: :).

i am trying to prove that $\binom{n}{k}\frac{1}{n^k}\leq\frac{1}{k!}$ for $n\geq1$ and for all $k\in\Bbb{N}$. My first problem is that i never tried to prove a statement with induction where i have two dependencies. here $n$ and $k$.

induction base: $n=1$ and $k=1$. $\binom{1}{1}\frac{1}{1^1}\leq\frac{1}{1!}$ which is okay.
inductive hypothesis: for $n\geq1$ and for all $$k\in\Bbb{N},~~\binom{n}{k}\frac{1}{n^k}\leq\frac{1}{k!}$$ 1)first induction step: $$n\rightarrow n+1~~ \text{and}~~ k,\binom{n+1}{k}\frac{1}{(n+1)^{k}}\leq\frac{1}{(k)!}$$ 2)second induction step: $n$ and $$k\rightarrow k+1,~~\binom{n}{k+1}\frac{1}{(n)^{k+1}}\leq\frac{1}{(k+1)!}$$

1)$$\binom{n+1}{k}\frac{1}{(n+1)^{k}}=\Bigg(\binom{n}{k}+\binom{n}{k-1}\Bigg)\frac{1}{(n+1)^{k}} =\\ \binom{n}{k}\frac{1}{(n+1)^{k}} + \binom{n}{k-1}\frac{1}{(n+1)^{k}} \leq \frac{1}{(k)!}$$

2) Help.

I am having hard time to prove further in calculations, can you pls show me further? is 1) right? i am not sure

  • 1
    For two-point induction, you first prove the basis case for $n=k=1$, and then you have two inductive steps, first proving that if the hypothesis holds for $n=x$ and $k=y$ then $\implies$ the hypothesis holds for $n=x+1$ and $k=y$ and then show that if the hypothesis holds for $k=x$ and $n=y$ then $\implies$ that it holds for $k=x+1$ and $n=y$.2012-12-23
  • 1
    I assume you only want yes or no. It is insufficient, $k$ and $n$ are independent.2012-12-23
  • 1
    For a non-induction, combinatorial proof: ${n\choose k}k!$ is the number of ordered lists of length $k$ with entries taken from a set of size $n$ *without* repetition allowed, whereas $n^k$ is the number of ordered lists of length $k$ with entries taken from a set of size $n$ *with* repetition allowed. The lists in the former category are in the latter category but not necessarily vice-versa, which establishes the inequality by rewriting as so: ${n\choose k}k!\le n^k\iff {n\choose k}\frac{1}{n^k}\le k!$.2012-12-24
  • 0
    great @anon i forgot that, nice remembering und explanation! thanks a lot2012-12-24

2 Answers 2

7

In general, for inductions involving two independent natural numbers (here, $n$ and $k$, with $n, k \ge 1$), the strategy is as follows:

  • You first prove the basis case for $n=k=1$, which you have done.

  • Then you state an inductive hypothesis that the property holds for $n = a$ and $k = b$.

  • Then you need two inductive steps, and for each you assume the inductive hypothesis to be true, i.e. you'll want to use the inductive hypothesis to

    • First, prove the hypothesis also holds for $n=a+1$ and $k = b$; and
    • Then, prove that the hypothesis also holds for $ n=a, k = b+1$.
  • 0
    Oh, okay, that is what i was looking for, great thanks alot2012-12-23
  • 0
    Good...you're on your way then!2012-12-23
  • 0
    can you pls check my edited question?2012-12-23
  • 0
    Yes, the statement immediately following each inductive step is what you want to prove: can you show more justification?2012-12-23
8

Note that $k! \dbinom{n}k = \dfrac{n!}{(n-k)!} = n(n-1)(n-2) \cdots (n-k+1)$. Hence, you want to show that $$n(n-1)(n-2) \cdots (n-k+1) \leq n^k$$ Can you now show this?