Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

KingGeorge Group Title

[SOLVED] George's problem of the [insert arbitrary time unit] Define a function \(f: \mathbb{Z}^+ \longrightarrow \mathbb{Z}^+\) such that \(f\) is strictly increasing, is multiplicative, and \(f(2)=2\). Show that \(f(n) =n\) for all \(n\). Hint 1: You need to find an upper and a lower bound for a certain \(n\) and show that the bounds are the same. Hint 2: Find the upper and lower bound for \(n=18\). Using this show that \(f(3)=3\). Now deduce that \(f(n)=n\) for all \(n\). [EDIT: It should be noted that this problem is relatively difficult (but only if you don't see the right process)]

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Strictly increasing means that if \(a>b\), then \(f(a)>f(b)\). Multiplicative means that if \(a, b\) are coprime, then \(f(ab)=f(a)f(b)\).

    • 2 years ago
  2. beginnersmind Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Do you need help with this or is it more of a puzzle? (I managed to prove that f(3)=3)

    • 2 years ago
  3. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    More of a puzzle. I know how to get the answer. BTW, how did you prove f(3)=3?

    • 2 years ago
  4. beginnersmind Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    2=f(2)<f(3)<f(4)=f(2)*f(2)=4

    • 2 years ago
  5. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    2 and 2 are not coprime, so that doesn't work.

    • 2 years ago
  6. beginnersmind Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    oh

    • 2 years ago
  7. nbouscal Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Any ring automorphism on Z that takes 2 to itself will by definition take every n to itself? (Just a guess, I'm not that far along yet).

    • 2 years ago
  8. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    That's certainly not the solution I have.

    • 2 years ago
  9. nbouscal Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Well it's kind of part of the definition of Z, isn't it, that what you describe in the problem would be the case? I mean, it should be a pretty straightforward proof by induction, I would think. But I might be misunderstanding the question.

    • 2 years ago
  10. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I'm using \(\mathbb{Z}^+\) which is equivalent to \(\mathbb{N}\) with out 0. I'm just repeating the problem the way it was given to me.

    • 2 years ago
  11. nbouscal Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Hey! You can answer a question I have! I just discovered this site today. How do you do inline TeX? And yeah, I follow what ring you're referring to, I just don't see what makes the problem interesting, I guess.

    • 2 years ago
  12. beginnersmind Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I need some help, I know almost no number theory. To define a multiplicative function I need to define it on all powers of all primes, right?

    • 2 years ago
  13. nbouscal Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Sorry, not a ring at all, just a set. Even so, it seems like a pretty simple induction proof to show that f(n)=n if f(2)=2. Still could be missing something though.

    • 2 years ago
  14. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Use "\ (" instead of "\ [" (without the spaces to do inline \(\LaTeX\). Defining it on all powers of primes would certainly be helpful. Also, this is not just a simple induction proof.

    • 2 years ago
  15. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I will return to answer questions after dinner.

    • 2 years ago
  16. nbouscal Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Awesome. Most sites I use just use the $ notation, haven't seen it with parentheses before. Also, yes, I see where the problem is with this, will think about it for some time and try to work it out.

    • 2 years ago
  17. nbouscal Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    1 is coprime to every integer, so \(f(n)=n\) by definition.

    • 2 years ago
  18. joemath314159 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    That just means:\[f(n\cdot 1)=f(n)f(1)\]first you need to show f(1)=1, which can be done like this:\[f(2)=f(2\cdot 1)=f(2)f(1)\Longrightarrow 2=2f(1)\Longrightarrow f(1)=1\]

    • 2 years ago
  19. beginnersmind Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I think that only proves f(n)=f(n)*f(1)=f(n)

    • 2 years ago
  20. nbouscal Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Right, what Joe said.

    • 2 years ago
  21. beginnersmind Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Anyway, I'm stuck, I'll read KG's solution later.

    • 2 years ago
  22. nbouscal Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Or alternatively, the way that I thought about it, if f is strictly increasing, the only element left in Z+ that is less than 2 is 1, so f(1) has to be 1

    • 2 years ago
  23. nbouscal Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I spent a good ten minutes thinking about rebuilding the series of primes, should have remembered, always start with the identity :P

    • 2 years ago
  24. beginnersmind Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    George Polya said, if you can't solve the problem, try to solve an easier one that's similar. Any suggestions?

    • 2 years ago
  25. beginnersmind Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Looking only at the set of primes and numbers that are the product of n distinct primes what constraint do we get for f, if we want to keep it strictly increasing?

    • 2 years ago
  26. nbouscal Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I tried building it up from primes that way and hit a dead end, which is when I went back to basics and realized you could just force the definition via the identity. Building it by primes seems a bit more difficult, and I'm not positive how you would go about it.

    • 2 years ago
  27. beginnersmind Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    "and realized you could just force the definition via the identity." What do you mean by that?

    • 2 years ago
  28. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    f(2*1) = f(2)f(1) f(1) = 1 f(3*2) = f(3) 2 f(3) = f(6)/2 f(5) = f(10)/2 f(n) = f(2n)/2 for odd n

    • 2 years ago
  29. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    @experimentX That is correct, but it still doesn't solve the original problem.

    • 2 years ago
  30. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I have posted a hint for those who had previously participated.

    • 2 years ago
  31. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    \[f(2) = f(1\cdot2) = f(1)\cdot f(2) = 2 \implies f(1) = 1\] Lets assume \(f(k-1) = k-1\) and same follows up from 2. \[f(k) = f\left(\frac k 2 \cdot 2\right) = f\left(\frac k2\right)\cdot f(2)\] \[1 < \frac{k}2< k-1\] Is this enough lol? :/ :(

    • 2 years ago
  32. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    If you knew that \(f(n)=n\) for at least one value of \(n\geq3\) that would work (with a little bit of fixing). But first you need to show that \(f(n)=n\) for some value of \(n\) that's not 1 or 2.

    • 2 years ago
  33. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    2=f(2)<f(3)<f(4)=f(2)*f(2)=4 what's wrong with this one?

    • 2 years ago
  34. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    2 is not coprime to 2. So \(f(2)f(2)\) does not necessarily equal \(f(4)\)

    • 2 years ago
  35. experimentX Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    f(2) = f(1+1) = f(1) + f(1) ???

    • 2 years ago
  36. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    I don't understand it. Can you give me an example which proves f(2)f(2) isn't necessarily f(4). Sorry If I sound dumb.

    • 2 years ago
  37. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    @experimentX Not necessarily. This is not necessarily a homomorphism. @Ishaan94 Suppose \(f(3) =10\) and \(f(6)=f(2)f(3)=20\). \(f(4)\) could be anywhere in between. The function is given as multiplicative (see first post for definition), so if the two arguments don't have a gcd of 1, you can't say anything about the product.

    • 2 years ago
  38. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    @experimentX It would probably be simpler to say that the function is just multiplicative. Not additive, and what you posted was the definition of additive.

    • 2 years ago
  39. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    \[f(3)>f(2) \implies f(3) \ge f(2) + 1 \implies f(3) \ge 3\]\[f(4) \ge 4 \implies f(n) \ge n \]Can we assume \(f(n)=n+k\)? but k may not be necessarily a constant term right?

    • 2 years ago
  40. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    But this doesn't help either :/

    • 2 years ago
  41. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    That's the right direction. If you follow that direction correctly, you'll be able to get the lower bound you need. To get the upper bound you need, you'll need to change things a little bit first.

    • 2 years ago
  42. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I'll post a second, more helpful hint in half an hour or so if you think you need it.

    • 2 years ago
  43. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    \[f(3) =3 +k, \quad f(6) =f(3)f(2) = 6+2k, \quad f(5)< 6 +2k, \quad f(4)> 3+k \]\[f(5) \le 5 + 2k, \quad f(4) \ge 4+ k\]\[f(5) \ge f(4) + 1 \implies f(4)+1\le f(5)\le5+2k \] If I prove \(f(4) +1 = 5+2k\) then this might work out, but \(f(4) +1 \ge 5+k\). It's just more and more and more inequalities. :/

    • 2 years ago
  44. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    From the above inequalities, \[5+ k\le f(5) \le 5+2k\]

    • 2 years ago
  45. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Have posted 2nd hint. I would also suggest letting \(f(3)=k\). It makes the manipulations easier

    • 2 years ago
  46. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    wait... \(f(4) + 1 \le 5+ 2k \implies f(4) \le 4 +2k \implies f(3) <(4) \le 4+2k\) \(\implies 4 + k \le f(4) \le 4 + 2k\) \[\implies n + k \le f(n) \le n + 2k\] woow, nice. 4 + 2k< 5 + k k< 1 Woow, Wow. K<1. Yay! I am so happy! K can not be less than Zero as f(n) is supposed to be an increasing function. So, K has to be Zero. Yay! Yayyy! But I am not sure if it's right. :/

    • 2 years ago
  47. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I don't think that's quite right. It's almost correct, but in your last expression, 4+2k>5+k, I'm pretty sure the second k is not the same k.

    • 2 years ago
  48. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    If you could convince me that the k's are in fact the same, you would indeed have a proof.

    • 2 years ago
  49. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    No, it's same. Really?\[f(3) >2 \implies f(3) \ge f(2) + 1 \implies f(3) \ge 3\]\[\implies f(n) \ge n\] Let \(f(3) = 3 + k\). \[f(6) = f(2) \cdot f(3) = 6 + 2k\] \[f(5) < f(6) \implies f(5) < 6+ 2k \implies f(5) \le 5 + 2k \tag1\] \[f(4) < f(5) \implies f(4) + 1 \le f(5) \tag2\] From1 and 2.\[f(4) +1 \le f(5) \le 5+2k \tag3\] \[f(3) < f(4) \implies f(3) + 1 \le f(4) \implies 4 + k \le f(4) \tag 4\] From 4 and 3 \[5 + k \le f(5) \le 5 + 2k \tag5\]Also from 3\[f(4) + 1\le 5+2k \implies f(4) \le 4 + 2k\tag6\]From 4 and 6 \[4+k \le f(4) \le 4+ 2k\] \[\implies n+k \le f(n) \le n +2k\tag7 \] From 5 and 6 \[4+2k < 5+k \implies k<1 \implies k=0\tag8\]From 7 and 8 \[n\le f(n)\le n \implies f(n) = n\]

    • 2 years ago
  50. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Can I type QED now? :D

    • 2 years ago
  51. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I think I see the actual problem now. You're trying to compare an upper bound for 4, and a lower bound for 5. Your claim is that those bounds can't overlap, but I don't see anything that shows those bounds can't overlap. It is true of course, that the best bounds don't overlap, but these bounds are not as small as possible. If \(f(4)=4+2k\), then of course \(4+2k<f(5)<6+2k\). And we're done. But what if \(f(4)<4+2k\)? That is still possible and we no longer get the same implication.

    • 2 years ago
  52. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I must sleep now. I will return to see any corrections you have made.

    • 2 years ago
  53. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Ohh hmm :( I will try again.

    • 2 years ago
  54. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Hmm but I still do have the bounds hehehe \[n+k \le f(n) \le n+2k\] Wait... for \(n=2\),\[2+k \le f(2) \le 2+2k \implies 2+ k \le 2\le 2+2k \implies k=0\]

    • 2 years ago
  55. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    How about this?

    • 2 years ago
  56. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Shall I type QED now? :D

    • 2 years ago
  57. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    You have those bounds for \(n \geq3\) so you can't use it for \(n=2\). For \(n=2\), you're given that it's 2. You're method is great, you just need to refine it to get an upper and lower bound for a single number and show that the bounds are the same.

    • 2 years ago
  58. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Oh I knew something was wrong. hmm I will try again. (Y) :D

    • 2 years ago
  59. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    It's very helpful to set \(f(3)=a\). From there, get a lower and upper bound for \(f(18)\). If you do it just right, you'll get a quadratic that you can solve for a.

    • 2 years ago
  60. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    I can't take \(f(18)=f(3)f(6)\). Can I? I think \(f(2)\cdot f(9)\) is right. Hmm \(2f(9)\).

    • 2 years ago
  61. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    That's the right track. Now what's the upper bound of\(f(9)\) in terms of \(f(3)\)?

    • 2 years ago
  62. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Hint: \[f(9)\leq f(10)-1\]

    • 2 years ago
  63. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    4k-3 or 4a -3?

    • 2 years ago
  64. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Right. So this means that \(f(18) \leq \text{____}\)

    • 2 years ago
  65. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    8k - 6 \(\ge\) f(18) How do I solve it for f(17)?

    • 2 years ago
  66. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Ignore f(17). You found the upper bound of f(18). Now we need to find the lower bound for f(18). Once again, you want to start at f(3)=k.

    • 2 years ago
  67. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    In this part, you'll want to get a quadratic. You'll want to look at f(3) and f(5) and use these to get to f(18).

    • 2 years ago
  68. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    I can only get f(15) using f(3) and f(5)

    • 2 years ago
  69. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    And from f(15) you can get f(18)

    • 2 years ago
  70. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    \[2k + k^2 \le f(15) \le 2k^2 -k\]

    • 2 years ago
  71. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Just use \[2k + k^2 \le f(15)\]Now this means that \[\text{______}\le f(18)\]

    • 2 years ago
  72. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    \((k+1)^2 + 2 \le f(18) \le 8k+6\)

    • 2 years ago
  73. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \[(k+1)^2 + 2 \le 8k+6\]Now just solve for k

    • 2 years ago
  74. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    \((k+1)^2 + 2 \le 8k + 6 \implies k^2 + 2k+3 \le 8k+6 \implies k^2 -6k - 3\le0\) \[ \implies 3 -2\sqrt3 \le k \le 3 + 2\sqrt3 \] But is this what I am supposed to get?

    • 2 years ago
  75. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    There was a typo that was making this rather hard. It should be \[(k+1)^2 + 2 \le f(18) \le 8k-6\]You had this right originally, there was just a typo that was perpetuated. Try and solve this one.

    • 2 years ago
  76. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    Ohh I can't concentrate at all :( I see now, \[3\le k \le 3 \implies k=3 \implies f(3) =3\]

    • 2 years ago
  77. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    So, we finally have f(3)=3. But I don't get it why did we have to go all the way from 4 and 5 to 18. Why a quadratic?\[\]

    • 2 years ago
  78. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    We can get the relation \[k^2-6k+9 \le 0\implies (k-3)^2 \le 0\]There is only one value of \(k\) that solves this, \(k=3\). That's why we need a quadratic. It allows us to get an inequality with only 1 solution. If it were linear, we would have a line with infinite solutions satisfying the inequality.

    • 2 years ago
  79. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    eh the proof still isn't complete I will have to show it for f(n). I think I will have to use induction. \[f(3) =3\] Lets assume it works up from 3 to 2k-1. \[f(k) = 2\cdot f\left(k\right) = 2k\] I am not sure if it's right. I can only recall strong induction from your previous problem.

    • 2 years ago
  80. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    To show it for all n, just take \(f(2)f(3)=f(6)=2*3=6\) So \(f(4)=4\) and \(f(5)=5\) since it has to be strictly increasing. We can just continue this process up to infinity.

    • 2 years ago
  81. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    and why wasn't f(1) enough for us to use induction? why did we need to solve it for f(3).

    • 2 years ago
  82. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \(f(1)\) just let us get \(f(2)\). We needed a value greater than 2 to generate larger numbers using the multiplicative rule.

    • 2 years ago
  83. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 3

    ohh, thanks. i couldn't have done this without your help.

    • 2 years ago
  84. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    You did very well. =D

    • 2 years ago
  85. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I appreciate the amount of time you spent on this. Thanks for actually doing this.

    • 2 years ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.