# Confused on trying to figure out what this paragraph is saying, setting up induction

1. Oct 2, 2006

### mr_coffee

Hello everyone. I'm trying to set this problem up to prove by induction but having some issues.

Suppose that for some Predicate P(k), you first prove that P(1) is true, and then you do the following. You prove that, for every positive even integer k, if P(i) is true for all odd integers i such that 0 < i < k, then P(k+1) is true.

For which values of n can you now be certain that P(n) is true? Give an explanation of why your answer is correct.

Hint: you have to "unwind the meaning of the first paragraph"

So am i suppose to actually prove that for every positive even integer k, if P(i) is true for all odd integers i such that 0 < i < k, then P(k+1) is true.

Then test the base case to make sure p(1) is true?

And if that is true, then I have to go on to prove that
P(1)->P(2)
P(2)->P(3)
P(3)->P(4)
P(n)->P(n+1) ?

Am I suppose to be using Strong mathematical induction or just regular? P(n) makes me think i have to use strong, because in those they usually start out with,

Let the property P(n) be the inequality or statment....

So could i write:

Let the Property P(n) be 2k+1, where k is any postive integer >= 1. #this would be the definition of an odd number.

But I still don't see what i'm proving. Usually I'm proving 2 statements are equivlent to eachother in regular induction. ANd in strong induction Ive only been proving things in a sequence so i'm confused on how to set this up and the book had no examples of this type. Any help would be great! Thanks!

2. Oct 3, 2006

### kreil

You don't need to perform induction, it is done in the paragraph. You need to analyze the paragraph to see which values of n it proved are true
for P(n). To break down the paragraph:

P(k) is true for the first even number k=1, and for k=1, P(i) is true for all odds less than k=1 and thus P(k+1)=P(2) is true.

Now P(k) is true for the second even number k=2, and for k=2, P(i) is true for all odds less than k=2 and thus P(k+1)=P(3) is true.

Continuing in this way, P(k) is true for all even natural numbers k greater than 0, and P(i) is true for all odd natural numbers less than any k, so it is true for all odd numbers. Thus P(n) is true for all natural numbers.

3. Oct 3, 2006

### shmoe

The second sentence is saying something about an even k that's greater than 0 (0 < i < k), so start with k=2. What can you conclude from that paragraph?

1 is not the first even number, it's odd.

4. Oct 3, 2006

### kreil

I guess I interpreted it wrong, I figured n=1 is i=1, n=2 is k=1, n=3 is i=2 etc...

5. Oct 3, 2006

### mr_coffee

I understand what kreil is saying can I interpret what he said but instead of starting out with 1, start out with 2 like you said shmoe?
If i take what kreil has said, and did the following (i'm goign to copy and paste ur stuff kriel).

P(k) is true for the first even number k=2, and for k=1, P(i) is true for all odd integers i such that 0 < i < k, therefore P(k+1)

But what confuses me here is, you say start with k = 2, but they say P(1) is true, which is odd, not even.
P(k) is true for the first odd number k=1, and for k=2, P(i) is true for all even numbers P(k+1) and thus P(k+1)=P(2) is true.

Now P(k) is true for the second even number k=2, and for k=2, P(i) is true for all odds less than k=2 and thus P(k+1)=P(3) is true.

Continuing in this way, P(k) is true for all even natural numbers k greater than 0, and P(i) is true for all odd natural numbers less than any k, so it is true for all odd numbers. Thus P(n) is true for all natural numbers.

I modified some of kreils stuff.

Thanks for the help guys!

6. Oct 3, 2006

### shmoe

Where did the bold part come from?

You start off knowing that if k is even and if P(i) is true for all odd integers i such that 0 < i < k, then P(k+1) is true.

When k=2, you can check the conditions of this line. Meaning we have to consider P(i) for odd values of i satisfying 0<i<2, namely i=1. We already know P(1) is true, so these conditions are satsified for k=2 and we can conclude P(2+1)=P(3) is true. Nothing at all is said about P(2) here.

Now what happens at k=4?

7. Oct 3, 2006

### mr_coffee

oh i understand now I think!
well you know k(4) is true becuase P(3) is true.
and when k = 4,
P(4+1) = P(5) must also be true and this will keep going on and on becuase a number is either even or odd. So P(n) would be true for all integers right?

8. Oct 3, 2006

### shmoe

What's k(4)?

How are you concluding that P(2) is true?

9. Oct 3, 2006

### mr_coffee

whoops i have no idea why I wrote that.

We know that P(1) is true;
and
For every postive even integer k
P(i)->p(k+1)

Which i thought means, if P(i) is true, then p(k+1) must be true acording to the universal instantiation, that no matter what particular integer i is subsititued in place of i, the statement "If P(i) then P(k+1)" is true.

Doesn't this statement prove it? Because you proved 1 is true, which is an odd number, then you add 1+1 = 2, so now P(2) is true becuase P(1) was true. and p(2)->p(3) now P(3) is true becuase P(2) was true and P(1) was true.

Or do i have to do it like the following:
P(1) base case true;
P(2)->P(2+1)
P(3)->P(3+1)

I was thinking in terms of:
P(1) base case true;
P(1) -> P(1+1)
P(2) -> P(2+1)
...
...
...
P(n) -> P(n+1)

10. Oct 3, 2006

### shmoe

You don't know this at all.

You know "if k is even and P(i) is true for all odd i with 0<i<k then P(k+1) is true".

Maybe stating it like:

"if k is even and P(1), P(3), ..., P(k-1) are all true, then P(k+1) is true"

will help, the "i" seems to be a source of confusion.

11. Oct 3, 2006

### mr_coffee

Ahh that does help, i'll give it another try, thanks for the help!