KingGeorge
  • KingGeorge
[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)]
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
KingGeorge
  • KingGeorge
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)\).
beginnersmind
  • beginnersmind
Do you need help with this or is it more of a puzzle? (I managed to prove that f(3)=3)
KingGeorge
  • KingGeorge
More of a puzzle. I know how to get the answer. BTW, how did you prove f(3)=3?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

beginnersmind
  • beginnersmind
2=f(2)
KingGeorge
  • KingGeorge
2 and 2 are not coprime, so that doesn't work.
beginnersmind
  • beginnersmind
oh
anonymous
  • anonymous
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).
KingGeorge
  • KingGeorge
That's certainly not the solution I have.
anonymous
  • anonymous
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.
KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
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.
beginnersmind
  • beginnersmind
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?
anonymous
  • anonymous
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.
KingGeorge
  • KingGeorge
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.
KingGeorge
  • KingGeorge
I will return to answer questions after dinner.
anonymous
  • anonymous
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.
anonymous
  • anonymous
1 is coprime to every integer, so \(f(n)=n\) by definition.
anonymous
  • anonymous
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\]
beginnersmind
  • beginnersmind
I think that only proves f(n)=f(n)*f(1)=f(n)
anonymous
  • anonymous
Right, what Joe said.
beginnersmind
  • beginnersmind
Anyway, I'm stuck, I'll read KG's solution later.
anonymous
  • anonymous
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
anonymous
  • anonymous
I spent a good ten minutes thinking about rebuilding the series of primes, should have remembered, always start with the identity :P
beginnersmind
  • beginnersmind
George Polya said, if you can't solve the problem, try to solve an easier one that's similar. Any suggestions?
beginnersmind
  • beginnersmind
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?
anonymous
  • anonymous
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.
beginnersmind
  • beginnersmind
"and realized you could just force the definition via the identity." What do you mean by that?
experimentX
  • experimentX
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
KingGeorge
  • KingGeorge
@experimentX That is correct, but it still doesn't solve the original problem.
KingGeorge
  • KingGeorge
I have posted a hint for those who had previously participated.
anonymous
  • anonymous
\[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? :/ :(
KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
2=f(2)
KingGeorge
  • KingGeorge
2 is not coprime to 2. So \(f(2)f(2)\) does not necessarily equal \(f(4)\)
experimentX
  • experimentX
f(2) = f(1+1) = f(1) + f(1) ???
anonymous
  • anonymous
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.
KingGeorge
  • KingGeorge
@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.
KingGeorge
  • KingGeorge
@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.
anonymous
  • anonymous
\[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?
anonymous
  • anonymous
But this doesn't help either :/
KingGeorge
  • KingGeorge
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.
KingGeorge
  • KingGeorge
I'll post a second, more helpful hint in half an hour or so if you think you need it.
anonymous
  • anonymous
\[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. :/
anonymous
  • anonymous
From the above inequalities, \[5+ k\le f(5) \le 5+2k\]
KingGeorge
  • KingGeorge
Have posted 2nd hint. I would also suggest letting \(f(3)=k\). It makes the manipulations easier
anonymous
  • anonymous
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. :/
KingGeorge
  • KingGeorge
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.
KingGeorge
  • KingGeorge
If you could convince me that the k's are in fact the same, you would indeed have a proof.
anonymous
  • anonymous
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\]
anonymous
  • anonymous
Can I type QED now? :D
KingGeorge
  • KingGeorge
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
KingGeorge
  • KingGeorge
I must sleep now. I will return to see any corrections you have made.
anonymous
  • anonymous
Ohh hmm :( I will try again.
anonymous
  • anonymous
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\]
anonymous
  • anonymous
How about this?
anonymous
  • anonymous
Shall I type QED now? :D
KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
Oh I knew something was wrong. hmm I will try again. (Y) :D
KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
I can't take \(f(18)=f(3)f(6)\). Can I? I think \(f(2)\cdot f(9)\) is right. Hmm \(2f(9)\).
KingGeorge
  • KingGeorge
That's the right track. Now what's the upper bound of\(f(9)\) in terms of \(f(3)\)?
KingGeorge
  • KingGeorge
Hint: \[f(9)\leq f(10)-1\]
anonymous
  • anonymous
4k-3 or 4a -3?
KingGeorge
  • KingGeorge
Right. So this means that \(f(18) \leq \text{____}\)
anonymous
  • anonymous
8k - 6 \(\ge\) f(18) How do I solve it for f(17)?
KingGeorge
  • KingGeorge
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.
KingGeorge
  • KingGeorge
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).
anonymous
  • anonymous
I can only get f(15) using f(3) and f(5)
KingGeorge
  • KingGeorge
And from f(15) you can get f(18)
anonymous
  • anonymous
\[2k + k^2 \le f(15) \le 2k^2 -k\]
KingGeorge
  • KingGeorge
Just use \[2k + k^2 \le f(15)\]Now this means that \[\text{______}\le f(18)\]
anonymous
  • anonymous
\((k+1)^2 + 2 \le f(18) \le 8k+6\)
KingGeorge
  • KingGeorge
\[(k+1)^2 + 2 \le 8k+6\]Now just solve for k
anonymous
  • anonymous
\((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?
KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
Ohh I can't concentrate at all :( I see now, \[3\le k \le 3 \implies k=3 \implies f(3) =3\]
anonymous
  • anonymous
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?\[\]
KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
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.
KingGeorge
  • KingGeorge
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.
anonymous
  • anonymous
and why wasn't f(1) enough for us to use induction? why did we need to solve it for f(3).
KingGeorge
  • KingGeorge
\(f(1)\) just let us get \(f(2)\). We needed a value greater than 2 to generate larger numbers using the multiplicative rule.
anonymous
  • anonymous
ohh, thanks. i couldn't have done this without your help.
KingGeorge
  • KingGeorge
You did very well. =D
KingGeorge
  • KingGeorge
I appreciate the amount of time you spent on this. Thanks for actually doing this.

Looking for something else?

Not the answer you are looking for? Search for more explanations.