jmc

If we write the value of $f(m,n)$ at the point $(m,n)$ in the plane and border the resulting array with zeros as in the diagram,

$\begin{array}{ccccccc}0& & & & & & \\ 0& 1& & & & & \\ 0& 1-& 7& & & & \\ 0& 1|& 5-& 13& & & \\ 0& 1& 3|& 5-& 7& 9& \\ 0& 1& 1& 1|& 1-& 1& \\ 0& 0& 0& 0& 0& 0& 0\end{array}$

Numbers with a $|$ appended belong to $S_2$; numbers with a $-$ appended belong to $S_3$.

we see that the recursion relation together with the given values for $f(1,n)$ and $f(m,1)$ amount to the assertion that every non-zero entry in this array (except $f(1,1)$) is the sum of the entry immediately to its left, the entry just below it, and the entry diagonally below it to the left.

Now $S(k+2)$ is the sum of the terms on the $(k+2)$nd diagonal, $x+y=k+2,$ and it is clear from the diagram that each non-zero term on the $(k+1)$st diagonal enters this sum twice while each term on the $k$th diagonal enters once; hence, $S(k+2)=2S(k+1)+S(k).$

This expression can be verified as follows:

$$S(k+2)=\sum _{j=1}^{k+1}f(k+2-j,j)$$This is the diagonal running from $(k+1,1)$ to $(1,k+1).$ We would like to apply the recursion relation, but it does not apply for $f(k+1,1)$ or $f(1,k+1),$ so we detach them from the sum and then expand $f(k+2-j,j)$ using the recursion relation:

$$\begin{array}{rl}S(k+2)& =f(k+1,1)+f(1,k+1)+\sum _{j=2}^{k}f(k+2-j,j)\\ & =f(k+1,1)+f(1,k+1)\\ & +\sum _{j=2}^k[f(k+1-j,j)+f(k+2-j,j-1)+f(k+1-j,j-1)]\end{array}$$The sum of $f(k+1-j,j-1)$ is the diagonal corresponding to $S(k).$ The other two sums correspond to most of the diagonal pertaining to $S(k+1),$ though each one is missing one of its boundary value 1 terms. Setting $j=\ell +1$ in two of the sums and use the facts that $f(k+1,1)=1=f(k,1)$ and $f(1,k+1)=1=f(1,k),$ we have

$$\begin{array}{rl}S(k+2)& =\left[f(k,1)+\sum _{j=2}^{k}f(k+1-j,j)\right]+\left[\sum _{\ell =1}^{k-1}f(k+1-\ell ,\ell )+f(1,k)\right]+\sum _{\ell =1}^{k-1}f(k-\ell ,\ell )\\ & =S(k+1)+S(k+1)+S(k)\end{array}$$So $S(k+2)=2S(k+1)+S(k),$ or $p=2,q=1$ so $pq=\boxed{2}.$