document.write( "Question 1073142: PLEASE HELP!!!\r
\n" ); document.write( "\n" ); document.write( "Prove that U
\n" ); document.write( "(n choose k-1) + (n choose k)=(n+1 choose k)\r
\n" ); document.write( "\n" ); document.write( "for all natural numbers n and k, with k ≤ n. \n" ); document.write( "

Algebra.Com's Answer #687976 by KMST(5328) $\"\"$ $\"About$

You can put this solution on YOUR website!
$\"%28matrix%282%2C1%2Cn%2Ck-1%29%29\"$ $\"%22=%22\"$ $\"n%21%2F%28%28k-1%29%21%28n-%28k-1%29%29%21%29\"$ $\"%22=%22\"$ $\"n%21%2F%28%28k-1%29%21%28n-k%2B1%29%21%29\"$ is n choose k-1.
\n" ); document.write( " $\"%28matrix%282%2C1%2Cn%2Ck%29%29\"$ $\"%22=%22\"$ $\"n%21%2F%28k%21%28n-k%29%21%29\"$ is n choose k.
\n" ); document.write( "The key to the proof is understanding that for any positive integer, $\"h\"$ ,
\n" ); document.write( " $\"%28h%2B1%29%21\"$ $\"%22=%22\"$ $\"%28h%2B1%29%2Ah%21\"$ .
\n" ); document.write( "Let us add those two fractions.
\n" ); document.write( " $\"%28matrix%282%2C1%2Cn%2Ck-1%29%29\"$ $\"%22%2B%22\"$ $\"%28matrix%282%2C1%2Cn%2Ck%29%29\"$ $\"%22=%22\"$ $\"n%21%2F%28%28k-1%29%21%28n-k%2B1%29%21%29%2Bn%21%2F%28k%21%28n-k%29%21%29\"$
\n" ); document.write( "Taking out the common factors, we get
\n" ); document.write( " $\"%28matrix%282%2C1%2Cn%2Ck-1%29%29\"$ $\"%22%2B%22\"$ $\"%28matrix%282%2C1%2Cn%2Ck%29%29\"$ $\"%22=%22\"$ $\"%28n%21%2F%28%28k-1%29%21%28n-k%29%21%29%29%2A%281%2F%28n-k%2B1%29%2B1%2Fk%29\"$
\n" ); document.write( "Now we just have to deal with that simpler sum,
\n" ); document.write( "using as common denominator the product
\n" ); document.write( " $\"%28n-k%2B1%29k\"$ .
\n" ); document.write( "So, we get
\n" ); document.write( " $\"%28matrix%282%2C1%2Cn%2Ck-1%29%29\"$ $\"%22%2B%22\"$ $\"%28matrix%282%2C1%2Cn%2Ck%29%29\"$ $\"%22=%22\"$

\n" ); document.write( " $\"%22=%22\"$ $\"%28n%21%28n%2B1%29%29%2F%28%28%28k-1%29%21k%29%28%28n-k%2B1%29%28n-k%29%21%29%29\"$
\n" ); document.write( " $\"%22=%22\"$ $\"%28n%2B1%29%21%2F%28k%21%28n-k%2B1%29%21%29\"$ $\"%22=%22\"$ $\"%28n%2B1%29%21%2F%28k%21%28%28n%2B1%29-k%29%21%29\"$ $\"%22=%22\"$ $\"%28matrix%282%2C1%2Cn%2B1%2Ck%29%29\"$ \n" ); document.write( "

\n" );