Iterative function of $f(n)=2n$ In Cormen's book (chapter 3, page 58), it is shown that for iterative functions:
$$f^{(i)}(n) = \begin{cases}n & \text{if }i=0,\\
f(f^{(i-1)}(n)) & \text{if }i > 0.\end{cases}$$
I have tried to prove it using the associative and the composition properties:
$$f^m \circ  f^n = f^n \circ f^m = f^{m+n}.$$
Therefore,
$$f(f^{i-1}(n)) = f^{1+i-1}(n) = f^i(n).$$
However, following this reasoning I am not able to prove it. What should I do? Is there any easy way, given a linear or polynomial function (correct me If I am wrong, but I think that it could be more complex with fractional iterations), to obtain the iterative function?
Could you help me? Or give me any advice? I am studying by my own, the Cormen's book.
 A: You have posed two distinct questions:


*

*Given $f$ and an explicit definition of $f^{(i)}$, how do we verify that $f^{(i)}$ is correct?

*Given $f$, how do we find $f^{(i)}$?


The first question is easier because we already know what $f^{(i)}$ is. For example, given $f(n) = 2n$ and $f^{(i)}(n) = (2^i)n$, we can verify that $f^{(i)}$ is correct using a proof by induction on $i$. The second question is more difficult because we don't know what $f^{(i)}$ is. My recommendation to you for this kind of problem is to monkey around.
For example, given $f(n) = n^3$, perhaps it isn't immediately obvious what $f^{(i)}$ is. I would begin by listing the first view values of $f^{(i)}$:


*

*$$f^{(0)}(n) = n$$

*$$f^{(1)}(n) = f(f^{(0)}(n)) = f(n) = n^3$$

*$$f^{(2)}(n) = f(f^{(1)}(n)) = f(n^3) = (n^3)^3 = n^9$$


At this point, we might guess that $f^{(i)}(n) = n^{3^i}$. To verify that this is correct, we should try proving it by induction.
Unfortunately, I cannot give you a general "cookbook" strategy for finding $f^{(i)}$ given any arbitrary f. You could try finding $f^{(i)}$ for certain types of functions, such as $f(n) = an$ or $f(n) = n^k$. However, finding $f^{(i)}$ for, say, polynomials in general is much more daunting.
You are wading into the mathematical problem of solving recurrence relations, which can be very difficult. There are many strategies for solving certain types of recurrence relations, but there is no general "cookbook" strategy.
More on recurrence relations: https://en.wikipedia.org/wiki/Recurrence_relation
A: First I think that $f^{(i)}(n) = 2^in$
We can prove that by induction on $i$ 
For $i=0,1$ we have the rule verified.
Suppose that it is for some $i$ and let's prove it for $i+1$ $$f^{(i+1)}(n) = f(f^{(i)}(n)) = f (2^in) =    2 \cdot 2^in = 2^{i+1}n$$
