I need some help with Discrete Structures.

Basic

Alright, technicaly, this was my homework. Keyword: Was. I am doing this problem for my own sake, and I cannot figure out how to do this problem.

Also, >= means greater than or equal to.

Suppose P(n) is a property such that
1. P(0). P(1). P(2) are all true,
2. for all integers k >= 0, if P(k) is true, then P(3k) is true.
Must it follow that P(n) is true for all integers n >= 0? If yes, explain why; if no, give a counterexample.

I only want a push in the right direction, I don't want the answer (that would defeat the purpose of trying to solve this for my own sake).

snowkissed

You have to look at what numbers can be generated by 3k with k >= 0. And then look at that k and see whether or not P(k), k as chosen, holds. That should tip you off.

Basic

Thanks a bunch.

Paul_IQ164

Or try constructing the simplest property you can think of that those two rules will hold for (beyond trivial properties that hold for all numbers). See whether it holds for every number.

Edit: hm, probably too late to be helpful. Never mind.

musanman

seems to me your only remainders are 0,1,2...that probably gives it away

sirSolarius

Basic wrote: »

Alright, technicaly, this was my homework. Keyword: Was. I am doing this problem for my own sake, and I cannot figure out how to do this problem.

Also, >= means greater than or equal to.

Suppose P(n) is a property such that
1. P(0). P(1). P(2) are all true,
2. for all integers k >= 0, if P(k) is true, then P(3k) is true.
Must it follow that P(n) is true for all integers n >= 0? If yes, explain why; if no, give a counterexample.

I only want a push in the right direction, I don't want the answer (that would defeat the purpose of trying to solve this for my own sake).

So, let's take these numbers out for a spin.

P(0) is defined. That means P(3*0) is defined. Oh wait, 0*3 is 0, 0*3*3 = 0, etc. So all we get here is P(0).

P(1) is defined. That means P(3) is defined. That means P(3*3) = P(9) is defined. That means P(3*3*3) = P(27) is defined, etc.... basically, if P(1) is defined, then P(3^k) for any k is defined.

P(2) is defined. Therefore P(2*3) = P(6) is cool. Therefore P( (2*3)*3) = P(18) is cool. Etc. Basically, P(2*3^k) is defined for all k.

Can you represent all numbers using 3^k and 2*3^k? What about... I don't know... 5?

musanman

sirSolarius wrote: »

Basic wrote: »

Alright, technicaly, this was my homework. Keyword: Was. I am doing this problem for my own sake, and I cannot figure out how to do this problem.

Also, >= means greater than or equal to.

Suppose P(n) is a property such that
1. P(0). P(1). P(2) are all true,
2. for all integers k >= 0, if P(k) is true, then P(3k) is true.
Must it follow that P(n) is true for all integers n >= 0? If yes, explain why; if no, give a counterexample.

I only want a push in the right direction, I don't want the answer (that would defeat the purpose of trying to solve this for my own sake).

So, let's take these numbers out for a spin.

P(0) is defined. That means P(3*0) is defined. Oh wait, 0*3 is 0, 0*3*3 = 0, etc. So all we get here is P(0).

P(1) is defined. That means P(3) is defined. That means P(3*3) = P(9) is defined. That means P(3*3*3) = P(27) is defined, etc.... basically, if P(1) is defined, then P(3^k) for any k is defined.

P(2) is defined. Therefore P(2*3) = P(6) is cool. Therefore P( (2*3)*3) = P(18) is cool. Etc. Basically, P(2*3^k) is defined for all k.

Can you represent all numbers using 3^k and 2*3^k? What about... I don't know... 5?

I've been thinking about this more, and I'm running in circles now. I don't think it's important if you can represent 5 that way, I think what you need to do in order to prove that this DOESN'T work is to say that something like 5 works but 5*3=15 doesn't work.

If p->q is only gonna be disproven if p is true and q is false. My gut reaction was to blow this off because my last exposure to these sorts of proofs was in abstract, but now I'm getting frustrated I can't easily prove this.

Edit: It seems to me that since it's easy to prove P(3) works, we're pretty much done. If P(5) works then P(15) must work because P(3*5 = 15). If P(5) doesn't work, then it doesn't fall into our domain and doesn't matter (which doesn't disprove anything). I guess I'm assuming it's a closed function because the integers are closed under multiplication.

Marty81

If P(5) doesn't work, then it doesn't fall into our domain and doesn't matter

Not quite, because the question was, "must it follow that P(n) is true for all integers n >= 0?" To answer that, you need to either prove that it must follow, or you need to construct a statement satisfying 1) and 2), but for which there's some integer x >= 0 for which P(x) isn't true.