IB Math HL Portfolio Practice

[Ratski]

Hi I think our IB HL Math class is behind compared to other schools when it comes to the portfolios.

Our teacher gave us a practice question to do before she hands us the real ones. It deals with induction quite a bit, which I have a lot of trouble with. I remember the rules of induction are:

1. Assume P(n) is true.

2. Show P(1) is true

3. Assume P(k) is true.

4. Show P(k+1) is true.

Usually the most trouble I have is with the step #4. I can never figure out to show the last step as being true.

So I was wondering if anyone has any other tips or helpful methods they use in trying to prove something by induction?

Thanks.

Edited February 4, 2010 by Ratski

[Austin Glau]

The conclusion of a Proof By Induction usually explains that. "Because n=k and n=k+1 is true, it can be assumed that <insert problem> is true for all values of n"

If the problem is solving the last step and not understanding how it is true, than I will provide you with an example that may help.

for:

1 + 2 + 3 + . . . + n = n(n + 1)

2 .

after the test and n=k, you would do n=k+1

1 + 2 + 3 + . . . + (k + 1) = (k + 1)(k + 2)

2 .

so we can use n=k, we will subsitute the next term in by adding k+1 to both sides...

1 + 2 + 3 + . . . k + (k + 1) = (k + 1)(k + 2)+(k+1)

2 .

Put into fraction

1 + 2 + 3 + . . . k + (k + 1) = (k + 1)(k + 2)

2

Notice how that is the same as the statement we made above. This is how you solve the n=k+1 part.

Tips:

• You almost always will use the n=k part of the proof, and often you need to manipulate it so it works with the n=k+1 part.
• Often you may have an exponent of k. when n=k+1, it will be n^k+1 . Remember that is the same as n^kn, so you can subsitute the n=k series.

[sweetnsimple786]

The problem is that it can get really complicated, and the types of things you're proving are often very diverse.

I know what I have to do is keep reminding myself of what the end result is supposed to look like, so it's kind of like I'm working backwards, except I'm working both forwards and backwards, on the sly, because you're not supposed to be assuming what you're trying to prove.

So by looking at the end result, I try to manipulate the terms to get them to look like what I want. It's easy to have the answer staring you in the face, but you don't realize it because on some level, you've forgotten that you're now in terms of k+1 and not k, so things look different, but they are really the same. Do you know what I mean? Anyways, I might be able to help you work through a problem, but I don't know how to give general advice on this.

[Ratski]

Thanks for the responses both of you. Hopefully that will clear things up a bit, and I would give you my specific question sweetnsimple but I don't know if I am allowed to even if it's a practice one?

[Ratski]

I asked my teacher and she said it's okay to ask since it's for practice? Perhaps just give hints, not direct answers if you wanna be sure of not cheating.

The question is

1. Factorize the expression P(n)=n^x-n for x = 2,3,4,5. Determine if the expression is always divisible by the corresponding x. If divisible use mathematical induction to prove your result by showing whether P(k+1)-P(k) is always divisible by x. Using appropriate technology, explore more cases and make a conjecture for when n^x - n is divisible by x.

I figured out how to do the first part of the question. I realize that 4 is not divisible and that the rule here is that x must be prime. My question however is how to prove by induction whether P(k+1)-P(k) is always divisible by x?

Would you first start with:

P(k+1+1)-P(k+1) = x (Does it equal x since we are trying to prove that it is divisible by x?)

P(k+2)-P(k+1) = x

And then I'm not sure where to go from here. Any advice would be great. Thanks!

[sweetnsimple786]

Since it says 'use mathematical induction to prove your result BY showing whether P(k+1) - P(k) is always divisible by x,' I interpreted that as the problem already giving you the k+1 step. That is, you don't need to do P(k+2). You need to do P(k+1). Does that make sense?

So you'd start by showing when n=k, P(n) holds true, so P(k) holds true. Then you'd solve this for P(k+1). I'm not entirely sure why it's asking if P(k+1) - P(k) is divisible by x, but I have a feeling that this is more of a hint and the answer will be apparent in the end [because I haven't gone through the proof yet]. I understand that it's easy enough to factor out what would be x from those two polynomials, but why do a second polynomial in the first place? Guess I'll see.

Oh yeah, please tell me if you think I misinterpreted in the beginning haha

Edit: I think I got it. =)

Edited February 5, 2010 by sweetnsimple786

[Ratski]

Yes your interpretation makes complete sense (much more than mine anyway)! Thanks I'm going to try and prove it now using your interpretation instead and see if I can get the final result!

[Ratski]

I seem to keep getting stuck =(

I get this:

I'm trying to prove that n^3-n is divisible by 3 for when x=3

Assume P(k) is true: 3a=k^3-k

Show P(k+1) is true: 3a=(k+1)^3 - (k+1)

3a= (k+1)(k+1)(k+1)-(k+1)

3a= k^3+3k^2+2k

Then I thought of substituting in the k^3-k for 3a but that just led me to solve for 0 basically. Then I thought of adding k to both sides for P(k) instead so it became 3a+k=k^3. So then I could substitute in 3a+k when there was a k^3 but that didn't seem to get me anywhere either.

EDIT: I think I may have gotten it sort of... I can get it so P(k+1): 3a=k^3+k

Edited February 5, 2010 by Ratski

[sweetnsimple786]

I don't think you're allowed to make x a specific number and prove it for specific instances... for how would you prove this for all prime numbers? The way that I approached this was

P(k+1) = (k+1)^x - (k+1)

P(k) = k^x - k

So P(k+1) - P(k) = (k+1)^x - (k+1) - (k^x - k) = (k+1)^x - k -1 - k^x + k = (k+1)^x -1 - k^x

Now I used binomial expansion for the first term [the (k+1)^x term]. Try it from here.