Contest problem in functional equations. 
Let n be a positive integer with $f(n)= 1! +2! +3!+... +n!$ and P(x),
  Q(x) be polynomials in $x$ such that $f(n+2)=P(n)f(n+1)+Q(n)f(n)$ for
  all $n \geq 1$, then  which of the options is/are correct? 
  
  
*
  
*$P(x)= x+3$
  
*$Q(x)= -x-2$
  
*$P(x)= -x-2$
  
*$Q(x)= x+3$
  

I managed to get that options 1 and 2 are correct by calculating $f(1),f(2),f(3),f(4)$, substituting them in the equation and then trying out all the options. Is there any way to do the problem without using the options? 
 A: $$
\big[1!+2!+\dots+n!+(n+1)!+(n+2)!\big]=\\
\big[1!+2!+\dots+n!+(n+1)!\big]P(n)+\\
\big[1!+2!+\dots+n!\big]Q(n)
$$
So an easy way to get this is to have $P(n)+Q(n)=1$ so that all terms
$1!+2!+\dots+n!$ come out right.  Then we want $P(n)$ so that
$$
(n+1)!P(n) = (n+1)!+(n+2)!
$$
Divide by $(n+1)!$ to get
$$
P(n) = 1+(n+2)=n+3.
$$
and, as noted $P(n)+Q(n)=1$, so $Q(n) = -n-2$.
A: If $P(x)$ is greater than linear or $Q(x)$ is greater than quadratic you have a delicate cancellation which can not be achieved.  You have to have $Q$ one degree higher than $P$.  Now look at lots of points for large $n$ and argue the difference cannot have that many roots.  I am handwaving, but I believe it.  Given that, we have five constants to determine, so can just take five values and solve the equations 
$$10=3P(2)+Q(1)\\34=10P(3)+3Q(2)$$ and so on.  Now let $P(n)=an+b, Q(n)=cn^2+dn+e$ and you get five equations in five unknowns.  
In this case, the high order term comes only from $P(n)$, which forces that $P(n)=n+b$ and $Q(n)=dn+3$ so you only need three equations.  I also don't know how to prove that.
