175k views
1 vote
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.

User Enomad
by
7.6k points

1 Answer

4 votes

Answer:

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.

User Aditya Santoso
by
9.0k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories