There are many different ways of defining the Chebyshev polynomials. For the purposes of this question, I'm interested in this inductive definition:
$$T_0(x) = 1, \qquad T_1(x) = x, \qquad T_{n+2}(x) = 2x T_{n+1}(x) - T_n(x)$$
A well-known fact about these polynomials is that they commute and generally play nicely with composition:
$$T_m \circ T_n = T_{mn}.$$
This, among other things, proves that $T_m \circ T_n = T_n \circ T_m\text,$ which is how I first learned about Chebyshev polynomials.
I'm trying to prove that $T_m \circ T_n = T_{mn}$ using the inductive definition of the Chebyshev polynomials given above. Here's what I have so far. First, if $m = 0$, then we have
$$\begin{aligned}(T_m \circ T_n)(x) &= T_m(T_n(x)) \\ &= T_0(T_n(x)) \\ &= 1 \\ &= T_0(x) \\ &= T_{mn}(x)\text.\end{aligned}$$
If $m = 1$, then we have
$$\begin{aligned}(T_m \circ T_n)(x) &= T_m(T_n(x)) \\ &= T_1(T_n(x)) \\ &= T_n(x) \\ &= T_{mn}(x)\text.\end{aligned}$$
However, I'm getting stuck at the inductive step. Let's suppose that the claim is true for $m = k$ and $m = k+1$. Then when $m = k+2$ we have that
$$\begin{aligned}(T_m \circ T_n)(x) &= T_m(T_n(x)) \\ &= T_{k+2}(T_n(x)) \\ &= 2T_n(x) \cdot T_{k+1}(T_n(x)) - T_k(T_n(x)) \\ &= 2T_n(x) \cdot T_{n(k+1)}(x) - T_{nk}(x)\text.\end{aligned}$$
At this point, I'm not sure how to simplify things further. I thought that perhaps doing a secondary induction on $n$ might help here. If $n = 0$, then
$$\begin{aligned}(T_m \circ T_n)(x) &= 2T_n(x) \cdot T_{n(k+1)}(x) - T_{nk}(x) \\ &= 2T_0(x) \cdot T_0(x) - T_0(x) \\ &= 2 - 1 \\ &= 1 \\ &= T_0(x) \\ &=T_{mn}(x)\text. \end{aligned}$$
If $n = 1$, then
$$\begin{aligned}(T_m \circ T_n)(x) &= 2T_n(x) \cdot T_{n(k+1)}(x) - T_{nk}(x) \\ &= 2T_1(x) \cdot T_{k+1}(x) - T_{k}(x) \\ &= 2x \cdot T_{k+1}(x) - T_k(x) \\ &= T_{k+2}(x) \\ &= T_{m}(x) \\ &= T_{mn}(x)\text.\end{aligned}$$
Now, assuming that the claim is true for $n = r$ and $n = r+1$, we look at the case when $n = r+2$. That gives us the following:
$$\begin{aligned}(T_m \circ T_n)(x) &= 2T_n(x) \cdot T_{n(k+1)}(x) - T_{nk}(x) \\ &= 2T_{r+2}(x) \cdot T_{(r+2)(k+1)}(x) - T_{(r+2)k}(x) \\ &= 2(2x T_{r+1}(x) - T_r(x)) \cdot T_{(r+2)(k+1)}(x) - T_{(r+2)k}(x) \\ &= 4x T_{r+1}(x) T_{(r+2)(k+1)}(x) - T_r(x) T_{(r+2)(k+1)}(x) - T_{(r+2)k}(x)\text.\end{aligned}$$
At this point I'm completely stuck and am not sure how to proceed.
Is there a way to carry forward this induction proof to get the desired result? I'm aware that there are other ways of proving this result (using trigonometric identities, using generating functions, etc.), but it would be nice to be able to also show this using the vanilla recursive definition of $T_n$.