You are here:

Advanced Math/Mathematical Induction

Advertisement


Question
Okay I think I wrote this proof correctly but I just want to make sure!

Claim: For every nonnegative integar n, 7|(3^(2n)-2^n).
Proof: Induction on n
Base: When n=0, then 3^(2n)-2^n = 3^0-2^0 = 0, and 7|0.
Step: Let k be a nonnegative integar and assume that
7|(k^(2k)-2^k). Then k^(2k)-2^k=7x for some integar x,
which implies 9(3^(2k))-2(2^k)=7x,
which implies 3^(2k+2)-2^(k+1)=7x.
By the Inductional Hypothesis, the claim is true.

If I have any errors please let me know!! Thanks!

Answer
This looks good -- there are a few typos and a few changes I will advise.

Here is part of your proof with the corrections in bold:

----------------------------------------------------------------

Claim: For every nonnegative intege r n, 7|(3^(2n)-2^n).

Proof: Induction on n

Base: When n=0, then 3^(2n)-2^n = 3^0-2^0 = 0, and 7|0.

Step:
Let k be a nonnegative integar and assume that 7|(3 ^(2k)-2^k).

Then 3 ^(2k)-2^k=7x for some intege r x,

----------------------------------------------------------------

After this point, you say: 9(3^(2k))-2(2^k)=7x,

That makes no sense. You have:

A - B = C

Where A, B, and C are 3^(2k), 2^k, and 7x respectively. Why should it ever be true that:

9A - 2B = C

?????


You have to make sure that when you take steps, that they are logically valid. For example, one possible step you could take next is:

9A - 9B = 9C

or you could say:

2A - 2B = 2C


But what you have is not valid at all.



Here is what I will say. Generally, you have been asking questions like this:

Prove by induction that f(n) = g(n) for all values of n, or sometimes you are looking at an inequality instead like f(n) ≥ g(n), but the idea is the same.

You prove the base case (n=0 or n=4 or something) just fine -- that's just plug-and-chug to prove that f(0)=g(0).

Then you assume f(k) = g(k), this is the induction hypothesis.

But the next step is usually where your problem is -- in your previous questions, and in this one, you do not deduce f(k+1)=g(k+1) in a valid way.


Here is my suggestion:

Start with f(k+1) and simplify it USING THE INDUCTION HYPOTHESIS.

That is how you use the induction hypothesis. In your proof above that you have written, you simply say at the end "by the induction hypothesis" but you haven't even used the induction hypothesis in that end step!

So, you want to simplify f(k+1). In this case, look at the formula and start simplifying:

3^(2(k+1)) - 2^(k+1)

3^(2k+2) - 2^(k+1)

9 3^(2k) - 2 2^k

We want it to be equal to, or contain, f(k) somehow. I can't factor out 9, nor can I factor out 2, so I want to do something that relates 9 and 2 in a useful way. The most useful way would involve 9 = 2+7, because 7 is special for this problem:

(7+2) 3^(2k) - 2 2^k

7 3^(2k) + 2 3^(2k) - 2 2^k

Now you CAN factor out the 2:

7 3^(2k) + 2 ( 3^(2k) - 2^k )

And now that you see f(k), you can use the induction hypothesis:

7 3^(2k) + 2 ( 7x )

7 ( 3^(2k) + 2x )

which is a multiple of 7. You could even say this equals:

7x'

where x' is the "new" value of x, x' = 2x + 3^(2k).

Sorry to use CAPS and !!!!, I am trying to be emphatic to give proper emphasis and pointers, not to be "yelling" or mad over the internet. I'm not mad, nor yelling. I'm trying to be helpful and stern, and to really get the point across -- not trying to be rude of course!




I'll summarize the new proof:

Claim: For every non-negative integer n, 7|(3^(2n)-2^n).
Proof: Induction on n.
Base: When n=0, then 3^(2n)-2^n = 3^0-2^0 = 0, and 7|0.
Step: Let k be a nonnegative integer and assume that
7|(3^(2k)-2^k). Then 3^(2k)-2^k=7x for some integer x.
If you say x' = 2x + 3^(2k) then:
3^(2(k+1)) - 2^(k+1) = 73^(2k) + 2 ( 3^(2k) - 2^k ) = 73^(2k) + 2 ( 7x ) = 7 x'
Thus 3^(2(k+1)) - 2^(k+1) is divisible by 7.
QED


And I'll summarize the new strategy:

Given some formula f(n)=g(n), or inequality f(n)≥g(n), or some statement f(n) is ______, you want to prove by induction, the steps are:

1. First prove the base case, plug in n=0 (or some other base number). Show that it is true by simply observing the equality, inequality, or property you expect.

2. Assume for induction that f(k)=g(k), f(k)≥g(k), or that f(k) is _____.

3. Manipulate the expression f(k+1) until you get something that looks like f(k).*

4. Use the induction hypothesis to get an equality, inequality, etc. that proves the case where n=k+1. From this, you are done.

*If this doesn't work, try also manipulating g(k+1) too, to try to get g(k).

Advanced Math

All Answers


Answers by Expert:


Ask Experts

Volunteer


Clyde Oliver

Expertise

I can answer all questions up to, and including, graduate level mathematics. I am more likely to prefer questions beyond the level of calculus. I can answer any questions, from basic elementary number theory like how to prove the first three digits of powers of 2 repeat (they do, with period 100, starting at 8), all the way to advanced mathematics like proving Egorov's theorem or finding phase transitions in random networks.

Experience

I am a PhD educated mathematician working in research at a major university.

Organizations
AMS

Publications
Various research journals of mathematics. Various talks & presentations (some short, some long), about either interesting classical material or about research work.

Education/Credentials
BA mathematics & physics, PhD mathematics from a top 20 US school.

Awards and Honors
Various honors related to grades, various fellowships & scholarships, awards for contributions to mathematics and education at my schools, etc.

Past/Present Clients
In the past, and as my career progresses, I have worked and continue to work as an educator and mentor to students of varying age levels, skill levels, and educational levels.

©2016 About.com. All rights reserved.