2
$\begingroup$

So I'm reviewing some problems but I can't seem to understand the part below, doesn't really have to do with induction but just so you guys understand whats going on.

Use mathematical induction to prove the following statement is true for integers $n > 1:$

$n! < n^n$

Solution

Base Case: $n = 2$

LHS: $2! = 2$

RHS: $2^2 = 4$

Because the LHS is less than the RHS the base case is shown to be true.

Inductive Hypothesis: Assume for an arbitrary positive integer $n = k$ s.t $k! < k^k$

Inductive Step: Prove for $n = k+1$ that $(k+1)! < (k+1)^{k+1}$

(starting with the IH)

$k! < k^k$

$(k+1)k! < (k+1)k^k$

$(k+1)! < (k+1)k^k$ <--

$(k+1)! < (k+1)(k+1)^k$ <--

$(k+1)! < (k+1)^{k+1}$

(starting with k+1)

(k+1)! = (k+1)k!

$(k+1)! < (k+1)k^k$ by the IH

$(k+1)! < (k+1)(k+1)^k$

$(k+1)! < (k+1)^{k+1}$

Now what I'm lost on is how did he go from $(k+1)k^k$ to $(k+1)(k+1)^k$ ?

$\endgroup$
  • 1
    $\begingroup$ The solution is just indicating that if the LHS is less than $(k+1)k^k$, then it is also less than $(k+1)(k+1)^k$. $\endgroup$ – Marcus Andrews Dec 3 '15 at 19:46
  • $\begingroup$ This might be a duplicate of this question. $\endgroup$ – mickep Dec 3 '15 at 20:08
3
$\begingroup$

In this case, both sides were not equally operated on, but instead the property "$a<b$ and $b<c$ implies $a<c$" was used.

In one of the lines you have $(k+1)! < (k+1)k^k.$

As a tangential fact, we know $(k+1)k^k < (k+1)^{k+1},\;$ since $\;(k+1)k^k < (k+1)(k+1)^k$.

From these two inequalities, it follows that $(k+1)! < (k+1)^{k+1},$ which is the next line in your proof.

$\endgroup$
  • $\begingroup$ Ahhhhh, now I see it. So $c$ is just a function he picked that is greater than $a$ and $b$ but also something that I can manipulate to finish the proof? $\endgroup$ – RiGid Dec 3 '15 at 20:24
  • $\begingroup$ Yes. Most of the basic induction proofs tend to be where you manipulate in a step-by-step fashion the induction assumption equation (or inequality), but sometimes (such as this one) you wind up stepping outside the box a little, so to speak. A possible analogy might be with a geometry proof, in which you usually only need to work with the figure given to you, but sometimes it helps to draw one or two auxiliary line segments that were not originally in the figure. $\endgroup$ – Dave L. Renfro Dec 3 '15 at 20:39
1
$\begingroup$

In the second part, you can use the fact that $(k+1)^{k+1}=\sum_{i=0}^{k+1}\binom{k+1}{i}k^i=1+\binom{k+1}{2}k+...+\underset{=(k+1)}{\underbrace{\binom{k+1}{k}}}k^k+k^{k+1}>(k+1)k^k$ and so $$(k+1)!=(k+1)k!\underset{\text{@Marcus Andrews indication}}{<}(k+1)k^k<(k+1)^{k+1}.$$

$\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.