Associate Degree 2024 – 2025 First Semester

CCMA4002 Linear Algebra

Exercise 1

1. Prove that 1  3  5   (2n 1)  n 2 for all positive integers n.

Solution:

(1) For n = 1,
L.H.S. = 1,
R.H.S. = (1)2  1 = L.H.S.
 The statement is true for n = 1.

(2) Assume the statement is true for some integer k  1, i.e., 1  3  5   (2k 1)  k 2

For n = k + 1,
1  3  5   [2(k  1)  1]  1  3  5   (2k  1)
 1 3  5   (2k  1)  (2k  1)
 k 2  (2k  1)
 (k  1) 2

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

1
 1 1 1 1 n
2. Prove that      for all positive integers n.
1 2 2  3 3  4 n(n  1) n  1

Solution:

(1) For n = 1,
1 1
L.H.S. =  ,
1 2 2
1 1
R.H.S. =  = L.H.S.
11 2
 The statement is true for n = 1.

1 1 1 1 k
(2) Assume the statement is true for some integer k  1, i.e.,     
1 2 2  3 3  4 k(k  1) k  1

For n = k + 1,
1 1 1 1 1 k 1
      
1 2 2  3 3  4 k(k  1) (k  1)[(k  1)  1] k  1 (k  1)(k  2)
k(k  2)  1

(k  1)(k  2)
k2  2 k1

(k  1)(k  2)
(k  1) 2

(k  1)(k  2)
k 1

k2
k 1

(k  1)  1

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

2
 1
3. Prove that 11  2  7  3 13   n  (6n  5)  n(n  1)(4n  3) for all positive integers n.
2

Solution:

(1) For n = 1,
L.H.S. = 1 1  1 ,
1 1
R.H.S. = (1)[(1)  1][4(1)  3]  (1)(2)(1)  1 = L.H.S.
2 2
 The statement is true for n = 1.

(2) Assume the statement is true for some integer k  1,

1
i.e., 11  2  7  3 13   k  (6k  5)  k(k  1)(4k  3)
2

For n = k + 1,

1
11  2  7  3  13   k  (6k  5)  (k  1)  [6(k  1)  5]  k(k  1)(4k  3)  (k  1)  [6(k  1)  5]
2
1
 k(k  1)(4k  3)  (k  1)  (6k  1)
2
1
 (k  1)[k(4k  3)  2  (6k  1)]
2
1
 (k  1)(4k 2  3k  12k  2)
2
1
 (k  1)(4k 2  9k  2)
2
1
 (k  1)(k  2)(4 k  1)
2
1
 (k  1)[(k  1) 1][4(k  1)  3]
2

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

3
 n(n  1)(2 n  1)
4. (a) Prove that 12  22  32   n2  for all positive integers n.
6
(b) Hence find the values of
(i) 12  22  32   752 ,
(ii) 202  212  222   502 .

Solution:

(a) (1) For n = 1,

L.H.S. = 12  1 ,
1(1  1)[2(1)  1] 6
R.H.S. =   1 = L.H.S.
6 6
 The statement is true for n = 1.

k(k  1)(2k  1)
(2) Assume the statement is true for some integer k  1, i.e., 12  22  32   k2 
6

For n = k + 1,
k(k  1)(2k  1)
12  22  32   k 2  (k  1) 2   (k  1) 2
6
k(k  1)(2k  1)  6(k  1) 2

6
(k  1)[k(2k  1)  6(k  1)]

6
(k  1)(2 k  k  6 k  6)
2

6
(k  1)(2 k  7 k  6)
2

6
(k  1)(k  2)(2 k  3)

6
(k  1)[(k  1)  1][2(k  1)  1]

6

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

75(75  1)[2(75)  1] 75(76)(151)

(b) (i) 12  22  32   752    143450
6 6

(ii) 202  212  222   502  (12  22  32   502 )  (12  22  32   192 )

50(50  1)[2(50)  1] 19(19  1)[2(19)  1]
 
6 6
 40455
4
 n 2 (n  1) 2
5. (a) Prove, by mathematical induction, that 13  23  33   n3  for all positive integers n.
4
(b) Hence, evaluate
(i) 13  33  53   1013 ,
(ii) the sum of the cubes of all the numbers between 50 and 100 which are divisible by 3,
i.e., 513  543  573   993 .

Solution:

(a) (1) For n = 1,

L.H.S. = 13  1 ,
12 (1  1) 2 4
R.H.S. =   1 = L.H.S.
4 4
 The statement is true for n = 1.

k 2 (k  1) 2
(2) Assume the statement is true for some integer k  1, i.e., 13  23  33   k3 
4

For n = k + 1,
k 2 (k  1) 2
13  23  33  k 3  (k  1)3   (k  1)3
4
k (k  1) 2  4(k  1)3
2

4
(k  1) [k  4(k  1)]
2 2

4
(k  1) (k  4k  4)
2 2

4
(k  1) (k  2) 2
2

4
(k  1) 2 [(k  1)  1]2

4

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

5
5. (b) (i) 13  33  53   1013  13  23  33   1013  (23  43  63   1003 )
1012 (101  1) 2
  23 (13  23  33   503 )
4
2
101 (102) 2  502 (50  1) 2 
  23  
4  4 
1012 (102) 2
  2(50) 2 (51) 2
4
 26532801  13005000
 13527801

(ii) 513  543  573   993  33 (173  183  193   333 )

 27[(13  23  33   333 )  (13  23  33   163 )]
 332 (33  1)2 162 (16  1)2 
 27   
 4 4 
 33 (34) 16 (17) 
2 2 2 2
 27   
 4 4 
 7998075

6
 1
6. Prove that 14  2 4  3 4    n 4  n (n  1)(6n 3  9n 2  n  1) for all positive integers n.
30

Solution:

(1) For n = 1,
L.H.S. = 14 = 1
1 1
R.H.S. = (1)(1  1)[6(1) 3  9(1) 2  (1)  1] = (1)(2)[6  9  1  1] = 1 = L.H.S.
30 30
 The statement is true for n = 1.

(2) Assume the statement is true for some integer k  1,

1
i.e., 14  2 4  3 4    k 4  k (k  1)(6k 3  9k 2  k  1)
30

For n = k + 1,

1
14  24  34   k 4  (k  1) 4  k(k  1)(6k 3  9k 2  k  1)  (k  1) 4
30
1
 (k  1)[k(6k 3  9k 2  k  1)  30(k  1) 3 ]
30
1
 (k  1)[6k 4  9k 3  k 2  k  30(k 3  3k 2  3k  1)]
30
1
 (k  1)(6k 4  9k 3  k 2  k  30k 3  90k 2  90k  30)
30
1
 (k  1)(6k 4  39k 3  91k 2  89k  30)
30
1
 (k  1)(k  2)(6k 3  27k 2  37k  15)
30
1
 (k  1)(k  2)[(6k 3  18k 2  18k  6)  (9k 2  18k  9)  (k  1)  1]
30
1
 (k  1)(k  2)[6(k 3  3k 2  3k  1)  9(k 2  2k  1)  (k  1)  1]
30
1
 (k  1)(k  2)[6(k  1)3  9(k  1) 2  (k  1)  1]
30

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

7
7. Prove that 4n 3  5n is divisible by 3 for all positive integers n.

Solution:

Let f(n) = 4n 3  5n

(1) For n = 1,
f(1) = 4(1)3  5(1)  9  3  3 which is divisible by 3.
 The statement is true for n = 1.

(2) Assume the statement is true for some integer k  1, i.e., f(k) is divisible by 3.
 There exists an integer t such that f(k) = 4k3  5k  3t

For n = k + 1,

f (k  1)  4(k  1)3  5(k  1)

 4(k 3  3k 2  3k  1)  5 k  5
 4k 3  12k 2  12k  4  5 k  5
 (4k 3  5k)  12k 2  12k  9
 3t  3(4k 2  4k  3)
 3(t  4k 2  4k  3)

As t and k are integers, so t  4k 2  4k  3 is also an integer.

 f(k + 1) is divisible by 3.

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

8
8. Prove that 6 n 1  5(n  1)  1 is divisible by 25 for all positive integers n.

Solution:

Let f(n) = 6 n 1  5(n  1)  1

(1) For n = 1,
f(1) = 61+1 – 5(1 + 1) – 1 = 36 – 10 – 1 = 25 which is divisible by 25.
 The statement is true for n = 1.

(2) Assume the statement is true for some integer k  1, i.e., f(k) is divisible by 25.
 There exists an integer t such that f(k) = 6 k+1 – 5(k + 1) – 1 = 25t

For n = k + 1,

f(k + 1) = 6(k+1)+1 – 5[(k + 1) +1] – 1

= 6k+2 – 5(k + 2) – 1
= 6 [6k+1 – 5(k + 1) – 1] + 30(k + 1) + 6 – 5(k + 2) – 1
= 6(25t) + 30k + 30 + 6 – 5k – 10 – 1
= 6(25t) + 25k + 25
= 25(6t + k + 1)

As t and k are integers, so 6t + k + 1 is also an integer.

 f(k + 1) is divisible by 25.

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

9
9. Prove that 34n  24n 2 is divisible by 5 for all positive integers n.

Solution:

Let f(n) = 34n  24n 2

(1) For n = 1,
f(1) = 34(1)  24(1)2  34  26  145  5  29 which is divisible by 5.
 The statement is true for n = 1.

(2) Assume the statement is true for some integer k  1, i.e., f(k) is divisible by 5.
 There exists an integer t such that f(k) = 34k  24k 2  5t

For n = k + 1,

f (k  1)  34(k 1)  24(k 1) 2

 34k  4  24k  6
 34 (34k )  24 (24k  2 )
 81(34k )  16(24k  2 )
 16(34k  24k  2 )  65(34k )
 16(5t)  5[13(34k )]
 5[16 t  13(34k )]

As t and k are integers, so 16t  13(34k ) is also an integer.

 f(k + 1) is divisible by 5.

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

10
 1 1 1 2n
10. Prove that 1      for all positive integers n.
2 3 n n 1

Solution:

(1) For n = 1,
L.H.S. = 1
2(1)
R.H.S. =  1  L.H.S.
(1)  1
 The statement is true for n = 1.

1 1 1 2k
(2) Assume the statement is true for some integer k  1, i.e., 1     
2 3 k k 1

For n = k + 1,

1 1 1 1 2k 1
1      
2 3 k k 1 k 1 k 1
2k  1

k 1
2k  1 2(k  1) 2(k  1)
  
k 1 k2 k2
(2k  1)(k  2)  2(k  1) 2 2(k  1)
 
(k  1)(k  2) k2
(2k 2  4k  k  2)  2(k 2  2k  1) 2(k  1)
 
(k  1)(k  2) k2
2k 2  5k  2  2k 2  4k  2 2(k  1)
 
(k  1)(k  2) k2
k 2(k  1)
 
(k  1)(k  2) k2
2(k  1) k
 ( 0 )
k2 (k  1)(k  2)
2(k  1)

(k  1)  1

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

11
 1 1 1 1
11. Prove that     for all positive integers n.
n 1 n  2 nn 2

Solution:

(1) For n = 1,
1
L.H.S. =
2
1
R.H.S. =  L.H.S.
2
 The statement is true for n = 1.

1 1 1 1
(2) Assume the statement is true for some integer k  1, i.e.,    
k 1 k  2 2k 2

For n = k + 1,

1 1 1 1 1
   
(k  1)  1 (k  1)  2 (k  1)  (k  1) (k  1)  k (k  1)  (k  1)
1 1 1 1 1
     
k 2 k 3 2k 2k  1 2k  2
1 1 1 1 1 1 1
       
k 1 k  2 k  3 2k 2k  1 2k  2 k  1
1 1 1 1
   
2 2k  1 2k  2 k  1
1 2(k  1)  (2k  1)  2(2k  1)
 
2 2(2k  1)(k  1)
1 2k  2  2k  1  4k  2
 
2 2(2k  1)(k  1)
1 1
 
2 2(2k  1)(k  1)
1 1
> (∵ >0)
2 2(2k  1)(k  1)

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

12
12. Prove that 2 n (1  2 n 1 )  3n 1 for all positive integers n.

Solution:

(1) For n = 1,
L.H.S. = 21 (1  211 ) = 10  9 = 311 = R.H.S.
 The statement is true for n = 1.

(2) Assume the statement is true for some integer k  1, i.e., 2 k (1  2 k 1 )  3k 1

For n = k + 1,

2k 1[1  2(k 1)1 ]  2k 1 (1  2k 2 )

 2k 1 (1  2  2k 1 )
 2k 1 (1  2k 1  2k 1 )
 2  2k (1  2k 1 )  22k  2
 2  3k 1  22k  2
 3  3k 1  22(k 1)  3k 1
 3k  2  (22 )(k 1)  3k 1
 3k  2  (4k 1  3k 1 )
 3k 2 (∵ 4k 1  3k 1 for k  1)
 3(k 1)1

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

13
13. Prove that 2 n  n 3 for all positive integers n  10.

Solution:

(1) For n = 10, 210 = 1024 > 1000 = 103

 The statement is true for n = 10.

(2) Assume the statement is true for some integer k  10. i.e., 2 k  k 3

For n = k + 1,

2k 1  2(2k )
 2(k 3 )
 k3  k  k 2
 k3  10k 2 ( k  10)
 k  3k  7k  k
3 2

 k3  3k 2  70k ( k  10)
 k  3k  3k  67k
3 2

 k3  3k 2  3k  1 ( k  10)
 (k  1)3

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n  10.

14
14. A sequence of real numbers is defined as follows:
x1  1 , x 2  2 , x n 1  x n  x n 1 for n = 2, 3, 4, …
n
7
Prove, by induction, that x n    for all positive integers n.
4
Solution:

1
7
(1) x1  1     1.75
4
2
7
x 2  2     3.0625
4
 The statement is true for n = 1 and n = 2.

(2) Assume the statement is true for some integers k – 1 and k, where k  2,
k 1 k
7 7
i.e., x k 1    and x k   
4 4

For n = k + 1,
x k 1  x k  x k 1
k k 1
7 7
    
4 4
k 1
7 7 
    1
4 4 
k 1
 11   7 
   
 4  4 
k 1
7
 2.75  
4
k 1
7
 3.0625  
4
2 k 1
7 7
   
4 4
2  k 1
7
 
4
k 1
7
 
4

 The statement is true for n = k + 1.

By the principle of mathematical induction, the statement is true for all positive integers n.
15
15. Prove that f(n) = 52n+1 – 32n+1 – 2 is divisible by 30 for all positive even integers n.

Solution:

(1) f(2) = 52(2)+1 – 32(2)+1 – 2 = 55 – 35 – 2 = 2880 = 30  96

 f(2) is divisible by 30.
 The statement is true for n = 2.

(2) Assume the statement is true for some integer k  2, i.e., f(k) is divisible by 30.
 There exists an integer t such that f(k) = 52k+1 – 32k+1 – 2 = 30t

For n = k + 2,

f(k + 2) = 52(k+2)+1 – 32(k+2)+1 – 2

= 52k+5 – 32k+5 – 2
= (52k+1 – 32k+1 – 2) + 52k+5 – 52k+1 – 32k+5 + 32k+1
= f(k) + 52k(55 – 5) – 32k(35 – 3)
= f(k) + 3120(52k) – 240(32k)
= 30t + 30[104(52k) – 8(32k)]
= 30[t + 104(52k) – 8(32k)]

As t and k are integers, so t  104(52k )  8(32k ) is also an integer.

 f(k + 2) is divisible by 30.

 The statement is true for n = k + 2.

By the principle of mathematical induction, the statement is true for all positive even integers n.

16
 1 1
16. Prove, by mathematical induction, that the equation x  2y  n has f (n)  (n  1)  [1  (1) n ]
2 4
non-negative integral solutions for all positive integers n.

Solution:

(1) For n = 1,
the equation x  2y  1 has only one non-negative integral solution (1, 0);
1 1
and f (1)  (1  1)  [1  (1)1 ]  1  0  1
2 4
 The statement is true for n = 1.

(2) For n = 2,
the equation x  2y  2 has 2 non-negative integral solution (0, 1) and (2, 0);
1 1 3 1
and f (2)  (2  1)  [1  (1) 2 ]   (2)  2
2 4 2 4
 The statement is true for n = 2.

(3) Assume the statement is true for some integer k  1,

1 1
i.e., x  2y  k has f (k)  (k  1)  [1  (1) k ] non-negative integral solutions.
2 4

For n = k + 2, consider the equation x  2y  k  2

(i) Case 1: y = 0

When y = 0, x = k + 2. So (k + 2, 0) is a non-negative integral solution.

(ii) Case 2: y  1

x  2y  k  2
x  2y  2  k
x  2(y  1)  k

When y  1 , y  1  0 ,
1 1
by assumption, there are f (k)  (k  1)  [1  (1) k ] non-negative integral solutions.
2 4

17
16. (3) Therefore, combine Case 1 and Case 2, totally the number of non-negative integral solutions are
1 1 
1  f(k)  1   (k  1)  [1  (1) k ]
2 4 
2 1 1
  (k  1)  [1  (1) k ]
2 2 4
1 1
 (k  3)  [1  (1) k ]
2 4
1 1
 (k  3)  [1  (1) k  2 ]
2 4
1 1
 [(k  2)  1]  [1  (1) k  2 ]
2 4
 f(k  2)

 The statement is true for n = k + 2.

By the principle of mathematical induction, the statement is true for all positive integers n.

18
17. Let x1 , x 2 , , x n be n real numbers.
 x  x2   x n  x12  x 2 2   xn2
2

Prove, by induction, that  1   for all positive integers n.

 n  n

Solution:

(1) Claim the statement is true for n = 2m, m  N.

(i) For m = 1, n = 21,

 x1  x 2  x1  (2x1x 2 )  x 2
2 2 2

  
 2  4
x  (x1  x 2 2 )  x 2 2
2 2
 1 [ (x1  x 2 )2  0  x12  2x1x 2  x 2 2  0  x12  x 2 2  2x1x 2 ]
4
2x  2x 2 2
2
 1
4
x1  x 2 2
2

2

 The statement is true for n = 21.

(ii) Assume the statement is true for some integer 2k, where k  1,

 x1  x 2   x 2k  x1  x 2   x 2k 2
22 2

i.e.,   
 2k  2k

For n = 2k+1,

 x1  x 2   x 2k1   x1  x 2   x 2k  x 2k 1  x 2k  2   x 2k  2k 
2 2

   
 2k 1   2  2k 
2
 1  x1  x 2   x 2k x 2k 1  x 2k  2   x 2k  2k  
   
2  2k 2k 

1  x1  x 2   x 2k   x 2k 1  x 2k  2   x 2k 2k  
2 2

      (By the result in (i))

2  2k   2k  

1  x1  x 2   x 2k   x 2k 1  x 2k  2   x 2k  2k  
2 2 2 2 2 2

      
2  2k   2k  
(By induction assumption on the two parts each having 2k terms.)
x12  x 2 2   x 2k 2  x 2k 12  x 2k  2 2   x 2k1 2

2k 1

 The statement is true for n = 2k+1.

By the principle of mathematical induction, the statement is true for infinitely many positive integers n
of the form 2m, i.e., n = 2, 4, 8, 16, …
19
  x  x2   x k  x12  x 2 2   xk2
2

17. (2) Assume the statement is true for some integer k  2, i.e.,  1  
 k  k

For n = k – 1, consider the numbers x1 , x 2 , , x k 1

x1  x 2   x k 1
Let x k 
k 1

By induction assumption on the k numbers, we have

 x1  x 2   x k 1  x k  x12  x 2 2   x k 12  x k 2
2

  
 k  k
 (k  1) x k  x k  x12  x 2 2   x k 12  x k 2
2

  
k k
x1  x 2   x k 12  x k 2
2 2
xk  2

k
kx k  x1  x 2   x k 12  x k 2
2 2 2

(k  1)x k 2  x12  x 2 2   x k 12

x12  x 2 2   x k 12
xk2 
k 1
 x1  x 2   x k 1  x1  x 2   x k 12
2 2 2

  
 k 1  k 1

 The statement is true for n = k – 1.

By the principle of mathematical induction, the statement is true for all positive integers n.

20