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.
Let be
$$\mathcal A_{k l}^m = \int_{-1}^1 P_k^m \left({x}\right) P_l^m \left({x}\right) \, \mathrm d x $$
where the associated Legendre functions are
$$P^m_l \left({x}\right) = \left({1 - x^2}\right)^{m/2} \dfrac {\mathrm d^m P_l \left({x}\right)} {\mathrm d x^m}={\left({1 - x^2}\right)^m \frac {\mathrm d^{k + m} } {\mathrm d x^{k + m} } \left({x^2 - 1}\right)^k }\qquad 0 \le m \le l$$
Thus we have
$$\mathcal A_{k l}^m = \frac 1 {2^{k + l} k! l!} \int_{-1}^1 \left({\left({1 - x^2}\right)^m \frac {\mathrm d^{k + m} } {\mathrm d x^{k + m} } \left({x^2 - 1}\right)^k}\right) \left({\frac{\mathrm d^{l + m} } {\mathrm d x^{l + m} } \left({x^2 - 1}\right)^l }\right) \, \mathrm d x$$
where $k$ and $l$ occur symmetrically.
Let $l \ge k$.
We can integrate by parts $l + m$ times
$$\int_{-1}^1 u v' \mathrm d x = \left.{u v}\right|_{-1}^1 - \int_{-1}^1 v u' \ \mathrm d x$$
where $u = \left({1 - x^2}\right)^m \frac {\mathrm d^{k + m} } {\mathrm d x^{k + m} } \left({x^2 - 1}\right)^k$ and
$v' = \frac {\mathrm d^{l + m}} {\mathrm d x^{l + m}} \left({x^2 - 1}\right)^l$
For each of the first $m$ integrations by parts, $u$ in the $\left.{uv}\right|_{-1}^1$ term contains the factor $\left({1 - x^2}\right)$, so the term vanishes.
For each of the remaining $l$ integrations, $v$ in that term contains the factor $\left({x^2 - 1}\right)$ so the term also vanishes.
This means
$$ \mathcal A_{k l}^m = \frac {\left({-1}\right)^{l + m} } {2^{k + l} k! l!} \int_{-1}^1 \left({x^2 - 1}\right)^l \frac {\mathrm d^{l + m} } {\mathrm d x^{l + m} } \left({\left({1 - x^2}\right)^m \frac {\mathrm d^{k + m} } {\mathrm d x^{k + m} } \left({x^2 - 1}\right)^k }\right) \, \mathrm d x$$
Expanding the second factor using Leibniz's Rule
$$\frac {\mathrm d^{l + m} } {\mathrm d x^{l + m} } \left({1 - x^2}\right)^m \frac {\mathrm d^{k + m} } {\mathrm d x^{k + m} } \left({x^2 - 1}\right)^k= \sum_{r \mathop = 0}^{l + m} \binom {l + m} r
\frac {\mathrm d^r} {\mathrm d x^r} \left({1 - x^2}\right)^m \frac {\mathrm d^{l + k + 2 m - r} } {\mathrm d x^{l + k + 2 m - r} } \left({x^2 - 1}\right)^k$$
the leftmost derivative in the sum is non-zero only when $r \le 2 m$ (remembering that $m \le l$) and the other derivative is non-zero only when $k + l + 2 m - r \le 2 k$, that is, when $r \ge 2 m + l - k$.
Because $l \ge k$, these two conditions imply that the only non-zero term in the sum occurs when $r = 2 m$ and $l = k$.
Thus
$$\mathcal A_{k l}^m = \left({-1}\right)^l \delta_{k l} \frac {\left({-1}\right)^{l + m} } {2^{2 l} \left({l!}\right)^2}
\binom {l + m} {2 m} \int_{-1}^1 \left({x^2 - 1}\right)^l \frac {\mathrm d^{2 m} } {\mathrm d x^{2 m} } \left({1 - x^2}\right)^m \frac {\mathrm d^{2 l} } {\mathrm d x^{2 l} } \left({1 - x^2}\right)^l \mathrm d x$$
where $\delta_{k l}$ is the Kronecker Delta.
The factor $(-1)^l$ at the front of $\mathcal A_{k l}^m$ comes from switching the sign of $x^2 - 1$ inside $\left({x^2 - 1}\right)^l$.
To evaluate the differentiated factors, expand $\left({1 - x^2}\right)^k$ using the Binomial Theorem
$$\left({1 - x^2}\right)^k = \sum_{j \mathop = 0}^k \binom k j \left({-1}\right)^{k-j} x^{2 \left({k-j}\right)}$$
The only term that survives differentiation $2^k$ times is the $x^{2 k}$ term, which after differentiation gives
$$\left({-1}\right)^k \binom k 0 2 k! = \left({-1}\right)^k \left({2k}\right)!$$
Therefore
$$\mathcal A_{k l}^m = \left({-1}\right)^l \delta_{k l} \frac 1 {2^{2 l} \left({l!}\right)^2} \frac {\left({2 l}\right)! \left({l + m}\right)!} {\left({l - m}\right)!} \int_{-1}^1 \left({x^2 - 1}\right)^l \ \mathrm d x =\left({-1}\right)^l \delta_{k l} \frac 1 {2^{2 l} \left({l!}\right)^2} \frac {\left({2 l}\right)! \left({l + m}\right)!} {\left({l - m}\right)!} \mathcal B_l$$
The integral
$$\mathcal B_l=\int_{-1}^1 \left({x^2 - 1}\right)^l \ \mathrm d x$$
can be evaluated by a change of variable $x = \cos \theta$
Thus
$$\mathcal B_l= \left({-1}\right)^{l + 1} \int_\pi^0 \left({\sin \theta }\right)^{2 l + 1} \, \mathrm d \theta=\left({-1}\right)^{l} \int_0^\pi \left({\sin \theta }\right)^{2 l + 1} \, \mathrm d \theta$$
Integration of
$$\frac {\mathrm d \left({\sin^{n - 1} \theta \cos \theta}\right)} {\mathrm d \theta} = \left({n-1}\right) \sin^{n-2} \theta - n \sin^n \theta$$
gives
$$\int_0^\pi \sin^n \theta \, \mathrm d \theta = \frac {\left.{-\sin^{n - 1} \theta \cos \theta}\right|_0^\pi} n + \frac {\left({n - 1}\right)} n \int_0^\pi \sin^{n - 2} \theta \, \mathrm d \theta= \frac {\left({n - 1}\right)} n \int_0^\pi \sin ^{n - 2} \theta \, \mathrm d \theta$$
since
$\displaystyle \left.{-\sin^{n-1} \theta \cos \theta}\right|_0^\pi = 0$ for $n > 1$.
Applying this result to $\int_0^\pi \left({\sin \theta }\right)^{2 l + 1} \, \mathrm d \theta$ and changing the variable back to $x$ yields:
$$\int_{-1}^1 \left({x^2 - 1}\right)^l \, \mathrm d x = - \frac {2 l} {2 l + 1} \int_{-1}^1 \left({x^2 - 1}\right)^{l - 1} \, \mathrm d x\quad\text{for}\;l \ge 1$$
Using this recursively
$$\displaystyle \int_{-1}^1 \left({x^2 - 1}\right)^l \, \mathrm d x = \left({-1}\right)^l \left({\frac {2 l} {2 l + 1} \frac {2 \left({l - 1}\right)} {2 l - 1} \frac {2 \left({l - 2}\right)} {2 l - 3} \cdots \frac 2 3}\right) \int_{-1}^1 \, \mathrm d x$$
and noting that
$$ \frac {2 l} {2 l + 1} \frac {2 \left({l-1}\right) } {2 l - 1} \frac {2 \left({l - 2}\right)} {2 l - 3} \cdots \frac 2 3= \frac {2^l l!} {\left({2 l + 1}\right) \left({2 l - 1}\right) \left({2 l - 3}\right) \cdots 3}
= \frac{2^l l!} {\frac {\left({2 l + 1}\right)!} {2^l l!} }
= \frac {2^{2 l} \left({l!}\right)^2} {\left({2 l + 1}\right)!}
$$
it follows that
$$\mathcal B_l=\int_{-1}^1 \left({x^2 - 1}\right)^l \mathrm d x = \ \left({-1}\right)^l \ \frac{2^{2l+1} \left({l!}\right)^2} {\left({2l+1}\right) !}$$
Therefore we have
$$\mathcal A_{k l}^m =\left({-1}\right)^l \delta_{k l} \frac 1 {2^{2 l} \left({l!}\right)^2} \frac {\left({2 l}\right)! \left({l + m}\right)!} {\left({l - m}\right)!} \mathcal B_l= \delta _{k l} \frac 2 {2 l + 1}
\frac {\left({l + m}\right) !} {\left({l - m}\right)!}$$
that is
$$\int_{-1}^1 P_k^m \left({x}\right) P_l^m \left({x}\right) \, \mathrm d x = \delta _{k l} \frac 2 {2 l + 1}
\frac {\left({l + m}\right) !} {\left({l - m}\right)!}$$
Best Answer
We apply the Leibniz Product Rule \begin{align*} (f\cdot g)^{(n)}=\sum_{j=0}^n\binom{n}{j}f^{(j)}g^{(n-j)} \end{align*} to $(x^2-1)^L=(x+1)^L(x-1)^L$ according to the hint.
Comment:
In (1) we apply the Leibniz product rule.
In (2) we do the differentiation which is not too hard since we have powers of linear factors only \begin{align} \frac{d^j}{dx^j}(x+1)^L &= L(L-1)(L-2)\cdots(L-j+1)(x+1)^{L-j}\\ &=\frac{L!}{(L-j)!}(x+1)^{L-j}\\ \frac{d^{L-m-j}}{dx^{L-m-j}}(x-1)^L &= \frac{L!}{(L-(L-m-j))!}(x-1)^{L-(L-m-j)}\\ &=\frac{L!}{(m+j)!}(x-1)^{m+j} \end{align}
In (3) we factor out $(L-m)!$ from $\binom{L-m}{j}$ and expand the expression with $\frac{(L+m)!}{(L+m)!}$.
In (4) we shift the index $j$ to start from $m$ and substitute in the expression $j\rightarrow j-m$ accordingly.
In (5) we factor out $(x+1)^m(x-1)^m=(x^2-1)^m$ and rearrange the factorials.
In (6) we write the expression using derivatives.
In (7) we extend the range of $j$ to $0\leq j \leq L+m$ without changing anything, since we are just adding zeros.
More detailed: Since $(x+1)^L$ and $(x-1)^L$ are polynomials in $x$ of degree $L$ we get \begin{align*} \frac{d^j}{dx^j}(x+1)^L&=0\qquad\qquad L<j\leq L+m\\ \frac{d^{L+m-j}}{dx^{L+m-j}}(x-1)^L&=0\qquad\qquad 0\leq j<m\\ \end{align*}