According to Binomial Theorem $$ (x+y)^n=\sum_{k=0}^{n}(^{n}_k) x^ky^{n-k} $$ The result is true for n=1, since $$ (x+y)^1=(^{1}_0)y^{1}+(^{1}_1)x $$ Let the result be true for n=m, that is $$ (x+y)^m=\sum_{k=0}^{m}(^{m}_k) x^ky^{m-k} $$ we need to prove that the result is also true for n=m+1, that is $$ (x+y)^{m+1}=\sum_{k=0}^{m+1}(^{m+1}_k) x^ky^{{m+1}-k} $$ By assumption $$ (x+y)^m=\sum_{k=0}^{m}(^{m}_k) x^ky^{m-k} $$ multiplying both sides by x+y $$ (x+y)^{m+1}=(x+y)\sum_{k=0}^{m}(^{m}_k) x^ky^{m-k} $$ $$ =\sum_{k=0}^{m}(^{m}_k) x^ky^{m+1-k}+\sum_{k=0}^{m}(^{m}_k) x^{k+1}y^{m-k} $$ $$ =(^{m}_0) y^{m+1}+\sum_{k=1}^{m}(^{m}_k) x^{k}y^{m+1-k}+\sum_{k=0}^{m-1}(^{m}_k) x^{k+1}y^{m-k}+(^{m}_m) x^{k+1} $$ $$ =(^{m}_0) y^{m+1}+[(^{m}_1)+(^{m}_0)]xy^m+[(^{m}_2)+(^{m}_1)]x^2y^{m-1}+...+[(^{m}_m)+(^{m}_{m-1})]x^my+(^{m}_m) x^{k+1} $$ $$ =(^{m+1}_0) y^{m+1}+[(^{m+1}_1)]xy^m+[(^{m+1}_2)]x^2y^{m-1}+...+[(^{m+1}_m)]x^my+(^{m+1}_{m+1}) x^{m+1}y $$ $$ =\sum_{k=0}^{n}(^{m+1}_k) x^ky^{m+1-k} $$
Hence the result is also true for n=k+1.
The following results were used in the proof: $$ (^{m}_0)= (^{m+1}_0), (^{m}_m)= (^{m+1}_{m+1}), (^{m}_r)+(^{m}_{r-1})=(^{m+1}_r)$$
I've been working through proof by induction and I'm stuck on this question. Can somebody provide some help to prove it by applying the proof above?
Prove: $$ 2^{n-1}=\sum_{k=0}^{n-1}(^{n-1}_k)=\sum_{k=1}^{n}(^{n-1}_{k-1})\text{ for } n> 0$$
I don't know how to prove it using the guide above.....
expand $ (1+1)^{n-1}$
using the binomial formula . The result is immediate , you don't need induction .