My attempted answer is $P< Q$ holds for all $k,j>0$.
I think some computation can be done like this(I guess that's the tedious math you mentioned):
Mark $C^{n}_{k}=P$;
and $C^{n+j}_{k-1}=Q$, we have $\frac{P}{Q}$ equal
$$\frac{(n!)}{(n-k)!k!}*\frac{(n+j-k+1)!(k-1)!}{(n+j)!}$$
Mark $n-k=S$, we have the above to be
$$\frac{(n!)}{S!k}*\frac{(S+j+1)!}{(n+j)!}=k^{-1}\frac{n!}{(n+j)!}\frac{(S+j+1)!}{S!}=k^{-1}\frac{\frac{n!}{(n+j)!}}{\frac{(S)!}{(S+j+1)!}}$$
Therefore we only need to consider the function $$A(m,j)=\frac{(m+j)!}{m!}$$ For changing $j$ we have $A(m,j+1)=A(m,j)*(m+j+1)$, for changing $m$ we have $$\frac{A(m,j)}{A(m+1,j)}=\frac{m+1}{m+j+1}<1$$
Therefore $A(m,j)$ increased by changing $m$ as well. Therefore we have the equation:
$$\frac{P}{Q}=\frac{S+j+1}{k}*\frac{A(n,j)}{A(s,j)}=(\frac{n+j+1}{k}-1)\frac{A(n,j)}{A(s,j)}$$
We consider the situation when we change $j$ or $k$. $P_{j},P_{k}$ means $P$'s value when we concern about $j$ or $k$. If we change $j$, we have $$\frac{P_{j}}{Q_{j}}/\frac{P_{j+1}}{Q_{j+1}}=\frac{1}{(S+j+2)}<1$$, moreover it has no lowerbound other than $0$ with $j$ increased. Therefore $\frac{P}{Q}$ is decreasing increasing with $j$ increased irrespective of $k$. Hence $P< Q$ will hold eventually when increasing $j$.
We consider the situation when we change $k$. In this situation $$j>\frac{P_{k}}{Q_{k}}/\frac{P_{k+1}}{Q_{k+1}}=\frac{(S+j+1)(k+1)}{(S+j)k}*\frac{S+j+1}{S+1}>1$$, therefore $\frac{P}{Q}$ increases decreases with one increases $k$ while fixing $j$. More specific we have $$\frac{P_{k}}{Q_{k}}<\frac{P_{n}}{Q_{n}}=\frac{1}{c^{n+j}_{k-1}}<1$$. Therefore $P< Q$ should hold for all value $k,j$. I don't know if I made a mistake somewhere in here.
The points $(j,k)$ such that $P=Q$ are satisfies this equation:
$$\frac{(n+j-k+1)(n+j-k)...(n-k+1)}{(n+j)(n+j-1)...(n+1)*n)}=\frac{k}{n}$$.This cannot hold if $k$ is a prime. I don't know how to push further at this point.
