Proof by Induction

  • #1
283
0

Homework Statement



Prove by induction on n that [tex] 11^n - 4^n [/tex] 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

[tex] 11^1 - 4^1 = 7 [/tex]

and

[tex] 7/7 = 1 \in \mathbb{Z} [/tex]

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

[tex] \frac{11^k - 4^k}{7} = a \in \mathbb{Z} [/tex]

then I examine the situation for k+1

[tex] \frac{11^{k+1} - 4^{k+1}}{7} [/tex]

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.
 

Answers and Replies

  • #2
gb7nash
Homework Helper
805
1
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:
  • #3
283
0
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:
  • #4
gb7nash
Homework Helper
805
1
Thank you. But what part of this page are you referring to? The bottom part about factoring differences of odd powers?

You got it.
 
  • #5
258
0
[tex]
11^{n+1} - 4^{n+1} = 11 \cdot 11^{n} - 4 \cdot 4^{n}
[/tex]

Right? Now, remember that

[tex]
11 = 7 + 4
[/tex]

Plug that in for your first 11 and see what happens. : )
 
  • #6
gb7nash
Homework Helper
805
1
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)

[tex]
11^{n+1} - 4^{n+1} = 11 \cdot 11^{n} - 4 \cdot 4^{n}
[/tex]

Right? Now, remember that

[tex]
11 = 7 + 4
[/tex]

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.
 
  • #7
283
0
[tex]
11^{n+1} - 4^{n+1} = 11 \cdot 11^{n} - 4 \cdot 4^{n}
[/tex]

Right? Now, remember that

[tex]
11 = 7 + 4
[/tex]

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.
 

Related Threads on Proof by Induction

  • Last Post
Replies
6
Views
862
  • Last Post
Replies
5
Views
940
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
2
Views
762
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
942
  • Last Post
Replies
3
Views
1K
Top