If $f: \mathbb{C} \to \mathbb{C}$ is analytic and not linear, then $z, f(z), f(f(z)), \dots$ are linearly independent functions over $\mathbb{C}.$

I wish to prove that if $f: \mathbb{C} \to \mathbb{C}$ is analytic and not of the form $az+b,$ then $z, f(z), f(f(z)), \dots$ are linearly independent functions over $\mathbb{C}.$

The cases $n=0, 1$ are trivial. To solve this problem, I'm starting on the first non-trivial scenario: assume $c_1 z + c_2 f(z) + c_3 f(f(z)) = 0$ for some $c_1, c_2, c_3.$ If I can solve this, I'll probably know how to solve the general case. But I'm getting nowhere.

The equations $z-f(z)-f(f(z))+f^3(z)=g(z)-g(g(z)) = 0$ for $f(z) = z+1, g(z) = |z|$ suggest we should impose analycity and non-linearity. Any hints or ideas?

Edit: I've obtained a major breakthrough, but one step is still missing. Define a function to be $n$-independent if $z, f(z), f(f(z)), \dots, f^{(n)}(z)$ are linearly independent over $\mathbb{C}$ on some non-empty open subset of $\mathbb{C}.$

Unproven Lemma: The set of $n$-dependent functions forms a vector space under addition.

$f$ being $n$-dependent easily implies $cf$ is $n$-dependent, so additivity is the only thing that stands in the way of proving this lemma. We need to figure out some way to handle terms like $(f+g) \circ (f+g) = f(f(z)+g(z))+g(f(z)+g(z))$ without messing up the rest of the terms.

First note that $h(z)=az+b$ is $2$-dependent since $z, h(z), h(h(z))$ are $3$ vectors in the $2$ dimensional vector space of polynomials with degree $\le 1.$

Suppose $f$ is analytic and non-linear. Let $n$ be minimal such that $f$ is $n$-dependent. Let $g(z) = f(z)-(f(1)-f(0))z-f(0).$ Since $f$ isn't linear, $n \ge 2,$ implying $g$ is $n$-dependepnt. Suppose $c_0 z + c_1 g(z) + \dots + c_n g^n(z) = 0.$ Setting $z=1,$ we get $c_0 = 0,$ so $c_1 z + \dots + c_n g^{n-1}(z) = 0$ on $\mathcal{O} = g(\mathbb{C}),$ which is open by the open mapping theorem since $g$ is analytic and non-constant.

Thus, $g$ is $n-1$ dependent. If $n \ge 3,$ this means $f$ is $n-1$ dependent, contradiction. If $n=2,$ then $g$ is $1$-dependent, so $g(z)=cz$ for some $c,$ which means $f$ is linear, contradiction.

Write $f^n(z)$ be the $n$-th iterate of $f$, also define $f^0(z) = z$.

Let $U\subset \mathbb{C}$ be an open connected set, $f:U\to U$ analytic. If $f$ is nonconstant and not injective, then $\{z,f,\cdots,f^n\}$ are linearly independent over $\mathbb{C}$.

Proof: Use induction on $n$. If $n=1$, and $a_0z+a_1f(z) = 0$ for all $z\in U$ with $a_i\in \mathbb{C}$. Since $f$ is not injective, there exists distinct $z_1,z_2\in U$, such that $f(z_1)=f(z_2)=c$, so $a_0z_i+a_1c=0 \implies a_0(z_1-z_2)=0$, so $a_0=0$, hence $a_1=0$ also.

Now if $\sum_{i=0}^n a_i f^i(z) = 0$ for all $z\in U$. Using $z_1,z_2$ obtained above, one can similarly show $a_0 = 0$. Let $V=f(U)$, then $$\sum_{i=0}^{n-1} a_{i+1} f^i(z) = 0 \qquad \forall z\in V$$ Since $V\subset U$ is open (open mapping theorem), the above equality holds for all $z\in U$ by analytic continuation. Induction hypothesis then shows all $a_i=0$. QED

Regarding your question, take $U=\mathbb{C}$. If we can show any injective entire function must be linear, then we're done. This is a consequence of Weierstrass-Casorati.