Assume you have a Chebyshev approximation of a function $f(x)$ evaluated using the Clenshaw summation method, up to polynomial order $N$:
$$ f(x) = \sum_{k=0}^{N-1} a_k T_k(x) = (a_0 - y_2)T_0(x) + y_1 T_1(x) $$
where
$$ T_N = 2x \cdot T_{N-1} - T_{N-2} $$
and
$$ \begin{aligned} y_{N+1} &= 0\\ y_{N} &= 0 \\ y_{N-1} &= a_{N-1} - y_{N+1} + 2x \cdot y_N \\ \vdots \\ y_1 &= a_1 - y_3 + 2x \cdot y_2 \end{aligned} $$
I would like add higher order terms to $f(x)$, for example by computing a correction up to an order $\tilde{N} > N$ given by an expression
$$ \tilde{f}(x) = \sum_{k=N}^{\tilde{N}-1}a_k T_k(x) = (a_N - y_{N+2})T_N + y_{N+1} T_{N+1}. $$
The magnitudes $y_{N+2}$ and $y_{N+1}$ can be computed with the Clenshaw recurrence using just the $a_k$ for $k=N+1, \ldots, \tilde{N}-1$, but the polynomials $T_N$ and $T_{N+1}$ would have to be evaluated using the recurrence relation from $T_0$ and $T_1$. For my use case, I can only evaluate linear combinations of $x$ so I cannot use the analytical expression $T_N(x) = \cos(N \arccos(x))$.
I wonder if I could rewrite this expression using the previous solution $f(x)$, such as in terms of $T_0, T_1$, the old $y_k$, and the new $a_k$ for $k = N, \ldots, \tilde{N}-1$.
I have tried solving the recurrence relation by hand as
$$ \begin{aligned} \tilde{f}(x) &= (a_N - y_{N+2})T_N + y_{N+1}T_{N+1} \\ &= (a_N - y_{N+2} + 2x\cdot y_{N+1})T_N - y_{N+1}T_{N-1} \\ &= y_N(2x\cdot T_{N-1} - T_{N-2}) - y_{N+1} T_{N-1} \\ &= (2x \cdot y_N - y_{N+1}) T_{N-1} - y_N T_{N-2} \\ &= \left[ (a_{N-2} - y_N)T_{N-2} + y_{N-1} T_{N-1}\right] - (a_{N-2}T_{N-2} + a_{N-1}T_{N-1}) \end{aligned} $$
but in the end I am unable to reduce $T_N$ and $T_{N+1}$ as I get as a remainder precisely the original approximation $\sum_{k=0}^{N-1}c_k T_k$.
I am confused because this is very straightforward to do using the polynomial evaluation, as conserving the previously computed $T_{N-1}(x)$ allows you to compute $\tilde{f}(x)$ for higher order terms without having to re-evaluate the whole series. Given that the terms $y_k$ are constructed iteratively from the polynomials up to $T_{N-1}$, I would expect that they could be used to compute $T_N$.
Any hint (or solution) would be appreciated.
Use $y_{N+1} = a_{N+1} - y_{N+3} + 2x y_{N+2}$ instead of substituting $y_{N+2}$ in the first term. Because you need to get larger $N$ after expansion.
Then $$ \begin{equation} \begin{aligned} \tilde f &= a_N T_N - y_{N+2} T_N + a_{N+1} T_{N+1} - y_{N+3} T_{N+1} + 2x y_{N+2} T_{N+1} \\&= a_N T_N +a_{N+1}T_{N+1} + (a_{N+1}- y_{N+3})T_{N+1} + y_{N+2} T_{N+2} \end{aligned} \end{equation}$$
which recovers the iterative scheme if you use an induction argument.