# using induction, prove that 4 divides 3^(2n+1)+5 for every integer when n is greater than or equal zero?

any help is appreciated! thanks!

step by step would be great.

Relevance
• 8 years ago

Hello,

Does 4 divide (5 + 3²ⁿ⁺¹) for any natural integer n ?

♥ Let's check with n=0:

When n=0,

5 + 3²ⁿ⁺¹ = 5 + 3¹ = 8

which is indeed divisible by 4.

♥ Let's suppose it's true for rank n:

(5 + 3²ⁿ⁺¹) is divisible by 4.

♥ Let's prove it for rank n+1:

5 + 3²ⁿ⁺³ = 5 + 3²ⁿ⁺¹ × 3²

= 5 + (5 + 3²ⁿ⁺¹ - 5) × 9

= 5 + 9(5 + 3²ⁿ⁺¹) - 9×5

= 9(5 + 3²ⁿ⁺¹) - 45 + 5

= 9(5 + 3²ⁿ⁺¹) - 40

Since (5 + 3²ⁿ⁺¹) is divisible by 4, 9(5 + 3²ⁿ⁺¹) is obviously also divisible by 4.

Since 40 is divisible by 4.

Thus (5 + 3²ⁿ⁺³) is the difference of two values that are divisible by for 4.

Hence (5 + 3²ⁿ⁺³) is divisible by 4.

Thus is the property proven at rank n+1.

♥ We demonstrated by mathematical induction that

4 divide (5 + 3²ⁿ⁺¹) for any natural integer n.

(In fact, the same induction can prove it's divisible by 8.)

Logically,

• Anonymous
8 years ago

Assume that the given expression is divisible by 4 (i.e., P(n) is true). Then we need to show that implies the expression w/ n -> n + 1 is also divisible by 4 (i.e., show P(n) => P(n + 1)...)

Let's replace n -> (n + 1) in our given expression:

(3 ^ (2(n + 1) + 1)) + 5 can be rewritten as 3 ^ (2n + 3) + 5

==> 3 ^ [(2n + 1) + 2] + 5

BUT: 3 ^ [(2n + 1) + 2] = (3 ^ (2n + 1)) * 3^2, which becomes 9(3 ^ (2n + 1))

Substituting this in, we arrive at:

==> 9(3 ^ (2n + 1)) + 5 for expression. We can break this apart to form

==> 8(3 ^ (2n + 1)) + 3 ^ (2n + 1) + 5 ==> 8(3 ^ (2n + 1)) + [3 ^ (2n + 1) + 5]

However, note that we assumed the expression in brackets (which is P(n)) was divisible by 4 (at the start), and obviously 8(3 ^ (2n + 1)) is divisible by 4, so the whole expression must also be divisible by 4.

In other words P(n) => P(n + 1) for our induction hypothesis.

Now just go and check that P(1) works (i.e., that the expression is divisible by 4 when n = 1), and that should give you everything you need!