Algebra/Proofs

An Algebraic Proof is a proof of a Theorem (or Lemma or Corollary) that relies highly on symbolic manipulation of equations to go from the assumption(s) to the conclusion(s). An algebraic proof may be contrasted with a combinatorial proof, which involves more discussion of the objects themselves, rather than the symbols representing them.

Example

Theorem: ${n \choose k}+{n \choose k+1}={n+1 \choose k+1}$.

Proof:

 $LHS={\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k+1)!(n-k-1)!}}$
 $={\frac {n!(k+1)}{(k+1)!(n-k)!}}+{\frac {n!(n-k)}{(k+1)!(n-k)!}}$
 $={\frac {(k+1+n-k)n!}{(k+1)!(n-k)!}}={\frac {(n+1)n!}{(k+1)!(n-k)!}}=RHS$