Binomials, Pascal's Triangle & Induction

Factorials and binomial coefficients

A factorial, written n!, is the product of all whole numbers from n down to 1: for instance 4! = 4 · 3 · 2 · 1 = 24. By convention 0! = 1, a definition that keeps later formulas tidy. Factorials count arrangements, which is exactly why they appear in expansion coefficients.

A binomial coefficient, written C(n, k) or “n choose k,” equals n! / (k!(n − k)!). It counts how many ways to choose k items from n, and it is exactly the number multiplying each term when you expand a binomial power. These coefficients are always whole numbers despite the factorials.

Compute a binomial coefficient:  C(5, 2) = "5 choose 2"

C(n, k) = n! / ( k! (n - k)! )

C(5, 2) = 5! / ( 2! * 3! )
        = 120 / ( 2 * 6 )
        = 120 / 12
        = 10

The binomial theorem and Pascal's triangle

The binomial theorem says (a + b)ⁿ expands as a sum of terms C(n, k) · a^(n−k) · b^k for k running from 0 to n. As you read left to right, the power of a drops by one each term while the power of b climbs by one; their exponents always add to n. The coefficients are the binomial coefficients above.

Pascal's triangle is a fast way to get those coefficients without computing factorials. Start each row with 1, end with 1, and make every interior entry the sum of the two numbers above it. Row n (counting from row 0) gives exactly the coefficients of (a + b)ⁿ.

Pascal's triangle (rows 0 to 4):

            1                <- row 0:  (a+b)^0
          1   1              <- row 1:  coeffs 1, 1
        1   2   1            <- row 2:  coeffs 1, 2, 1
      1   3   3   1          <- row 3:  coeffs 1, 3, 3, 1
    1   4   6   4   1        <- row 4:  coeffs 1, 4, 6, 4, 1

Each inside number = sum of the two just above it (e.g. 6 = 3 + 3).

Use row 3 to expand (a + b)^3:
  (a + b)^3 = 1*a^3 + 3*a^2*b + 3*a*b^2 + 1*b^3
            = a^3 + 3a^2 b + 3a b^2 + b^3

A first taste of induction

How do we know a formula like 1 + 2 + … + n = n(n + 1)/2 holds for every n, not just the ones we tested? Mathematical induction proves it. Think of dominoes: if the first one falls, and each fallen domino knocks over the next, then they all fall.

1. Base case: show the statement is true for the first value, usually n = 1.
2. Inductive hypothesis: assume the statement holds for some value n = k.
3. Inductive step: using that assumption, prove the statement then holds for n = k + 1. The base case plus this step together force it true for all n.

Prove:  1 + 2 + ... + n = n(n + 1)/2,  for all n >= 1.

Base case (n = 1):   left = 1.   right = 1(1+1)/2 = 1.   Equal. OK.

Assume true at n = k:   1 + 2 + ... + k = k(k + 1)/2.

Step to n = k + 1:   add (k + 1) to both sides:
  1 + 2 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)
                            = (k + 1)[ k/2 + 1 ]
                            = (k + 1)(k + 2)/2

This is exactly the formula with n replaced by k + 1.  Proof complete.