0
$\begingroup$

This is a problem from Discrete Mathematics and its Applications

  1. Let $P(n)$ be the statement that $n!<n^n$, where $n$ is an integer greater than $1$.

$\quad(a)$ What is the statement $P(2)$?
$\quad(b)$ Show that $P(2)$ is true, completing the basis step of the proof.
$\quad(c)$ What is the inductive hypothesis?
$\quad(d)$ What do you need to prove in the inductive step?
$\quad(e)$ Complete the inductive step.
$\quad(f)$ Explain why these steps show that this inequality is true whenever $n$ is an integer greater than $1$.

I am currently on part e, completing the inductive step.
Here is my work so far,

I was able to show that the basic step, $P(2)$ is true because $2! < 2^2$ or $2 < 4$
Now I am trying to show the inductive step, or $P(k)\to P(k+1)$
Assuming $P(k)$, $k! <k^k$, show $(k+1)! < (k+1)^{k+1}$
To get $(k+1)!$ on both sides, I multiplied both sides by $k +1$ to get $$(k+1)! < k^k(k+1)$$ or $$(k+1)! < k^{k + 1} + k^k$$

How can I get this expression, $k^{k + 1} + k^k$ to equate $(k+1)^{k+1}$?

$\endgroup$
  • $\begingroup$ Should not have expanded. We have $(k^k)(k+1)\lt (k+1)^k(k+1)=(k+1)^{k+1}$. $\endgroup$ – André Nicolas Feb 25 '15 at 1:47
  • $\begingroup$ You don't need to "equate", it is sufficient to establish that $k^{k+1} + k^k < (k+1)^{k+1}$ $\endgroup$ – DanielV Feb 25 '15 at 1:49
  • $\begingroup$ @DanielV wait how did you turn that screenshot to text content? $\endgroup$ – committedandroider Feb 25 '15 at 1:52
  • $\begingroup$ @committedandroider Mr. Scott did that (and well), and to see how he did it, click the edit button. $\endgroup$ – DanielV Feb 25 '15 at 1:53
1
$\begingroup$

$$(n+1)!=(n+1) n! < (n+1) n^n<(n+1) (n+1)^n=(n+1)^{n+1} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oh cause you know (n)$^n < (n+1)^n$? for integers > 1? $\endgroup$ – committedandroider Feb 25 '15 at 1:54
1
$\begingroup$

You have $$k^{k+1} + k^k = k^k(k+1) $$

Can you use this fact?

| cite | improve this answer | |
$\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.