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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Thomas Russell Dec 23 '12 at 20:43
  • 1
    $\begingroup$ I assume you only want yes or no. It is insufficient, $k$ and $n$ are independent. $\endgroup$ – André Nicolas Dec 23 '12 at 20:44
  • 1
    $\begingroup$ 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!$. $\endgroup$ – anon Dec 24 '12 at 1:19
  • $\begingroup$ great @anon i forgot that, nice remembering und explanation! thanks a lot $\endgroup$ – doniyor Dec 24 '12 at 6:47
7
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ Oh, okay, that is what i was looking for, great thanks alot $\endgroup$ – doniyor Dec 23 '12 at 20:51
  • $\begingroup$ Good...you're on your way then! $\endgroup$ – Namaste Dec 23 '12 at 20:52
  • $\begingroup$ can you pls check my edited question? $\endgroup$ – doniyor Dec 23 '12 at 21:24
  • $\begingroup$ Yes, the statement immediately following each inductive step is what you want to prove: can you show more justification? $\endgroup$ – Namaste Dec 23 '12 at 21:27
8
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.