Prove 11^n - 4^n Divisible by 7 for All Natural n

[AlexChandler]

Homework Statement

Prove by induction on n that $$11^n - 4^n$$ is divisible by 7 for all natural numbers n (not including zero).

Homework Equations

Principle of mathematical induction.

The Attempt at a Solution

Of course I start by showing that the statement holds for n=1

$$11^1 - 4^1 = 7$$

and

$$7/7 = 1 \in \mathbb{Z}$$

Then I go on to assume that the statement holds for some value k, which gives

$$\frac{11^k - 4^k}{7} = a \in \mathbb{Z}$$

then I examine the situation for k+1

$$\frac{11^{k+1} - 4^{k+1}}{7}$$

and I must show that this is also equal to an integer.

However I have tried rewriting this in many ways in order that I may be able to use the induction assumption. But I have had no luck. Any hints to help me from here?

Thanks.

 

[gb7nash]

There are two cases here:

Case 1: k+1 even

Case 2: k+1 odd

What do you think you can do if k+1 is even? I'm still thinking about the odd case.

edit:

found it: http://www.k12math.com/math-concepts/algebra/factoring/factoring.htm

 

[AlexChandler]

found it: http://www.k12math.com/math-concepts/algebra/factoring/factoring.htm

Thank you. But what part of this page are you referring to? The bottom part about factoring differences of odd powers?

 

[gb7nash]

Thank you. But what part of this page are you referring to? The bottom part about factoring differences of odd powers?

You got it.

 

[l'Hôpital]

$$11^{n+1} - 4^{n+1} = 11 \cdot 11^{n} - 4 \cdot 4^{n}$$

Right? Now, remember that

$$11 = 7 + 4$$

Plug that in for your first 11 and see what happens. : )

 

[gb7nash]

And to be more specific, whenever you have a difference of the same odd powers aⁿ-bⁿ, you can always factor it into:

(a-b)(a^n-1+a^n-2b+a^n-3b²+...+b^n-1)

$$11^{n+1} - 4^{n+1} = 11 \cdot 11^{n} - 4 \cdot 4^{n}$$

Right? Now, remember that

$$11 = 7 + 4$$

Plug that in for your first 11 and see what happens. : )

That's slick. I didn't see that. You could do it either way, but I would suggest this method. It's a lot shorter.

 

[AlexChandler]

$$11^{n+1} - 4^{n+1} = 11 \cdot 11^{n} - 4 \cdot 4^{n}$$

Right? Now, remember that

$$11 = 7 + 4$$

Plug that in for your first 11 and see what happens. : )

Aha! Thank you. I had a feeling it would be something simple like this.

Thank you both very much for your help.