I'm trying to show that given any decreasing sequence $\delta_n \to 0$, we can find a continuous function $f: [-1,1] \to \mathbb{R}$ such that $$\inf\{\|f-P \|_{\infty}\mid P \text{ a polynomial of degree at most } n \} \geq \delta_n.$$
The hint I've been given is to show that, if $\gamma_j$ is a sequence of non-negative numbers with $\sum_{j \geq 1} \gamma_j$ convergent and $T_j$ is the $j$th Chebyshev polynomial, then show that $\displaystyle \sum_{j \geqslant 1} \gamma_j T_{3^j}$ converges uniformly on $[-1,1]$ to a continuous function $f$ and that if $P_n = \sum_{j=1}^n \gamma_j T_{3^j}$ then we can find points $$-1 \leqslant x_0 \leqslant \cdots \leqslant x_{3^{n+1}} \leqslant 1$$ with $$f(x_k) - P_n(x_k) = (-1)^{k+1} \sum_{j=n+1}^{\infty} \gamma_j.$$I haven't even managed to do much with the very first part of the hint, I'm having trouble showing that it converges uniformly. Given that I can't come up with a candidate limit, I suppose I need to show that its uniformly Cauchy (assuming that partial sums of $\gamma_j$ are Cauchy) but I'm not sure how to work with the Chebyshev polynomials.
In any case, I'm uncertain as to how the hint even applies to the question, I can see that $\sum_{j=n+1}^\infty \gamma_j$ is a decreasing sequence, which is more or less the only link I can think of between the parts, but again, doesn't help in any way.
As mentioned in the comment, the Bernstein's lethargy theorem is a generalization of the result you are looking for. Below is a proof following the hints you were given.
Convergence
Note that for for $n \in \mathbb{N}$, for $x \in [-1,1]$, $T_n(x)=\cos(n\mbox{Arccos}(x))$. With $||\cdot||_{\infty}$ the supremum norm on $\mathcal{C}^0([-1,1]),\mathbb{R})$, we have the upper bound $\sum \limits_{n=1}^{\infty} ||\gamma_n T_{3^n}||_{\infty} \le \sum \limits_{n=1}^{\infty} |\gamma_n| \cdot 1 = \sum \limits_{n=1}^{\infty} \gamma_n < +\infty$.
The series $\sum \limits_{n\ge 0} \gamma_nT_{3^n}$ is normally convergent on $[-1,1]$, so it is uniformly convergent to some $f$. $ $
$ $
Existence of the $P_n$
Note that if $\cos(\theta)=-1$ then $\theta \equiv \pi \pmod{2\pi}$ so $3\theta \equiv \pi \pmod{2\pi}$ and by induction $\cos(3^k\theta) = -1$. Similarly, $\cos(\theta)=1 \Rightarrow \forall k \ge 0, \cos(3^k\theta)=1$. (*)
Now for any $n$, we know that $T_{3^n}$ equioscillates: denoting $x_k = \cos\big(\pi - \frac{k\pi}{3^{n+1}}\big)$ for $0\le k \le 3^{n+1}$, we have $-1=x_0<...<x_{3^{n+1}}=1$ and $T_{3^{n+1}}(x_k) = \cos\big(3^{n+1}\cdot (\pi - \frac{k \pi}{3^{n+1}})\big) = (-1)^{1-k} = (-1)^{k+1}$. Then for all $j \ge n+1$ we have $T_{3^j}(x_k) = \cos\big(3^{j-n-1} \cdot 3^{n+1}\mbox{Arccos}(x_k)\big) = (-1)^{k+1}$ because of (*).
Hence, $\sum \limits_{j=n+1}^{\infty} \gamma_j T_{3^j}(x_k) = \sum \limits_{j=n+1}^{\infty} \gamma_j (-1)^{k+1}$. With $P_n := \sum \limits_{j=1}^n \gamma_j T_{3^j}$, we have $f-P_n = \sum \limits_{j \ge n+1} \gamma_j T_{3^j}$, so: $$\mbox{Choosing } x_k := \cos\big(\pi-\frac{k\pi}{3^{n+1}}\big) \mbox{for $0\le k \le 3^{n+1}$, we have } (f-P_n)(x_k) = (-1)^{k+1} \sum \limits_{j=n+1}^{\infty} \gamma_j.$$
Conclusion about the distance of $f$ to polynomial spaces
We will denote $d_p(f)=d(f,\mathbb{R}_p[X]) := \inf \{||f-P||_{\infty}, P\in \mathbb{R}_p[X]\}$. We have $P_n \in \mathbb{R}_{3^n}[X] \subset \mathbb{R}_{3^{n+1}-1}[X]$ and there are $3^{n+1}+1 \ge 3^{n+1}-1$ equioscillation points to $f$ so according to the equioscillation theorem, for any degree $p \in [\![3^n,3^{n+1}-1]\!]$, $P_n$ is the best approximation to $f$ in $\mathbb{R}_p[X]$ so $$\forall n \ge 0,\ \forall p \in [\![3^n,3^{n+1}-1]\!],\ d_p(f) = ||f-P_n||_{\infty} = \sum \limits_{j=n+1}^{\infty} \gamma_j.$$
Now a last constructive part. Let $(\delta_n)$ be any sequence of real decreasing to $0$. Denote $\gamma_j = \delta_j - \delta_{j+1}$. Then $\gamma_j$ is non negative and its sum converges. We apply what is above to these $\gamma_j$ and obtain some function $f$. Let $p \ge 1$. There exists $n \ge 0$ such that $3^n \le p < 3^{n+1}$. Thus $n < p$ (because $3^p \ge 2^p \ge p+1$). The previous inequality gives us $d_p(f) = \sum \limits_{j=n+1}^{\infty} \gamma_j = \delta_{n+1} - 0$. And $(\delta_k)$ is decreasing and $n+1 \le p$ so finally $d_p(f) \ge \delta_p$.