$f^n = f^k \circ f^{n-k}$

Question

$f : A \to A$ and $n \in n$, Let $f^n$ be defined by $f^1 = f$ and $$f^n = f \circ f^{n-1}$$ for $n \gt 1$.

Let $n$ and $k$ be natural numbers with $k \lt n$. Prove $$f^n = f^k \circ f^{n-k}$$

Induction: $n=2$

$f^2 = f \circ f^{2-1} \implies f^2 = f^1 \circ f^1$

Hence, the base case holds true.

I.H: Suppose its true for $n=m$. We have to prove that it also holds true for $n=m+1$, $$f^{m+1} = f \circ f^m$$

How do I show that it will be equal to $$f^n = f^k \circ f^{n-k}$$

Answer 1

Let $k<m+1$. Then $k-1<m$

Using definition and inductive hypothesis,

$$f^{m+1}:=f\circ f^m=f\circ (f^{k-1}\circ f^{m-k+1})=(f\circ f^{k-1})\circ f^{m+1-k}:=f^k\circ f^{m-k+1}$$

Third equality comes from associativity, rest are definitions and inductive hypothesis

Answer 2

Hint: fix $m$ and prove by induction on $n$ that $f^{n+m} = f^n \circ f^m$.