Let $f(m,1) = f(1,n) = 1$ for $m \geq 1, n \geq 1,$ and let $f(m,n) = f(m-1,n) + f(m,n-1) + Let $f(m,1) = f(1,n) = 1$ for $m \geq 1, n \geq 1,$ and let $f(m,n) = f(m-1,n) + f(m,n-1) + f(m-1,n-1)$ for $m &gt; 1$ and $n &gt; 1.$ Also, let

$$S(n) = \sum_{a+b=n} f(a,b), \text{ for } a \geq 1, b \geq 1.$$

Note: The summation notation means to sum over all positive integers $a,b$ such that $a+b=n.$

Given that

$$S(n+2) = pS(n+1) + qS(n) \text{ for all } n \geq 2,$$

for some constants $p$ and $q$, find $pq.$
We have

\begin{align}
S(n+2) &amp;= \sum_{a + b = n+2} f(a,b)\\
&amp; = \sum_{(a - 1) + (b - 1) = n} f((a - 1)+1, (b - 1) + 1)\\
&amp; = \sum_{a + b = n} f(a+1,b+1)\\
&amp;= \sum_{a + b = n} [f(a,b+1) + f(a+1,b) + f(a,b)]\\
&amp;= \sum_{a + b = n} f(a,b+1) + \sum_{a + b = n} f(a+1,b) + \sum_{a + b = n} f(a,b)\\
&amp;= \sum_{a + (b+1) = n+1} f(a,b+1) + \sum_{(a + 1) + b = n+1} f(a+1,b) + S(n)\\
&amp;= \sum_{a + b = n+1} f(a,b) + \sum_{a + b = n+1} f(a,b) + S(n)\\
&amp;= 2S(n+1) + S(n).
\end{align}

So $p = 2$ and $q = 1$, which implies $pq = 2$.
This was easy, but intimidating. I substituted in my values of $f(m,n)$ int the function, and found all the values of $$S(k) = \sum_{a+b=k} f(a,b), \text{ for } a \geq 1, b \geq 1$$ up to $k=5$, then wrote a system of equations, and solved for $p$ and $q$. Easy