# Proof by Induction

## 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
Homework Helper
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 [Broken]

Last edited by a moderator:
found it: http://www.k12math.com/math-concepts/algebra/factoring/factoring.htm [Broken]

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

Last edited by a moderator:
gb7nash
Homework Helper
Thank you. But what part of this page are you referring to? The bottom part about factoring differences of odd powers?

You got it.

$$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
Homework Helper
And to be more specific, whenever you have a difference of the same odd powers an-bn, you can always factor it into:

(a-b)(an-1+an-2b+an-3b2+...+bn-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.

$$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.