1. The problem statement, all variables and given/known data Prove that ∑nj=0 n C r = 2n 2. Relevant equations Defn. of a combination. Defn. of mathematical induction. 3. The attempt at a solution The formula is true for n=1 2=∑j=01 n C r = 1 C 0 +1 C 1 =1 + 1 = 2 Now assume that for some k∈ℕ and 0≤ j ≤ k we have 2k = ∑kj=0 (k C j) Then (2)(2k)=2k+1= (2)∑kj=0 (k C j) LHS= ∑kj=0 (k C j) + ∑kj=0 (k C j) LHS= ∑kj=0 (k C j) + ∑k+1j=0 (k C j-1) LHS= ∑kj=0 (k C j) + ∑kj=0 (k C j-1) + (k+1 C k+1) LHS= ∑kj=0 [ (k C j) + (k Cj-1) ] +(k+1 C k+1) LHS= ∑kj=0 (k+1 C j) + (k+1 C k+1) LHS= ∑k+1j=0 (k+1 C j) Does everything check? In addition, how was this formula discovered? How do people even find these things? Thanks again for the help guys and gals.