Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Composite Function with reccursive expression

  1. May 28, 2012 #1
    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
     
  2. jcsd
  3. May 30, 2012 #2
    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...
     
    Last edited: May 30, 2012
  4. Jun 22, 2012 #3
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Composite Function with reccursive expression
  1. Composite Functions (Replies: 3)

Loading...