Composite Function with reccursive expression

[joao_pimentel]

Hi guys

I'm thinking on this problem for long time :)

Let be one function defined only on POSITIVE INTEGERS
I) f(1) = 1
II) f(2n) = 2 . f(n) + 1, if n ≥ 1
III) f(f(n)) = 4n + 1, if n ≥ 2

Find f(1993)

______________

First I got this, I got to this milestone

f(2n) = 2 . f(n) + {1} \\\\ replacing \ n \ for \ 2n \\\\ f(4n)=2f(2n)+{1}=2(2 . f(n) + {1})+{1} =4f(n)+3\\ f(8n)=2f(4n)+{1}=2(4f(n)+3)+{1}=8f(n)+7\\ f(16n)=2(8n)+{1}=2(8f(n)+7)+{1}=16f(n)+15\\\\ generalizing\\\\ f(32n)=2f(16n)+{1}=\\ =2(16f(n)+15)+1=\\ =32f(n)+2.(2.7+1)+1=\\ =32f(n)+2.(2.(2.(2+1)+{1})+{1})+{1}\\\\ generalizing\\\\ f(2^k)=2^k+{2}.({2}.({2}.({2}.(...)...+{1})+{1})+{1})+{1}=\\ =2^k+{2}.{2}.{2}.{2}...+{8}+{4}+{2}+{1}=\\ =2^k+2^{k-1}+\sum_{i=0}^{k-2}2^k=\\ =2^k+2^{k-1}+\frac{1-2^{k-1}}{{1}-{2}}=\\ ={2}.2^k-{1}\\\\ then\\\\ f(2^k)={2}.2^k-{1}

But I can't go on...

What next steps shall I take?

Thank you in advance

 

[spamiam]

Hi guys

I'm thinking on this problem for long time :)

Let be one function defined only on POSITIVE INTEGERS
I) f(1) = 1
II) f(2n) = 2 . f(n) + 1, if n ≥ 1
III) f(f(n)) = 4n + 1, if n ≥ 2

Find f(1993)

______________

First I got this, I got to this milestone
...
<br /> f(2^k)={2}.2^k-{1}<br />

But I can't go on...

What next steps shall I take?

Thank you in advance

Hi joao!

Thanks for the interesting problem! It took me a while to wrap my head around it.

You've made good progress by showing that $f(2^k) = 2^{k+1} - 1$. Now can you use rule III to compute $f(2^k - 1)$? How about $f(2^k - 3)$? How about $f(2^k - m)$ where $m<2^{k-1}$? Then note that $1993 = 2^{11}-55$.

I started out by computing the values up to f(16) after which I saw a pattern that led me to the above method. Interestingly, I am still unable to compute f(5). I think f(5) = 10 since that's the only consistent way I can see to define it...

 

[joao_pimentel]

Hi people

Just to tell you the solution to this problem is here:
http://forumdematematica.org/viewtopic.php?f=21&t=408&p=1378#p1378

Thank you very much