f(f(n))

Agnishom · 2014-09-01 05:44:59

f: N -> N is a strictly increasing function such that f(f(n))=3n

What is the value of f(2001)?

bobbym · 2014-09-01 07:09:54

Hi;

Agnishom · 2014-09-01 12:20:55

How?

bobbym · 2014-09-02 00:12:51

Hi;

Agnishom · 2014-09-02 00:42:55

I know.

Further information, please?

bobbym · 2014-09-02 00:55:23

Using the problem itself (RIPOSTP) we can get a bunch of values

{2, 3, 6, 7, 8, 9, 12, 15, 18, 19, 20,...} for n = 1, 2, 3...

Now we just use EM.

Olinguito · 2014-09-02 02:15:55

Hi Agnishom.

Let me try. We have

.

As f is strictly increasing, we must have . It can’t be 1 otherwise . It can’t be 3 either otherwise so which is impossible for a strictly increasing function. Therefore:

by strict-increasingness.

Now note that . This gives and and if then while if then Thus and . Thus .

Last edited by Olinguito (2014-09-02 10:50:33)

ElainaVW · 2014-09-02 02:45:58

Anyone able to attack this problem head on by figuring what f(n) is. No piecewise functions, just one expression?

Agnishom · 2014-09-02 02:57:01

Olinguito wrote:

This gives
and
and if
then
while if
then

I don't get this. How do you get this?

bobbym · 2014-09-02 09:56:56

Hi;

Anyone able to attack this problem head on by figuring what f(n) is.

To some extent that can be done. It leads to the following rote procedure for the solution.

We expand on Michael Somos' answer and continue it. He provides 3 recurrences,

Using these we can recursively solve the problem by redefining it in terms of easier quantities.

Cleaning it up we get:

Now remembering our sequence,

you can see that a(1) = 2 and a(2) = 3 so

Looks complicated but it is just substitutions until the whole problem is defined in terms of the first two terms. I deliberately did not simplify each expression to make it easier to see the tree.

Olinguito · 2014-09-02 10:09:03

Agnishom wrote:

Olinguito wrote:
This gives
and
and if
then
while if
then
I don't get this. How do you get this?

and come from ; they can be proved by induction.

Note that there are integers strictly between and , and also integers strictly between

and

Hence, by strict-increasingness, for . Get it? Put another way:

[list=*]
[*]

If there are m integers strictly between a and b and m integers strictly between f((a) and f(b) and f is strictly increasing, then f(a + r) = f(a) + r for 1 ≤ r ≤ m,[/*]
[/list]

Hence .

Similarly you can show that if then – but you don’t need this bit to calculate .

Last edited by Olinguito (2014-09-02 10:50:12)

Agnishom · 2014-09-02 12:31:04

bobbym wrote:

Hi;
Anyone able to attack this problem head on by figuring what f(n) is.
To some extent that can be done. It leads to the following rote procedure for the solution.
We expand on M Somos's answer and continue it. He provides 3 recurrences,
Using these we can recursively solve the problem by redefining it in terms of easier quantities.
Cleaning it up we get:
Now remembering our sequence,
you can see that a(1) = 2 and a(2) = 3 so
Looks complicated but it is just substitutions until the whole problem is defined in terms of the first two terms. I deliberately did not simplify each expression to make it easier to see the tree.

your code, please?

bobbym · 2014-09-03 02:12:05

There is no code. That was done by hand with a pen. It requires no mathematics at all, just arithmetic on the first 2 initial conditions. M Somos made it easy but EVW was also able to derive his recurrences.

Olinguito · 2014-09-03 03:53:45

I didn’t realize this was supposed to be a computer question and solved it the hard way.

bobbym · 2014-09-03 03:55:54

This is not a computer answer. It was done by pen and paper in the manner shown. The only requirement is arithmetic. See post #13

Agnishom · 2014-09-03 03:57:39

Olinguito wrote:

I didn’t realize this was supposed to be a computer question and solved it the hard way.

I like your solution very much except that a solution is simpler when you can program it. (opinion 37)

bobbym · 2014-09-03 03:59:26

It took 5 minutes and 30 minutes to latex it by hand.

Regarding Opinion #37:

DZ wrote:

You would realize that you REALLY understand something ONLY after you PROGRAMED it YOURSELF.

But as I have said repeatedly my working here is not computer related.

Agnishom · 2014-09-03 04:29:12

M has an option to copy latex

I do not understand integer addition. I cannot program it.

bobbym · 2014-09-03 04:36:37

I am using M's much vaunted latex capabilities. I have even modified them. But latex as he sees it and latex on the forum are not the same things.

I do not understand integer addition. I cannot program it.

You do not understand it, you just think you do.

Agnishom · 2014-09-03 04:41:48

All my programs are based on addition, so I understand nothing?

bobbym · 2014-09-03 04:44:11

It is possible to use words and concepts that you do not fully understand, effectively. If humanity were required to have perfect understanding of things we would not exist. God would have made something better. Obviously perfect understanding or even a good understanding is not necessary for survival in math or life. See my signature.

Agnishom · 2014-09-03 04:47:05

There are people who can program integer addition. E.g, bobbym

bobbym · 2014-09-03 04:52:08

I can program integer addition even multiprecision on very primitive machines but I do not understand many things about it. I think humans get caught up in a very simple trap. Let us say that person A is a lot smarter than most of the other humans. Soon A becomes pride filled. A forgets that just because he/she is superior to other humans does not imply great intelligence or abilities.

Agnishom · 2014-09-03 04:54:02

What is J-rod?

The person below is C

bobbym · 2014-09-03 04:56:03

We are getting way off the topic. Were you able to follow my solution?

Math Is Fun Forum

#1 2014-09-01 05:44:59

f(f(n))

#2 2014-09-01 07:09:54

Re: f(f(n))

#3 2014-09-01 12:20:55

Re: f(f(n))

#4 2014-09-02 00:12:51

Re: f(f(n))

#5 2014-09-02 00:42:55

Re: f(f(n))

#6 2014-09-02 00:55:23

Re: f(f(n))

#7 2014-09-02 02:15:55

Re: f(f(n))

#8 2014-09-02 02:45:58

Re: f(f(n))

#9 2014-09-02 02:57:01

Re: f(f(n))

#10 2014-09-02 09:56:56

Re: f(f(n))

#11 2014-09-02 10:09:03

Re: f(f(n))

#12 2014-09-02 12:31:04

Re: f(f(n))

#13 2014-09-03 02:12:05

Re: f(f(n))

#14 2014-09-03 03:53:45

Re: f(f(n))

#15 2014-09-03 03:55:54

Re: f(f(n))

#16 2014-09-03 03:57:39

Re: f(f(n))

#17 2014-09-03 03:59:26

Re: f(f(n))

#18 2014-09-03 04:29:12

Re: f(f(n))

#19 2014-09-03 04:36:37

Re: f(f(n))

#20 2014-09-03 04:41:48

Re: f(f(n))

#21 2014-09-03 04:44:11

Re: f(f(n))

#22 2014-09-03 04:47:05

Re: f(f(n))

#23 2014-09-03 04:52:08

Re: f(f(n))

#24 2014-09-03 04:54:02

Re: f(f(n))

#25 2014-09-03 04:56:03

Re: f(f(n))

Board footer