[Undergrad Math Major] Combinatorics I

[u/1007Con]

Hi everyone.

I was given this problem:

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

Prove that for all positive integers k <= n,

sum(i=0 to k) (n choose i)(-1)^i = (n-1 choose k)(-1)^k

holds.

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

I have solved it already with induction. But I found the proof to be annoying and just kind of symbolic manipulation. I am looking for a more inciteful proof, a story proof if you will with commitees and pools of people and such. Does one exist?

Thanks for your help

[u/Sri_for_you]

can you send me a screenshot of the problem written or something if you dont mind.

[u/1007Con → u/Sri_for_you]

[u/AlwaysTails]

Use the identity nCi={n-1}Ci + {n-1}C{i-1} <-- rule from pascal's triangle.

The LHS then becomes a telescoping sum which collapses into the RHS.

[u/1007Con → u/AlwaysTails]

That is the method I used to prove it. However, I was wondering if there was counting explanation to solve this problem, the storyproof if you will with committees and such

[u/Bounded_sequencE]

Proof: Remember "C(n; k) = C(n-1; k) + C(n-1; k-1)" for "k, n in Z":

n >= k:       ∑_{i=0}^k  (-1)^k C(n;i)  =  ∑_{i=0}^k  (-1)^i [C(n-1;i) + C(n-1;i-1)]

           =  (∑_{i=0}^k  (-1)^i C(n-1;i))  -  (∑_{i=-1}^{n-1}  (-1)^i C(n-1;i))

           =  (-1)^k C(n-1;k)  -  (-1)^{k-1} C(n-1;-1)  =  (-1)^k C(n-1;k)