Proving P(n) for Every Positive Even Integer

[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 statement...

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 each other in regular induction. ANd in strong induction I've 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!

 

[kreil]

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"

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.

 

[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?

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.

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

 

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

 

[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.
So would I instead write:
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!

 

[shmoe]

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.

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?

 

[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?

 

[shmoe]

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?

What's k(4)?

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

 

[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)

 

[shmoe]

For every postive even integer k
P(i)->p(k+1)

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.

 

[mr_coffee]

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