Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2011-01-16 10:33:44

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! smile

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

Offline

#2 2011-01-16 10:36:21

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

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

Offline

#3 2011-01-16 12:44:51

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.

Offline

#4 2011-01-16 13:11:32

Anakin
Member
Registered: 2009-10-04
Posts: 145

Re: Proofs by Induction

mathsyperson wrote:

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

Offline

#5 2011-01-27 02:00:20

xjoaniex
Guest

Re: Proofs by Induction

Anakin wrote:
mathsyperson wrote:

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

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 )

#6 2011-01-27 02:23:12

vichet love
Member
Registered: 2011-01-26
Posts: 2

Re: Proofs by Induction

me wonder one prove 3+2 =6

Offline

Board footer

Powered by FluxBB