Math Is Fun Forum

Anakin

Member

Registered: 2009-10-04

Posts: 145

Proofs by Induction

Hi there! Well after a few years of high school and now onto my second semester in university, I'm taking Calc II that involves lots of proofs.

This week we were given a problem sheet with some proofs to prove.

Here is one I needed some aid with:

Prove that

is divisible by 7 for all h >= 1.

Here's what I've done thus far and I figured induction would be the best way to go:

for h = 1:

7 can be divided by 7 so the proof holds true for h = 1

for n = h + 1

And I'm stuck at that. Any hints anyone? Thanks in advance!

Last edited by Anakin (2011-01-16 10:44:00)

Anakin

Member

Registered: 2009-10-04

Posts: 145

Re: Proofs by Induction

I thought about subbing in 1 = h as it's no longer h+1 which gives 105 and it divides evenly by 7. However, that would just be like testing h = 2 from the very start, which is not how a proof should go (I think).

Edit: This website did it in the same way that I did and they have the solution: http://mathcentral.uregina.ca/QQ/database/QQ.09.99/pax1.html at the bottom.

However, I fail to understand the portion about the assumption.

Last edited by Anakin (2011-01-16 11:18:02)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Proofs by Induction

Proof by induction works in two stages.

First you prove the base case. In this case that's h=1, and you've done that.

Next you assume it's true for h=n, and use that to prove that it's true for h=n+1.

You've managed to get that 11^(n+1) - 4^(n+1) = 7*11^n + 4(11^h - 4^h).

The first term on the right is clearly divisible by 7, and by the inductive assumption, the second term also is. Therefore the whole right hand side is divisible by 7 and you're done. [True for h=n] implies [True for h=n+1].

---

Why did the vector cross the road?
It wanted to be normal.

Anakin

Member

Registered: 2009-10-04

Posts: 145

Re: Proofs by Induction

Proof by induction works in two stages.

First you prove the base case. In this case that's h=1, and you've done that.

Next you assume it's true for h=n, and use that to prove that it's true for h=n+1.

You've managed to get that 11^(n+1) - 4^(n+1) = 7*11^n + 4(11^h - 4^h).

The first term on the right is clearly divisible by 7, and by the inductive assumption, the second term also is. Therefore the whole right hand side is divisible by 7 and you're done. [True for h=n] implies [True for h=n+1].

Oh, that makes it very clear indeed. I didn't know that was the case.

Thanks for the explanation and walk-through, Mathsyperson.

xjoaniex

Guest

Re: Proofs by Induction

Proof by induction works in two stages.

First you prove the base case. In this case that's h=1, and you've done that.

Next you assume it's true for h=n, and use that to prove that it's true for h=n+1.

You've managed to get that 11^(n+1) - 4^(n+1) = 7*11^n + 4(11^h - 4^h).

The first term on the right is clearly divisible by 7, and by the inductive assumption, the second term also is. Therefore the whole right hand side is divisible by 7 and you're done. [True for h=n] implies [True for h=n+1].

Oh, that makes it very clear indeed. I didn't know that was the case.

Thanks for the explanation and walk-through, Mathsyperson.

For even more clarity, you could also rewrite as follows

Let 11^n - 4^n = 7a            (since we know that 11^n - 4^n is divisible by 7)

then carrying on from the last line:

= 7 ( 11^h ) + 4 ( 7a )
= 7 ( 11^h ) + 7 ( 4a )
= 7 ( 11^h + 4a )

vichet love

Member

Registered: 2011-01-26

Posts: 2

Re: Proofs by Induction

me wonder one prove 3+2 =6