document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=872853>Question 872853</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Please help me solve this induction question using a direct proof:<BR>\n" );
document.write( "Prove by induction that n! < n^n, for positive integers n >= 2 </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #526474 by </B><A HREF=/tutors/aboutme.mpl?userid=jim_thompson5910><B>jim_thompson5910(35256)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=jim_thompson5910><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=526474\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> First prove the base case n = 2.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "n! < n^n<BR>\n" );
document.write( "2! < 2^2<BR>\n" );
document.write( "2 < 4 ... true\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Inductive Step:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Assume the n = k case is true. So assume\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "k! < k^k\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "is true. We must prove the n = k+1 case is true based on the assumption n = k.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "So start with k! < k^k and multiply both sides by k+1\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "k! < k^k<BR>\n" );
document.write( "(k+1)*k! < (k+1)*k^k\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The inequality is still true because k+1 is positive (n >= 2, so k > 2). So the inequality sign has NOT flipped. It only flips when we multiply both sides by a negative number.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Now if we replace the base 'k', of k^k on the right side, with 'k+1', we get\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "(k+1)*k! < (k+1)*k^k<BR>\n" );
document.write( "(k+1)*k! < (k+1)*(k+1)^k<BR>\n" );
document.write( "(k+1)*k! < (k+1)^1*(k+1)^k<BR>\n" );
document.write( "(k+1)*k! < (k+1)^(1+k)<BR>\n" );
document.write( "(k+1)*k! < (k+1)^(k+1)<BR>\n" );
document.write( "(k+1)! < (k+1)^(k+1)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This last inequality is certainly true because (k+1)*k! < (k+1)*k^k is true and (k+1)^k is larger than k^k. <BR>\n" );
document.write( "That means (k+1)*(k+1)^k is larger than (k+1)*k^k. <BR>\n" );
document.write( "By extension, this means (k+1)*(k+1)^k is larger than (k+1)*k!<BR>\n" );
document.write( "So the right side is still larger than the left side. That's all we care about.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "So to wrap things up we assumed the equation held true for the n = k case. Then we just showed that the n = k+1 case is true based on the assumption that the inequality holds true when n = k. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This inductive step proves n! < n^n is true for all integers n >= 2.<BR>\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );