There's three recurrence relations that help here:
$$P_{n+1}^{'} -P_{n-1}^{'} = (2n+1)P_n$$
$$(n+1)P_{n+1} = (2n+1)xP_n -nP_{n-1}$$
$$P_{n+1}-P_{n-1} = (x^2-1)\cdot \frac{2n+1}{n(n+1)}\cdot P_n^{'}$$
The induction step then looks as follows:
$\newcommand{\partial}[1]{\left[#1\right]}$
$\newcommand{\bracket}[1]{\left(#1\right)}$
\begin{equation}
\begin{split}
[(1-x^2)P_{n+1}^{'}]^{'} &=[(1-x^2)(P_{n-1}^{'}+(2n+1)P_n)]^{'}
\\ &=[(1-x^2)P_{n-1}^{'}]^{'}+(2n+1)\bracket{-2xP_n + (1-x^2)P_n^{'}}
\\ &=-(n-1)nP_{n-1}-2\{(n+1)P_{n+1}+nP_{n-1}\} + n(n+1)(P_{n-1}-P_{n+1})
\\ &=\{-(n-1)n-2n+ n(n+1)\}P_{n-1}+\{-2(n+1)-n(n+1)\}P_{n+1}
\\ &=n\{-(n-1)-2+(n+1)\}P_{n-1}-(n+1)(2+n)P_{n+1}
\\ &=-(n+1)(n+2)P_{n+1}
\end{split}
\end{equation}
Q.E.D.
We consider for even $l$ the polynomial (OPs red part)
\begin{align*}
a_0^{(l)}\left[1-\frac{l(l+1)}{2!}x^2+\frac{l(l+1)(l-2)(l+3)}{4!}x^4-\cdots\right]\tag{1}
\end{align*}
and for odd $l$ the polynomial (OPs blue part)
\begin{align*}
a_1^{(l)}\left[x-\frac{(l-1)(l+2)}{3!}x^3+\frac{(l-1)(l+2)(l-3)(l+4)}{5!}x^5-\cdots\right]\tag{2}
\end{align*}
Note, we use for convenience an upper index $(l)$ to indicate to which polynomial the index $a_0$ resp. $a_1$ belongs. (... and I suppose this helps to clarify the things ...)
Setting $l=0$ in (1) we obtain
\begin{align*}
y_0(x)=a_0^{(0)}
\end{align*}
We observe that all terms containing $x^2$ or higher powers of $x$ vanish, since they all contain the factor $l$.
$$ $$
Setting $l=1$ in (2) we obtain
\begin{align*}
y_1(x)=a_1^{(1)}x
\end{align*}
We observe that all terms containing $x^3$ or higher powers of $x$ vanish, since they all contain the factor $l-1$.
$$ $$
Similarly to the first case we obtain with $l=2$:
\begin{align*}
y_2(x)=a_0^{(2)}\left[1-\frac{2\cdot 3}{2!}x^2\right]=a_0^{(2)}\left(1-3x^2\right)
\end{align*}
since all other terms in (1) contain the factor $l-2$.
We also know that $y_l(1)=1$ for all polynomials $y_l(x)$. We obtain
\begin{align*}
y_0(1)&=a_0^{(0)}=1\\
y_1(1)&=a_1^{(1)}=1\\
y_2(1)&=-2a_0^{(2)}=1
\end{align*}
We conclude $a_0^{(2)}=-\frac{1}{2}$ and obtain finally
\begin{align*}
y_0(x)&=a_0^{(0)}=1\\
y_1(x)&=a_1^{(1)}x=x\\
y_2(x)&=a_0^{(2)}\left(1-3x^2\right)=\frac{1}{2}\left(3x^2-1\right)
\end{align*}
[2016-03-22]: Update according to OPs comment: Why can we restrict the consideration to $a_0^{(l)}$ when $l$ is even and restrict the consideration to $a_1^{(l)}$ when $l$ is odd?
The short answer is: Since the other series diverges when considering the boundary condition at $x=1$ we can set $a_1^{(l)}=0$ when $l$ is even and we can set $a_0^{(l)}=1$ when $l$ is odd.
Some details: We start with the Legendre differential equation
\begin{align*}
(1-x^2)y^{\prime\prime}-2xy^{\prime}+l(l+1)y=0\tag{3}
\end{align*}
and we want to find polynomials as solution which additionally fulfill the boundary condition
\begin{align*}
y(1)=1
\end{align*}
We make an Ansatz with generating functions
\begin{align*}
y(x)=a_0+a_1x+a_2x^2+\cdots
\end{align*}
With the help of the differential equation (3) and via comparing coefficients we obtain
\begin{align*}
y(x)&=a_0^{(l)}\left[1-\frac{l(l+1)}{2!}x^2+\frac{l(l+1)(l-2)(l+3)}{4!}x^4-\cdots\right]\\
&+a_1^{(l)}\left[x-\frac{(l-1)(l+2)}{3!}x^3+\frac{(l-1)(l+2)(l-3)(l+4)}{5!}x^5-\cdots\right]
\end{align*}
with $a_0^{l}$ and $a_1^{l}$ being two degrees of freedom.
We next apply the boundary condition $y(1)=1$.
First case: $l=2k$ even. In this case $y$ has the shape
\begin{align*}
y(x)&=a_0^{(0)}\left[1-\frac{l(l+1)}{2!}x^2-\cdots
\pm\frac{l(l+1)\cdots(l-2k+2)(l+2k-1)}{(l-2k)!}x^{l-2k}\right]\\
&+a_1^{(l)}\left[x-\frac{(l-1)(l+2)}{3!}x^3+\frac{(l-1)(l+2)(l-3)(l+4)}{5!}x^5-\cdots\right]
\end{align*}
We see the $a_0^{(l)}$ series contains only finitely many terms, since all terms having factor $l-2k$ vanish. If we now consider $y(1)=1$, it can be shown that the other $a_1^{(l)}$ series diverges for $x=1$. To overcome this, we set $a_1^{(l)}=0$.
The second case is symmetrically. Here we correspondingly set $a_0^{(l)}=0$ since the $a_0^{(l)}$ series diverges, while the $a_1{(l)}$ series is a polynomial.
Best Answer
This an answer to the version of the question given in Mike's comment. Note first that for any polynomials $p$ and $q$ we have $(xp,q)=(p,xq)$. Second, note that $P_n$ is orthogonal to all polynomials of degree less than $n$.
So if $m \le n-2$, then $$ (xP_n,P_m) = (P_n,xP_m) = 0. $$
But we know that $xP_n$ must be a linear combination of $P_0,\ldots,P_n,P_{n+1}$ (because this holds for any polynomial of degree at most $n+1$), and the coefficient of $P_m$ in this expansion if $(xP_,P_m)/(P_m,P_m)$. Therefore $xP_n$ is a linear combination of $P_{n-1}$, $P_n$ and $P_{n+1}$.
Finally note that this works for any family of orthogonal polynomials, not just Legendre polynomials.