Se puede demostrar fácilmente por inducción.
Una forma de encontrar los coeficientes, suponiendo que ya sabemos que es un grado $3$ polinomio, es calcular la suma de $n=0,1,2,3$. Esto nos da cuatro valores de un grado $3$ polinomio, y así podemos encontrar.
La mejor manera de acercarse a ella, sin embargo, es a través de la identidad
$$ \sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}. $$
Esta identidad es cierto ya que en el fin de elegir un $(k+1)$-subconjunto de $n+1$, primero elija un elemento $t+1$, y, a continuación, una $k$-subconjunto de $t$.
Por eso sabemos que
$$ \sum_{t=0}^n A + Bt + C\binom{t}{2} = A(n+1) + B\binom{n+1}{2} + C\binom{n+1}{3}. $$
Ahora la elección de $A=0,B=1,C=2$, tenemos
$$ A+Bt + C\binom{t}{2} = t^2. $$
Por lo tanto, la suma es igual a
$$ \binom{n+1}{2} + 2\binom{n+1}{3}. $$