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
We may tackle this problem along the following lines. Assume for first $[a,b]=[-1,1]$. Up to translation and rescaling, this is not restrictive. Then we want a sequence of polynomials $\{P_n(x)\}_{n\in\mathbb{N}}$ with the property that $P_n(x)$ has degree $n$ and for any $k\in[0,n-1]$ $$ \int_{-1}^{1} x^k P_n(x)=0 $$ holds, so we may build the sequence $\{P_n(x)\}_{n\in\mathbb{N}}$ by applying the Gram-Schmidt process to the monomial base $\{1,x,x^2,\ldots\}$ of $L^2(-1,1)$ with the inner product $$ \langle f,g \rangle = \int_{-1}^{1} f(x)\,g(x)\,dx $$ and by choosing the normalization constraint: $$ \int_{-1}^{1} P_n(x)^2\,dx = \frac{2}{2n+1}.$$ In such a way, our sequence of polynomials is unique. In the next step, we take a sequence of polynomials defined by: $$ Q_n(x) = \frac{1}{2^n n!}\cdot\frac{d^n}{dx^n}\left[\left(x^2-1\right)^n\right] $$ and check, through integration by parts, that this sequence fulfills the same orthogonality properties of the previous sequence, hence $P_n(x)\equiv Q_n(x)$. The previous formula is known as Rodrigues' formula, and leads to the following generating function for Legendre polynomials: $$ \frac{1}{\sqrt{1-2xt+t^2}}=\sum_{n\geq 0}P_n(x)\, t^n.$$ Once we have the generating function at our disposal, to prove the Bonnet's recursion formula is easy through a differentiation trick: just see the first lines of this Wikipedia page.