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

Answer:

See proofs below

Step-by-step 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.