Let $T_k(x)$ be the Chebyshev polynomial of the first kind of order $k$, i.e., the polynomial given by the recurrence relation \begin{align} T_0(x)=1, \quad T_1(x)=x, \quad T_k(x)=2xT_{k-1}(x)-T_{k-2}(x), \quad k =2, 3,\ldots \end{align} I'm looking for a formula that gives $T_k(x+1)$ as a linear combination of $T_j(x)$ for $j=0,1,\ldots,k$. For $k= 0, 1, \ldots, 5$ I computed \begin{align} T_0(x+1)&=T_0(x), \\ T_1(x+1)&=T_1(x) + T_0(x), \\ T_2(x+1)&=T_2(x) + 4T_1(x) + 2T_0(x), \\ T_3(x+1)&=T_3(x) + 6T_2(x) + 12T_1(x) + 7T_0(x), \\ T_4(x+1)&=T_4(x) + 8T_3(x) + 24T_2(x) + 40T_1(x)+ 24T_0(x),\\ T_5(x+1)&=T_5(x) + 10T_4(x) + 40T_3(x) + 90T_2(x) + 140 T_1(x) + 81 T_0(x). \end{align} These results are found simplifying the explicit formulas for the Chebyshev polynomials. I don't find a clear pattern here.
My goal, denoting by $\mathbf{T}_K(x)=(T_0(x),T_1(x),\cdots,T_K(x))^\top\in \mathbb{R}^K$, would be to find the matrix $M_K \in \mathbb R^{K\times K}$ such that $\mathbf T_K(x+1) = M_K \mathbf T_K(x)$ without having to compute "manually" the coefficients for any arbitrary $K$.
The most obvious approach would be to try to convert the calculations that you did into "matrix-notation". That would result into something like the following. Let $A_K$ be the $(K+1)\times (K+1)$-matrix with the coefficients of the Chebyshev polynomials up to degree $K$ of the first kind: $$ A_K = \begin{pmatrix} 1 & 0 & & & & \cdots & 0 \\ 0 & 1 & 0 & & & & \\ -1 & 0 & 2 & 0 & & & \\ 0 & -3 & 0 & 4 & 0 & & \vdots \\ 1 & 0 & -8 & 0 & 8 & \ddots & \\ \vdots & & & & & \ddots & 0 \\ \vdots & & & & & & 2^{K-1} \end{pmatrix} $$ and $B_K$ the matrix with the binomial coefficients $\binom{i}{j}$ in the $i$-th row and the $j$-th column: $$ B_K = \begin{pmatrix} 1 & 0 & & & & \cdots & 0 \\ 1 & 1 & 0 & & & & \\ 1 & 2 & 1 & 0 & & & \\ 1 & 3 & 3 & 1 & 0 & & \vdots \\ 1 & 4 & 6 & 4 & 1 & \ddots & \\ \vdots & & & & & \ddots & 0 \\ 1 & & & & & & 1 \end{pmatrix} $$ then $$ M_K = A_K B_K A_K^{-1} $$ I have taken a look at a few of the $A_K^{-1}$ and it seems that the rows are independent of $K,$ that is, for larger $K$, you do not have to recalculate all the rows that you have already calculated for smaller values of $K$. However, I have not found a proof for that fact, and I have not found an elegant way of computing the rows of $A_K^{-1},$ either. When I come up with something, I will extend this answer accordingly.