document.write( "Question 1158359: prove that (n 0) + (n 1) + (n 2) + ... + (n k) = 2^n is true using mathematical induction\r
\n" ); document.write( "\n" ); document.write( "note that (n k) is a falling factorial \n" ); document.write( "

Algebra.Com's Answer #781299 by Shin123(626) $\"\"$ $\"About$

You can put this solution on YOUR website!
Base case: n=1. $\"%28matrix%282%2C1%2C1%2C0%29%29%2B%28matrix%282%2C1%2C1%2C1%29%29=1%2B1=2=2%5E1\"$ .
\n" ); document.write( "Induction step. Assume that $\"%28matrix%282%2C1%2Ck%2C0%29%29%2B%28matrix%282%2C1%2Ck%2C1%29%29\"$ +...+ $\"%28matrix%282%2C1%2Ck%2Ck-1%29%29%2B%28matrix%282%2C1%2Ck%2Ck%29%29=2%5Ek\"$ , for some arbitrary positive integer k. Lemma:

$\"%28k%2B1%29%21%2F%28j%21%28k-j%2B1%29%21%29=%28k%2B1%29%21%2F%28j%21%28k-j%2B1%29%21%29\"$ . Therefore,

. We need to find $\"%28matrix%282%2C1%2Ck%2B1%2C0%29%29%2B%28matrix%282%2C1%2Ck%2B1%2C1%29%29\"$ +...+ $\"%28matrix%282%2C1%2Ck%2B1%2Ck%29%29%2B%28matrix%282%2C1%2Ck%2B1%2Ck%2B1%29%29\"$ $\"%28matrix%282%2C1%2Ck%2B1%2C0%29%29=1\"$ .

, and so on.
So $\"%28matrix%282%2C1%2Ck%2B1%2C0%29%29%2B%28matrix%282%2C1%2Ck%2B1%2C1%29%29\"$ +...+

+...+ $\"2%28matrix%282%2C1%2Ck%2Ck%29%29%2B%28matrix%282%2C1%2Ck%2Ck%2B1%29%29\"$ . Since $\"%28matrix%282%2C1%2Ck%2Ck%2B1%29%29=0\"$ , we can use our assumption and get $\"%28matrix%282%2C1%2Ck%2B1%2C0%29%29%2B%28matrix%282%2C1%2Ck%2B1%2C1%29%29\"$ +...+

. The statement is proven. \n" ); document.write( "

\n" );