so I'm currently in a combinatorics course, and I am struggling immensely with proofs, especially with combinatorial identities. I have the following identity I am trying to prove:
$$\sum_{k = 0}^{m} (-1)^k {n \choose k} = (-1)^m {n-1 \choose m} $$
I tried to prove this algebraically by expanding the LHS and the RHS but it ended up being messy, so I gave up on that. In terms of a combinatorial proof, I have no clue what this identity is trying to say.
Any guidance towards both a combinatorial proof and an algebraic proof would be appreciated!
if $k\ge 1, {n\choose k} = {n-1\choose k-1} + {n-1\choose k}.$ If you need to prove this then do so, but it may be that you already have. It drives Pascal's triangle.
Making that change above
${n\choose 0} + \sum_\limits{k=1}^{m} (-1)^k ({n-1\choose k-1} + {n-1\choose k})$
Expanding that out, we will get something that telescopes.
${n\choose 0} - {n\choose 0} - {n\choose 1} + {n\choose 1} + {n\choose 2} - {n\choose 2} - {n\choose 3} + \cdots $
And all the terms except the last one will cancel each other out.