Composite Function with reccursive expression

In summary, the conversation is about a problem involving a function defined on positive integers and the task is to find the value of f(1993). The solution is found by using a pattern and rule III to compute values of f(2^k - m) where m<2^(k-1). The solution can be found on a forum dedicated to mathematics.
  • #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
 
Physics news on Phys.org
  • #2
joao_pimentel said:
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(2^k)={2}.2^k-{1}
[/tex]

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...
 
Last edited:
  • #3

1. What is a composite function with recursive expression?

A composite function with recursive expression is a function that is defined using itself. It is a function that calls itself repeatedly until a base case is reached.

2. How is a composite function with recursive expression different from a regular function?

A composite function with recursive expression is different from a regular function because it calls itself within its own definition. This allows for more complex and iterative calculations.

3. What is a base case in a composite function with recursive expression?

A base case in a composite function with recursive expression is a condition that is used to terminate the recursive calls and return a final value. It is necessary to prevent an infinite loop.

4. How is a composite function with recursive expression useful in scientific research?

A composite function with recursive expression is useful in scientific research because it allows for the creation of complex and efficient algorithms for solving problems. It is commonly used in fields such as computer science, mathematics, and physics.

5. What are some examples of real-life applications of composite functions with recursive expression?

Some examples of real-life applications of composite functions with recursive expression include algorithms for searching and sorting data, fractal patterns in nature and art, and calculating compound interest in finance.

Similar threads

Replies
11
Views
2K
Replies
5
Views
978
  • Calculus
Replies
13
Views
1K
Replies
3
Views
1K
Replies
16
Views
2K
Replies
1
Views
833
Replies
2
Views
1K
Replies
2
Views
789
Replies
3
Views
1K
Back
Top