document.write( "Question 756652: The number 3 can be expressed as a sum of one or more positive integers in four ways, namely, as 3, 1+2, 2+1, and 1+1+1. Show that any positive integer n can be so expressed in 2n-1 ways. \n" ); document.write( "
Algebra.Com's Answer #460359 by Edwin McCravy(20054)\"\" \"About 
You can put this solution on YOUR website!
\r\n" );
document.write( "Think of those 4 ways as ways to group a sum of 3 1's:\r\n" );
document.write( "\r\n" );
document.write( "3     = (1 + 1 + 1)\r\n" );
document.write( "1+2   = (1)+(1 + 1)\r\n" );
document.write( "2+1   = (1 + 1)+(1)\r\n" );
document.write( "1+1+1 = (1)+(1)+(1)\r\n" );
document.write( "\r\n" );
document.write( "We start with the longest possible petition\r\n" );
document.write( "\r\n" );
document.write( "3     =   (1 + 1 + 1)\r\n" );
document.write( "\r\n" );
document.write( "And we can either choose to replace either of the 2 \r\n" );
document.write( "\" + \" signs by \")+(\" or leave it as \" + \".  So starting\r\n" );
document.write( "with (1 + 1 + 1) we have 2 choices to make with each +\r\n" );
document.write( "sign,\r\n" );
document.write( "\r\n" );
document.write( "Either\r\n" );
document.write( "1. We may choose to leave it as \" + \"\r\n" );
document.write( "Or\r\n" );
document.write( "2. We may choose to change it to \")+(\"\r\n" );
document.write( "\r\n" );
document.write( "-----------\r\n" );
document.write( "\r\n" );
document.write( "For the general case, suppose we have the integer n.  Then write \r\n" );
document.write( "it as the sum of n 1's all in one set of parentheses, like this:\r\n" );
document.write( "\r\n" );
document.write( "n = (1 + 1 + 1 + ··· + 1 + 1 + 1)\r\n" );
document.write( "\r\n" );
document.write( "There are n-1 plus signs (because there is a + sign\r\n" );
document.write( "after each 1 except there isn't a + after the last one).\r\n" );
document.write( "\r\n" );
document.write( "For each of those n-1 plus signs,\r\n" );
document.write( "we have two possible choices to make:\r\n" );
document.write( "\r\n" );
document.write( "1. We may choose to leave it as \" + \"\r\n" );
document.write( "OR\r\n" );
document.write( "2. We may choose to change it to \")+(\"\r\n" );
document.write( "\r\n" );
document.write( "So there are 2 choices to make for the 1st + sign.\r\n" );
document.write( "For each of those 2 choices we can make for the 1st + sign, \r\n" );
document.write( "there are 2 choices we can make for the 2nd  + sign.\r\n" );
document.write( "That's 22 choices for the first 2 + signs.\r\n" );
document.write( "For each of those 22 choices we can make for the 1st 2 + signs, \r\n" );
document.write( "there are 2 choices we can make for the 3rd  + sign.\r\n" );
document.write( "That's 23 choices for the first 3 + signs.\r\n" );
document.write( "...\r\n" );
document.write( "\r\n" );
document.write( "this continues, and since we have (n-1) plus signs,\r\n" );
document.write( "\r\n" );
document.write( "the answer is 2n-1 ways of leaving the n-1\r\n" );
document.write( "+ signs as they are or changing them to \")+(\".\r\n" );
document.write( "\r\n" );
document.write( "Edwin
\n" ); document.write( "
\n" );