document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=836817>Question 836817</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Prove by induction that for all n (n being positive natural numbers), \r<BR>\n" );
document.write( "\n" );
document.write( "a) (x^n) - (y^n) is a multiple of (x-y), where x does not equal y, and x and y are integers.\r<BR>\n" );
document.write( "\n" );
document.write( "b) (Sigma n, i=1) i x i! = (n+1)! - 1\r<BR>\n" );
document.write( "\n" );
document.write( "This is a discrete mathematics word problem. </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #504377 by </B><A HREF=/tutors/aboutme.mpl?userid=richard1234><B>richard1234(7193)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=richard1234><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/cgi-bin/show-face.mpl?user=richard1234><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=504377\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> a) Base cases n = 1 and n = 2 holds (you will see why I checked two cases). Assume that for some <IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\large n \ge 2\">, that <IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\large x-y | x^n - y^n\"> and <IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\large x-y| x^{n-1} - y^{n-1}\">. We look at the n+1th term:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\large x^{n+1} - y^{n-1} = (x^n - y^n)(x+y) - x^ny + y^nx = (x^n - y^n)(x+y) - xy(x^{n-1} - y^{n-1})\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The RHS is divisible by x-y by our induction hypothesis, so the LHS must also be divisible by x-y, for all natural numbers n.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "b) Again, base case n = 1 holds. Assume that the statement holds for some <IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\large n \ge 1\">. Then, by our hypothesis,\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\large \sum_{i=1}^{n+1} i \times i! = \left( \sum_{i=1}^{n} i \times i! \right) + (n+1) \times (n+1)!\">\r<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\large = (n+1)! - 1 + (n+1) \times (n+1)!\">\r<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\large = (n+2) \times (n+1)! - 1\">\r<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=\"/cgi-bin/rendertex.cgi?\large = (n+2)! - 1\">\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Therefore the statement holds for n+1, so by induction, we are done. </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );