SOLUTION: prove that (n 0) + (n 1) + (n 2) + ... + (n k) = 2^n is true using mathematical induction note that (n k) is a falling factorial

Algebra ->  Sequences-and-series -> SOLUTION: prove that (n 0) + (n 1) + (n 2) + ... + (n k) = 2^n is true using mathematical induction note that (n k) is a falling factorial      Log On


   

Question 1158359: prove that (n 0) + (n 1) + (n 2) + ... + (n k) = 2^n is true using mathematical induction
note that (n k) is a falling factorial
Found 2 solutions by Shin123, ikleyn:
Answer by Shin123(626) About Me  (Show Source):
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.
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.

Answer by ikleyn(52782) About Me  (Show Source):
You can put this solution on YOUR website!
.

            There is another way and another method to prove it,
            much more effective,  more easy and more straightforward  (and really nice (!) ). 


Use the binomial formula


    %281+%2B+x%29%5En = 1 + C%5Bn%5D%5E1%2Ax + C%5Bn%5D%5E2%2Ax%5E2 +C%5Bn%5D%5E3%2Ax%5E3 + C%5Bn%5D%5E4%2Ax%5E4 + . . . + C%5Bn%5D%5E%28n-1%29%2Ax%5E%28n-1%29 + x%5En.


Now plug in x= 1 into this formula.  You will get


    2%5En = 1 + C%5Bn%5D%5E1 + C%5Bn%5D%5E2 +C%5Bn%5D%5E3 + C%5Bn%5D%5E4 + . . . + C%5Bn%5D%5E%28n-1%29 + 1,


and the proof is completed.



Those who saw this proof at least once in their life, will never forget it . . .

---------------

See the lesson
    - Remarkable identities for Binomial Coefficients
in this site.

Also, you have this free of charge online textbook in ALGEBRA-II in this site
    - ALGEBRA-II - YOUR ONLINE TEXTBOOK.

The referred lesson is the part of this textbook under the topic
"Binomial expansion, binomial coefficients, Pascal's triangle".


Save the link to this textbook together with its description

Free of charge online textbook in ALGEBRA-II
https://www.algebra.com/algebra/homework/complex/ALGEBRA-II-YOUR-ONLINE-TEXTBOOK.lesson

into your archive and use when it is needed.