Question

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

See proofs below

Explanation:

A proof by induction consists in two parts:

• The base case: verify the proposition for the first natural number in consideration (it can be 0, 1 or another, but it has to be the first number for which the statement is valid)
• The inductive step: assume that the statement holds true for some natural number n, and prove it for n+1.

a) Base case: for n=1,
`3^(2n)-1=3^2-1=8=4(2)` then 4 evenly divides
`3^(2n)-1` and the statement is true for n=1.

Inductive step: Fix n≥1. Suppose that 4 evenly divides
`3^(2n)-1`, then
`3^(2n)-1=4k` for some integer k. Now,
`3^(2(n+1))-1=3^(2n+2)-1=3^2(3^(2n))-1=9(3^(2n))-9+8=9(3^(2n)-1)+8=9(4k)+8=4(9k)+8=4(9k+2)=4q` for some integer q. Hence 4 evenly divides
`3^(2(n+1))-1` and the statement is proved by mathematical induction.

b) Base case: for n=1,
`7^(n)-1=7^1-1=6=6(1)` then 6 evenly divides
`7^(n)-1` and the statement is true for n=1.

Inductive step: Fix n≥1. Suppose that 6 evenly divides
`7^(n)-1`, then
`7^(n)-1=6k` for some integer k. Now,
`7^(n+1)-1=7(7^(n))-1=7(7^(n))-7+6=7(7^n -1)+6=7(6k)+6=6(7k+1)=4q` for some integer q. Hence 6 evenly divides
`7{n+1}-1` and the statement is proved by mathematical induction.