Question

Exercise 8.5.1: Proving divisibility results by induction. About Prove each of the following statements using mathematical induction. (a) Prove that for any positive integer n, 4 evenly divides 32n-1. (b) Prove that for any positive integer n, 6 evenly divides 7n - 1.

Answer 1

a) 4(9
`x`+2)

b)6(7
`x` +1)

Explanation:

a) Prove that for any positive integer n, 4 evenly divides 32n-1

checking whether the statement is correct or not

∴ n = 1;

=
`3^(2n) -1`

=
`3^(2*1) -1`

= 9 - 1

= 8

hence it is divisible by 4

Let the statement is for n = k

∴
`3^(2k ) -1` = 4
`x`(equation 1)

`(3^(2))^(k) -1` = 4
`x`

`9^(k) -1` = 4
`x` (equation 1)

Now, we have to proof the statement is true for n = k+1

=
`3^(2(k+1)) -1`

=
`(3^(2k) * 3^(2) ) -1` (
`x^(a+b) = x^(a) * x^(b)`)

Adding & Subtracting 8

=
`(3^(2k) * 3^(2) ) -1 +8 -8`

=
`9^(k) * 9 -9 + 8`

taking common 9

= 9(
`9^(k)` -1)+8

= 9 (4
`x`) +8 (from equation 1)

= 36
`x` + 8

= 4(9
`x`+2)

if (9
`x`+2) = p

then = 4p

Since
`3^(2(k+1)) -1` = 4p evenly divisible by 4

therefore given statement is true

b)Prove that for any positive integer n, 6 evenly divides
`7^(n) - 1`

checking whether the statement is correct or not

∴ n = 1;

`7^(n) - 1`

7 - 1

6

6 is divisible by 6

hence the given statement is true for n = 1

let it also true for n = k

`7^(k) - 1 = 6x` (equation 2)

Now we have to proof the statement is true for n = k+1

`7^(k+1) - 1`

`7^(k)*7 - 1`

Adding & Subtracting 6

`7^(k)*7 - 1 +6 - 6`

`7^(k)*7 - 7 +6`

`7(7^(k)* - 1) +6`

7(6
`x` )+6 ( from equation 2)

= 42
`x` + 6

= 6(7
`x` +1)

if 6(7
`x` +1) = p

then = 6p

Since
`7^(k+1) -1` = 6p evenly divisible by 6

therefore given statement is true