3
$\begingroup$

So i'm not sure at all how to prove things using a combinatorial proof. Where to do i start? What do i need to think about etc. For example how would i prove

$$\sum_{i=0}^n {n \choose i} 2^i = 3^n $$

  • 1
    Two approaches here: - Sums like this often lend themselves to induction. - If you stare hard at this, you may see a connection to the binomial theorem.2012-09-19
  • 1
    For this particular target, remember that $3=1+2$ and use the binomial theorem. But unless you restrict yourself to an extremely restricted class of problem, I don't think that very specific _general_ instructions for how to devise a proof can be given.2012-09-19
  • 0
    FYI, it's _combinatorial_, not _combinatorical_. @JohannesKloos: I wouldn't consider either of your approaches to be combinatorial. While they are valid methods of proof, it is often important to a student learning combinatorics to specifically learn how to give combinatorial (aka bijective) proofs.2012-09-19
  • 0
    @MichaelJoyce: True, I missed the "combinatorial" bit.2012-09-19
  • 1
    @MichaelJoyce: I would nuance the remark about learning combinatorics. I think it is OK to give an algebraic proof first if one easily spots one. Then looking closely to the proof, there is often a bijective proof hidden beneath the algebraic proof, as would be the case here when using the binomial theorem. Seeing how the two are related is more instructive than being forced to forgo the algebraic proof since "it must be bijective".2012-09-20

2 Answers 2