Summary Linear and Abstract Algebra Study Guide

lOMoARcPSD|15589855




1. MATHEMATICAL INDUCTION

EXAMPLE 1: Prove that
n(n + 1)
1 + 2 + 3 + ... + n = (1.1)
2
for any integer n ≥ 1.
Proof:
STEP 1: For n=1 (1.1) is true, since
1(1 + 1)
1= .
2
STEP 2: Suppose (1.1) is true for some n = k ≥ 1, that is
k(k + 1)
1 + 2 + 3 + ... + k = .
2
STEP 3: Prove that (1.1) is true for n = k + 1, that is

? (k + 1)(k + 2)
1 + 2 + 3 + . . . + k + (k + 1) = .
2
We have
 
ST.2 k(k + 1) k (k + 1)(k + 2)
1 + 2 + 3 + . . . + k + (k + 1) = + (k + 1) = (k + 1) +1 = .
2 2 2




EXAMPLE 2: Prove that

1 + 3 + 5 + . . . + (2n − 1) = n2 (1.2)

for any integer n ≥ 1.
Proof:
STEP 1: For n=1 (1.2) is true, since 1 = 12 .
STEP 2: Suppose (1.2) is true for some n = k ≥ 1, that is

1 + 3 + 5 + . . . + (2k − 1) = k 2 .

STEP 3: Prove that (1.2) is true for n = k + 1, that is
?
1 + 3 + 5 + . . . + (2k − 1) + (2k + 1) = (k + 1)2 .
ST.2
We have: 1 + 3 + 5 + . . . + (2k − 1) + (2k + 1) = k 2 + (2k + 1) = (k + 1)2 . 

1

Downloaded by Riley Singh ()

, lOMoARcPSD|15589855




EXAMPLE 3: Prove that
n! ≤ nn (1.3)
for any integer n ≥ 1.
Proof:
STEP 1: For n=1 (1.3) is true, since 1! = 11 .
STEP 2: Suppose (1.3) is true for some n = k ≥ 1, that is k! ≤ k k .
?
STEP 3: Prove that (1.3) is true for n = k + 1, that is (k + 1)! ≤ (k + 1)k+1 . We have
ST.2
(k + 1)! = k! · (k + 1) ≤ k k · (k + 1) < (k + 1)k · (k + 1) = (k + 1)k+1 . 



EXAMPLE 4: Prove that
8 | 32n − 1 (1.4)
for any integer n ≥ 0.
Proof:
STEP 1: For n=0 (1.4) is true, since 8 | 30 − 1.
STEP 2: Suppose (1.4) is true for some n = k ≥ 0, that is 8 | 32k − 1.
STEP 3: Prove that (1.4) is true for n = k + 1, that is 8 | 32(k+1) − 1. We have
32(k+1) − 1 = 32k+2 − 1 = 32k · 9 − 1 = 32k (8 + 1) − 1 = |32k{z· 8} + |32k{z− 1} . 
div. by 8 St. 2
div. by 8
EXAMPLE 5: Prove that
7 | n7 − n (1.5)
for any integer n ≥ 1.
Proof:
STEP 1: For n=1 (1.5) is true, since 7 | 17 − 1.
STEP 2: Suppose (1.5) is true for some n = k ≥ 1, that is
7 | k 7 − k.
STEP 3: Prove that (1.5) is true for n = k + 1, that is 7 | (k + 1)7 − (k + 1). We have
(k + 1)7 − (k + 1) = k 7 + 7k 6 + 21k 5 + 35k 4 + 35k 3 + 21k 2 + 7k + 1 − k − 1
7
= k
| {z− k} + |7k 6 + 21k 5 + 35k 4{z
+ 35k 3 + 21k 2 + 7k} . 
St. 2 div. by 7
div. by 7


2

Downloaded by Riley Singh ()

, lOMoARcPSD|15589855




2. THE BINOMIAL THEOREM


DEFINITION:
Let n and k be some integers with 0 ≤ k ≤ n. Then
 
n n!
=
k k!(n − k)!

is called a binomial coefficient.


PROPERTIES:
   
n n
1. = = 1.
0 n

Proof: We have
 
n n! n!
= = = 1,
0 0!(n − 0)! 1 · n!

 
n n! n! n!
= = = = 1. 
n n!(n − n)! n! · 0! n! · 1


   
n n
2. = = n.
1 n−1

Proof: We have
 
n n! (n − 1)! · n
= = = n,
1 1!(n − 1)! 1! · (n − 1)!

 
n n! n! (n − 1)! · n
= = = = n. 
n−1 (n − 1)![n − (n − 1)]! (n − 1)! · 1! (n − 1)! · 1!


   
n n
3. = .
k n−k

Proof: We have
   
n n! n! n! n
= = = = .
k k!(n − k)! (n − k)!k! (n − k)![n − (n − k)]! n−k


3

Downloaded by Riley Singh ()

, lOMoARcPSD|15589855




     
n n n+1
4. + = .
k k−1 k

Proof: We have
   
n n n! n!
+ = +
k k−1 k!(n − k)! (k − 1)!(n − k + 1)!
n!(n − k + 1) n!k
= +
k!(n − k)!(n − k + 1) (k − 1)!k(n − k + 1)!
n!(n − k + 1) n!k
= +
k!(n − k + 1)! k!(n − k + 1)!
n!(n − k + 1) + n!k
=
k!(n − k + 1)!
n!n − n!k + n! + n!k
=
k!(n − k + 1)!
n!n + n!
=
k!(n − k + 1)!
 
n!(n + 1) (n + 1)! (n + 1)! n+1
= = = = .
k!(n − k + 1)! k!(n − k + 1)! k!(n + 1 − k)! k



PROBLEM:
For all integers n and k with 1 ≤ k ≤ n we have
       
n n n n+2
+2 + = .
k−1 k k+1 k+1


Proof: By property 4 we have
             
n n n n n n n
+2 + = + + +
k−1 k k+1 k−1 k k k+1
     
n+1 n+1 n+2
= + = .
k k+1 k+1



THEOREM (The Binomial Theorem):
Let a and b be any real numbers and let n be any nonnegative integer. Then
       
n n n n−1 n n−2 2 n 2 n−2 n
(a + b) = a + a b+ a b + ... + ab + abn−1 + bn .
1 2 n−2 n−1


4

Downloaded by Riley Singh ()