- #1
joao_pimentel
- 68
- 0
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
[tex]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}[/tex]
But I can't go on...
What next steps shall I take?
Thank you in advance
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
[tex]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}[/tex]
But I can't go on...
What next steps shall I take?
Thank you in advance