1. The problem statement, all variables and given/known data Hi everyone, In my assignment I've been asked to show that 2^n = Ʃ(nCi) i from 0 -> n ie: 2^n = nC0 + nC1 + .... + nCn and I have to do this by induction and then also by a combinatorial argument. 2. Relevant equations Right now I'm just working on the induction part. BASE CASE: n = 0 ASSUME: 2^n = ƩnCi PROVE: 2^(n+1) = Ʃ(n+1)Ci 3. The attempt at a solution I've shown the base case, 2^0 = 1 and 0C0 = 1 Then I assumed that 2^k = ƩkCi (i from 0->k) Now I've expanded (n+1)Ci = (n+1)C0 + (n+1)C1 +... + (n+1)C(n+1) I know there must be a way to do this simply using algebra but I'm totally stumped. I tried saying that 2^k+1 = 2(2^k) which we know from the assumption to be 2*(ƩkCi) but that doesn't seem to help me out. If anyone could give me a hint which direction to go with the algebra I would really appreciate it!