16 - The Binomial Theorem

!Screenshot 2023-10-15 at 11.40.35 PM.png
!Screenshot 2023-10-16 at 12.27.54 AM.png
!Screenshot 2023-10-16 at 12.02.58 PM.png

1

HW 16

Ben Finch

E 16.1
Proposition:

(\binom{n}{0}) = (\binom{n}{n}) = 1

Proof:
Let $n \in Z, n \geq 0$ .
By the definition of the binomial coefficient,

(\binom{n}{0}) = \frac{n!}{0! (n - 0)!} = \frac{n!}{n!} = 1

Additionally,

(\binom{n}{n}) = \frac{n!}{n! (n - n)!} = \frac{n!}{n!} = 1

Thus we have

(\binom{n}{0}) = (\binom{n}{n}) = 1

$◻$

Proposition:

(\binom{n}{1}) = (\binom{n}{n - 1}) = n

Proof:
Let $n \in Z, n \geq 0$ .
By the definition of the binomial coefficient and definition of factorial, we have:

(\binom{n}{1}) = \frac{n!}{1! (n - 1)!} = \frac{n \cdot (n - 1)!}{1! (n - 1)!} = \frac{n}{1} = n

Additionally:

(\binom{n}{n - 1}) = \frac{n!}{(n - 1)! (n - (n - 1))!} = \frac{n \cdot (n - 1)!}{1! (n - 1)!} = \frac{n}{1} = n

Thus we have:

(\binom{n}{1}) = (\binom{n}{n - 1}) = n

$◻$

E 16.2
Proposition:

(\binom{n}{k}) = (\binom{n}{n - k})

for any $n, k \in Z$ .

Proof.
Let $n, k \in Z$ . We have two cases:

Case 1. Suppose $n < 0$ or $k < 0$ or $n < k$ . Then by the definition of the binomial coefficient,

(\binom{n}{k}) = 0

Consider two subcases for $(\binom{n}{n - k})$

If $n < k$ , then $n - k$ will be negative thus by the definition of the binomial coefficient:

(\binom{n}{n - k}) = 0

If $k < n$ , then based on our assumption $k < 0$ so $n - k > n$ thus by the definition of the binomial coefficient:

(\binom{n}{n - k}) = 0

In both subcases $(\binom{n}{n - k})$ = 0. Thus if $n < 0$ or $k < 0$ or $n < k$ :

(\binom{n}{k}) = (\binom{n}{n - k}) = 0

Case 2. Suppose that $n \geq k \geq 0$ . Then by the definition of binomial coefficient:

(\binom{n}{k}) = \frac{n!}{k! (n - k)!}

and

(\binom{n}{n - k}) = \frac{n!}{(n - k)! (n - (n - k)!)} = \frac{n!}{k! (n - k)!}

Thus we have for $n \geq k \geq 0$ , $(\binom{n}{k}) = (\binom{n}{n - k})$ .

Hence in all cases we have $(\binom{n}{k}) = (\binom{n}{n - k})$ $◻$

E 16.3
Proposition.
Let $n, j, k \in Z$ .

(\binom{n}{j}) (\binom{n - j}{k}) = (\binom{n}{k}) (\binom{n - k}{k})

Proof.

Let $n, j, k \in Z$ . We have four cases to consider:

Case 1. Suppose $j < 0$ or $k < 0$ . Then by the definition of the binomial coefficient, both $(\binom{n}{j})$ and $(\binom{n - j}{k})$ are zero. Hence,

(\binom{n}{j}) (\binom{n - j}{k}) = 0 \cdot (\binom{n - j}{k}) = 0

As $(\binom{n}{k})$ and $(\binom{n - k}{n - j})$ are also zero in this case (as $k < 0$ ), we also have

(\binom{n}{k}) (\binom{n - k}{n - j}) = 0 \cdot (\binom{n - k}{n - j}) = 0

Therefore, if $j < 0$ or $k < 0$ , then

(\binom{n}{j}) (\binom{n - j}{k}) = (\binom{n}{k}) (\binom{n - k}{n - j})

Case 2. Suppose $j + k > n$ . In this case, $(\binom{n - j}{k})$ and $(\binom{n - k}{n - j})$ are zero by the definition of the binomial coefficient. Hence, both sides of the equation are zero. Hence in this case also,

(\binom{n}{j}) (\binom{n - j}{k}) = (\binom{n}{k}) (\binom{n - k}{n - j})

Case 3. Suppose $j \geq 0$ , $k \geq 0$ , and $j + k \leq n$ . By the definition of the binomial coefficient, we have

(\binom{n}{j}) = \frac{n!}{j! (n - j)!}

and

(\binom{n - j}{k}) = \frac{(n - j)!}{k! (n - j - k)!}

Multiplying these two fractions, we get

(\binom{n}{j}) (\binom{n - j}{k}) = \frac{n!}{j! k! (n - j - k)!}

On the other hand, we also have

(\binom{n}{k}) = \frac{n!}{k! (n - k)!}

and

(\binom{n - k}{n - j}) = \frac{(n - k)!}{(n - j)! (k - j)!}

Multiplying these two fractions, we get

(\binom{n}{k}) (\binom{n - k}{n - j}) = \frac{n!}{k! (n - j)! (k - j)!}

Thus

(\binom{n}{j}) (\binom{n - j}{k}) = (\binom{n}{k}) (\binom{n - k}{n - j})

Case 4. Suppose $j > n$ . In this case, $(\binom{n}{j})$ and $(\binom{n - k}{n - j})$ are zero by the definition of the binomial coefficient, and hence the equality holds as both sides of the equation are zero.

Hence, in all cases, we have $(\binom{n}{j}) (\binom{n - j}{k}) = (\binom{n}{k}) (\binom{n - k}{n - j})$ . $◻$

E 16.4
Proposition:
Prove that for any integer $n \geq 0$

\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}

Proof.
Let $n \in Z$ , $n \geq 0$
Fix $x = y = 1$ and plug into the binomial theorem. We get:

(1 + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) 1^{n - k} 1^{k}

Simplifying, we get:

2^{n} = \sum_{k = 0}^{n} (\binom{n}{k})

Hence, we've proven the proposition. $◻$

E 16.5
Proposition:
For any integer $n \geq 0$ ,

\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = 0

Proof.
Let $n \in Z$ and $n \geq 0$ .
Fix $a = 1$ and $b = - 1$ . Then by the binomial theorem:

(1 - 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) \cdot 1^{n - k} \cdot (- 1)^{k} = \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k})

And since $1 - 1 = 0$ , it follows that:

\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = 0

So the proposition is proven. $◻$

E 16.6
Fix $n = 8$ , $k = 3$ , $a = 2 x$ , $b = 3 y$ .

Coefficient = $(\binom{8}{3}) * 2^{8 - 3} * 3^{3}$

$(\binom{8}{3}) = \frac{8!}{3! (8 - 3)!} = 56$
$2^{8 - 3} = 2^{5} = 32$
$3^{3} = 27$

So, Coefficient = $56 * 32 * 27$

Therefore, the coefficient is $56 * 32 * 27 = 43008$ .

E 16.7
Proposition:
Let $n, k \in Z$ . Prove that

k (\binom{n}{k}) = n (\binom{n - 1}{k - 1})

Proof.
Let $n, k \in Z$ . We have two cases.

Case 1: $n \leq 0$ or $k \leq 0$ or $k > n$ :
Then by definition of the binomial coefficient, both sides of the equation will be 0.

Case 2: $0 \leq k \leq n$ :
By definition of the binomial coefficient, we have:

k (\binom{n}{k}) = k \frac{n!}{k! (n - k)!} = \frac{n!}{(k - 1)! (n - k)!}

We also have

n (\binom{n - 1}{k - 1}) = n \frac{(n - 1)!}{(k - 1)! ((n - 1) - (k - 1))!} = \frac{n!}{(k - 1)! (n - k)!}

Thus we have

k (\binom{n}{k}) = n (\binom{n - 1}{k - 1})

. $◻$

E 16.8
a)
0)

(\binom{0}{0}) = \frac{0!}{0! (0 - 0)!} = 1

(\binom{2}{1}) = \frac{2!}{1! (2 - 1)!} = 2

(\binom{4}{2}) = \frac{4!}{2! (4 - 2)!} = 6

(\binom{6}{3}) = \frac{6!}{3! (6 - 3)!} = 20

(\binom{8}{4}) = \frac{8!}{4! (8 - 4)!} = 70

b)
Proof.
Let $n \in N$ . We aim to prove that $(\binom{2 n}{n})$ is an even integer.

By Theorem 16.4:

(\binom{2 n}{n}) = (\binom{2 n - 1}{n - 1}) + (\binom{2 n - 1}{n})

By exercise 16.2:

(\binom{2 n - 1}{n}) = (\binom{2 n - 1}{n - 1}) $ $ . T h e r e f o r e, w e c a n r e w r i t e t h e e q u a t i o n a s :

\begin{align*}
\binom{2n}{n} &= \binom{2n-1}{n-1} + \binom{2n-1}{n-1}\
&= 2\binom{2n-1}{n-1}
\end

S i n c e $ (\binom{2 n - 1}{n - 1}) $ i s a n i n t e g e r, $ (\binom{2 n}{n}) $ i s e v e n . $ ◻ $ * * E 16.9 * * a) * P r o o f . * L e t $ n, k \in Z $, $ n > 8 $ . * * B a s e C a s e s * * F i x $ n = 9 $ . 1. $ k = 0, (\binom{9}{0}) = 1 < 2^{9 - 2} = 128 $ 2. $ k = 1, (\binom{9}{1}) = 9 < 2^{9 - 2} = 128 $ 3. $ k = 2, (\binom{9}{2}) = 36 < 2^{9 - 2} = 128 $ 4. $ k = 3, (\binom{9}{3}) = 84 < 2^{9 - 2} = 128 $ 5. $ k = 4, (\binom{9}{4}) = 126 < 2^{9 - 2} = 128 $ 6. $ k = 5, (\binom{9}{5}) = 126 < 2^{9 - 2} = 128 $ 7. $ k = 6, (\binom{9}{6}) = 84 < 2^{9 - 2} = 128 $ 8. $ k = 7, (\binom{9}{7}) = 36 < 2^{9 - 2} = 128 $ 9. $ k = 8, (\binom{9}{8}) = 9 < 2^{9 - 2} = 128 $ 10. $ k = 9, (\binom{9}{9}) = 1 < 2^{9 - 2} = 128 $ * * I n d u c t i v e S t e p * * A s s u m e $ (\binom{n}{k}) < 2^{n - 2} $ . W e a i m t o p r o v e $ (\binom{n + 1}{j}) < 2^{n - 1} $ . B y t h e o r e m 16.4 :

\begin{align*}
\binom{n+1}{j} &= \binom{n}{j-1} + \binom{n}{j}
\end

b y t h e i n d u c t i v e s t e p :

\begin{align*}
\binom{n}{j-1} + \binom{n}{j} &< 2^{n-2}+2^{n-2}\
&= 2^{n-1}
\end

T h u s w e h a v e b y m a t h e m a t i c a l i n d u c t i o n $ (\binom{n + 1}{j}) < 2^{n - 1} $ . $ ◻ $ b) L e t $ n, k \in Z $ . L e t $ n > 7 $ . T h e r e a r e t w o c a s e s : * C a s e 1 : * I f $ k < 0 $ o r $ k > n $, t h e n b y d e f i n i t i o n o f t h e b i n o m i a l e x p a n s i o n, $ (\binom{n}{k}) = 0 < (n - 3)! $ * C a s e 2 * $ k > 0 $ a n d $ k < n $ . W e w o r k b y i n d u c t i o n . * * B a s e C a s e s : * * F i x $ n = 8 $ 1. $ k = 0 $ : $ (\binom{8}{0}) = 1 < 5! = 120 $ 2. $ k = 1 $ : $ (\binom{8}{1}) = 8 < 5! = 120 $ 3. $ k = 2 $ : $ (\binom{8}{2}) = 28 < 5! = 120 $ 4. $ k = 3 $ : $ (\binom{8}{3}) = 56 < 5! = 120 $ 5. $ k = 4 $ : $ (\binom{8}{4}) = 70 < 5! = 120 $ 6. $ k = 5 $ : $ (\binom{8}{5}) = 56 < 5! = 120 $ 7. $ k = 6 $ : $ (\binom{8}{6}) = 28 < 5! = 120 $ 8. $ k = 7 $ : $ (\binom{8}{7}) = 8 < 5! = 120 $ 9. $ k = 8 $ : $ (\binom{8}{8}) = 1 < 5! = 120 $ * * I n d u c t i v e S t e p * * L e t $ z \in N $, $ z \geq 8 $ A s s u m e $ P (z) $ i s t r u e, t h u s $ (\binom{z}{k}) < (z - 3)! $ W e a i m t o p r o v e $ P (z + 1) : (\binom{z + 1}{k}) < (z - 2)! $

\begin{align*}
\binom{z}{k} + \binom{z}{k -1} &= \binom{z+1}{k}\
&= 2((z -3)!)\
&< (z-2)(z-3)!\
&= (z-2)!
\end

T h u s b y m a t h e m a t i c a l i n d u c t i o n, $ P (n) $ i s t r u e f o r a l l $ n \in Z $ . $ ◻ $