document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=389515>Question 389515</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Let a_n = 11...1 with 3^n digits. Prove that a_n is divisible by 3a_(n-1). </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #276061 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=276061\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> We have\r<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=a%5B0%5D+=+1 ALIGN=MIDDLE  ALT=\"a%5B0%5D+=+1\"   DISABLED_style= \"max-width:90%; height:auto;\" ><BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=a%5B1%5D+=+111 ALIGN=MIDDLE  ALT=\"a%5B1%5D+=+111\"   DISABLED_style= \"max-width:90%; height:auto;\" ><BR>\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=a%5B2%5D+=+111111111 ALIGN=MIDDLE  ALT=\"a%5B2%5D+=+111111111\"   DISABLED_style= \"max-width:90%; height:auto;\" >, etc.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Proceed by induction. The base case n = 1 works, as 111 is divisible by 3. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "For some <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=k+%3E=+0 ALIGN=MIDDLE  ALT=\"k+%3E=+0\"   DISABLED_style= \"max-width:90%; height:auto;\" >,\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=a%5Bk%5D+=+%2810%5E%283%5Ek%29+-+1%29%2F9 ALIGN=MIDDLE  ALT=\"a%5Bk%5D+=+%2810%5E%283%5Ek%29+-+1%29%2F9\"   DISABLED_style= \"max-width:90%; height:auto;\" >\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Then, for k+1,\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=a%5Bk%2B1%5D+=+%2810%5E%283%5E%28k%2B1%29%29+-+1%29%2F9 ALIGN=MIDDLE  ALT=\"a%5Bk%2B1%5D+=+%2810%5E%283%5E%28k%2B1%29%29+-+1%29%2F9\"   DISABLED_style= \"max-width:90%; height:auto;\" >\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "It suffices to show that <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=a%5Bk%2B1%5D%2F%283a%5Bk%5D%29 ALIGN=MIDDLE  ALT=\"a%5Bk%2B1%5D%2F%283a%5Bk%5D%29\"   DISABLED_style= \"max-width:90%; height:auto;\" > is an integer. Substituting <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=a%5Bk%2B1%5D%7D%7D+and+%7B%7B%7Ba%5Bk%5D ALIGN=MIDDLE  ALT=\"a%5Bk%2B1%5D%7D%7D+and+%7B%7B%7Ba%5Bk%5D\"   DISABLED_style= \"max-width:90%; height:auto;\" >, we obtain:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=%2810%5E%283%5E%28k%2B1%29%29+-+1%29%2F%283%2A%2810%5E%283%5Ek%29-1%29%29 ALIGN=MIDDLE  ALT=\"%2810%5E%283%5E%28k%2B1%29%29+-+1%29%2F%283%2A%2810%5E%283%5Ek%29-1%29%29\"   DISABLED_style= \"max-width:90%; height:auto;\" >\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Letting <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=z+=+10%5E%283%5Ek%29-1 ALIGN=MIDDLE  ALT=\"z+=+10%5E%283%5Ek%29-1\"   DISABLED_style= \"max-width:90%; height:auto;\" >, we have\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=z%5E3+=+%2810%5E%283%5Ek%29-1%29%5E3+=+10%5E%283%5E%28k%2B1%29%29+-+3%2810%5E%282%2A3%5Ek%29%29+%2B+3%2810%5E%283%5Ek%29%29+-+1 ALIGN=MIDDLE   DISABLED_style= \"max-width:90%; height:auto;\" >\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Rearrange the terms:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=10%5E%283%5E%28k%2B1%29%29+-+1+=+z%5E3+-+3%2810%5E%282%2A3%5Ek%29+-+10%5E%283%5Ek%29%29+=+z%5E3+-+3%2A%2810%5E%283%5Ek%29%29%2810%5E%283%5Ek%29+-+1%29+=+z%5E3+-+3%2A%2810%5E%283%5Ek%29%29%2Az ALIGN=MIDDLE   DISABLED_style= \"max-width:90%; height:auto;\" >\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The last term is equivalent to the numerator in the fraction we wish to prove is an integer. Therefore, we can substitute this expression and obtain\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=%28z%5E3+-+3%2A%2810%5E%283%5Ek%29%29%2Az%29%2F3z ALIGN=MIDDLE  ALT=\"%28z%5E3+-+3%2A%2810%5E%283%5Ek%29%29%2Az%29%2F3z\"   DISABLED_style= \"max-width:90%; height:auto;\" > (we are trying to prove this is an integer for all k)\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Cancel out z from both sides to get\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "<IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=%28z%5E2+-+3%2A%2810%5E%283%5Ek%29%29%29%2F3 ALIGN=MIDDLE  ALT=\"%28z%5E2+-+3%2A%2810%5E%283%5Ek%29%29%29%2F3\"   DISABLED_style= \"max-width:90%; height:auto;\" >\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "It now suffices to prove that the numerator is divisible by 3, which happens if and only if <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=z%5E2 ALIGN=MIDDLE  ALT=\"z%5E2\"   DISABLED_style= \"max-width:90%; height:auto;\" > is divisible by 3. However, we already know that <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=z+=+10%5E%283%5Ek%29+-+1 ALIGN=MIDDLE  ALT=\"z+=+10%5E%283%5Ek%29+-+1\"   DISABLED_style= \"max-width:90%; height:auto;\" > which is divisible by 3, since all powers of 10 are 1 modulo 3 (therefore subtracting 1 makes it 0 mod 3, i.e. divisible by 3). Hence, the expression is an integer, and we are done.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "This is a somewhat lengthy proof, but rigorous proofs are sometimes more efficient and strong in terms of explaining their points. You'll definitely see proofs like this in contests like USAMO, IMO, and Putnam. </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );