How does one prove Rodrigues' formula for Legendre Polynomials?
If $n$ is integer \begin{eqnarray*} \frac{d^n}{d x^n} (x^2-1)^n &=& \frac{d^n}{d x^n} \left [ \sum_{k=0}^n (-1)^k \frac{n!}{k!(n-k)!} x^{2n-2k} \right ] \\ &=& \sum_{k=0}^n (-1)^k \frac{n!}{k! (n-k)!} \frac{(2n-2k)!}{(n-2k)!} x^{n-2k}. \end{eqnarray*} The sum above does not go up to $k=n$, since after $k=[n/2]$, the derivatives are 0 then we write
\begin{eqnarray*} \frac{d^n}{d x^n} (x^2-1)^n &=& \sum_{k=0}^{[n/2]} (-1)^k \frac{n!}{k! (n-k)!} \frac{(2n-2k)!}{(n-2k)!} x^{n-2k}. \end{eqnarray*} It follows from the infinite series truncated to the Legendre polynmial that
\begin{eqnarray*} P_n(x) = \frac{1}{2^n n!} \frac{d^n}{dx^n} (x^2-1)^n. \end{eqnarray*}
The approach followed here is in reverse order. We started with Rodriguez's formula and showed that it corresponds to a Legendre polynomial. A more intuitive approach is to start at the polynomials
\begin{eqnarray*} y(x)= (1-x^2)^n. \end{eqnarray*} and take derivates, and verifty that the derivatives taken $n$ times will get you to the Legendre differential equation. That is, we have that
\begin{eqnarray*} y' = -2 n x (1-x^2)^{n-1} \end{eqnarray*} which we can write as
\begin{eqnarray} (1-x^2) y' + 2n x y = 0. \label{tole} \end{eqnarray} and starts looking a bit like a Legendre differential equation.
We want to differentiate this equation $k$ times and use the Leibniz rule. That is, if we call $u=1-x^2$,
\begin{eqnarray*} \frac{ d^k}{dx^k} [u y'] = \sum_{j=0}^{k} \binom{k}{j} u^{(j)} y^{(k-j+1)} \end{eqnarray*} Given that $u$ is a second order polynomial only three terms of this sum will survive. That is
\begin{eqnarray*} \frac{ d^k}{dx^k} [u y'] &=& u y^{(k+1)} + k u' y^{(k)} + k(k-1) u^{(2)} y^{(k-1)} \\ &=& (1-x^2)y^{(k+1)} - 2 k x y^{(k)} -2 \frac{k(k-1)}{2} y^{(k-1)} = 0 \end{eqnarray*} Likewise we use the Leibniz rule for the product $2nxy$ where only two terms will survive. That is
\begin{eqnarray*} \frac{ d^k}{dx^k} [2 n x y] &=& 2 n x y^{(k)} + 2 n k y^{(k-1)}, \end{eqnarray*} we combine the two results above to find
\begin{eqnarray*} (1-x^2)y^{(k+1)} - 2 k x y^{(k)} - k(k-1) y^{(k-1)} + 2 n x y^{(k)} + 2 n k y^{(k-1)} = 0 \end{eqnarray*} At this point we observe that if $k=n+1$, we find
\begin{eqnarray*} (1-x^2)y^{(n+2)} - 2(n+1) x y^{(n+1)} - n(n+1) y^{(n)} + 2 n x y^{(n+1)} + 2 n (n+1) y^{(n)} = 0 \end{eqnarray*} which simplifies to
\begin{eqnarray*} (1-x^2) y^{(n+2)} - 2 x y^{(n+1)} + n(n+1) y^{(n)}=0. \end{eqnarray*}
and this is the Legendre differential equation with $y^n=P_n$. We then showed that
\begin{eqnarray*} \frac{d^n}{dx^n}(1-x^2)^n \end{eqnarray*} satisfies the Lagrange differential equation. The factor $1/(2^n n!)$ is included to make $P(1)=1$.
Check that the left side indeed defines an $n$th order polynomial.
Check that $\displaystyle \int_{-1}^{1}P_n(x)P_m(x)dx$ vanishes for $m\neq n$ (integration by parts).
Check the normalization condition $P_n(1)=1$ (Leibniz rule).
Added: As you almost correctly write in the comment below, the result of integration by parts (assuming that $m<n$ and transferring the derivatives from $P_n$ to $P_m$) can be written as $$\int_{-1}^1P_m(x)P_n(x)dx=\sum_{k=1}^{n}c_{mnk}\left[\frac{d^{m+k-1} (x^2-1)^m}{dx^{m+k-1}}\frac{d^{n-k}(x^2-1)^n}{dx^{n-k}}\right]_{-1}^{1},$$ where $c_{mnk}$ is some irrelevant constant. Consider the second factor in the square brackets. There you have a polynomial having $n$th order zeros at $x=\pm 1$ which we differentiate $n-k$ times. The result will therefore have $k$th order zeros at these points, which implies vanishing of the integral.