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 1$ and $n 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.

Question

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 > 1$ and $n > 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.

anonymous · Answer

I bet there's a neat solution that involves working through and possibly solving the first part with the double-index recurrence, but I'll admit I don't know how to work with those. Just working with the $S(n)$ recurrence, I'm getting $pq=2$.

anonymous · Answer

The first thing I did was to identify the first few terms of $S(k)$. For $f(m,n)$, you get this neat table:
$$\begin{array}{cc|ccccc}
&m&1&2&3&4&5&\cdots\
n&\
\hline
1&&\color{red}1&\color{green}1&1&1&1&\cdots\
2&&\color{green}1&\color{blue}3&5&7&9&\cdots\
3&&1&5&13&25&31&\cdots\
4&&1&7&25&63&129&\cdots\
5&&1&9&41&129&258&\cdots\
\vdots&&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots
\end{array}$$
with the pattern being $\color{red}{\text{red}}+\color{green}{\text{green}}+\color{green}{\text{green}}=\color{blue}{\text{blue}}$. $S(k)$ is the sequence given by the sum of the $\color{green}{\text{greens}}$.

anonymous · Answer

So, we have the following recurrence:
$$\begin{cases}S(2)=2\S(3)=5\S(k+2)=pS(k+1)+qS(k)&\text{for }k\ge2\end{cases}$$
Denote the generating function of $S(k)$ by $\sigma(x)$, i.e. $\sigma(x)=\sum\limits_{k\ge2}S(k)x^k$. You can solve for $\sigma(x)$:
$$\begin{align*}
S(k+2)&=pS(k+1)+qS(k)\[1ex]
\sum_{k\ge2}S(k+2)x^k&=p\sum_{k\ge2}S(k+1)x^k+q\sum_{k\ge2}S(k)x^k\[1ex]

\frac{1}{x^2}\sum_{k\ge2}S(k+2)x^{k+2}&=\frac{p}{x}\sum_{k\ge2}S(k+1)x^{k+1}+q\sigma(x)\[1ex]

\frac{1}{x^2}\sum_{k\ge4}S(k)x^k&=\frac{p}{x}\sum_{k\ge3}S(k)x^k+q\sigma(x)\[1ex]

\frac{1}{x^2}\left(\sigma(x)-S(2)x^2-S(3)x^3\right)&=\frac{p}{x}\left(\sigma(x)-S(2)x^2\right)+q\sigma(x)\[1ex]

\sigma(x)&=\frac{(2p-5)x^3-2x^2}{qx^2+px-1}
\end{align*}$$

anonymous · Answer

Finding the Taylor series for $\sigma(x)$ by hand seemed excruciating to me, so I used Mathematica to find the first few terms (about $x=0$):
$$\sigma(x)=2x^2+5x^3+(5p+2q)x^4+(5p^2+5q+2pq)x^5+\mathcal{O}(x^6)$$
So, you have
$$\begin{cases}S(4)=12\S(5)=29\end{cases}~~\implies~~\begin{cases}5p+2q=12\5p^2+5q+2pq=29\end{cases}~~\implies~~\begin{cases}5p+2q=12\12p+5q=29\end{cases}$$

anonymous · Answer

Maybe this is the intended approach... As soon as you can establish the first few terms of $S(k)$, the first half of the problem seems like fluff.

anonymous · Answer

Finding the Taylor series for $\sigma(x)$ by hand seemed excruciating to me, so I used Mathematica to find the first few terms (about $x=0$):
$$\sigma(x)=2x^2+5x^3+(5p+2q)x^4+(5p^2+5q+2pq)x^5+\mathcal{O}(x^6)$$
So, you have
$$\begin{cases}S(4)=12\S(5)=29\end{cases}~~\implies~~\begin{cases}5p+2q=12\5p^2+5q+2pq=29\end{cases}~~\implies~~\begin{cases}5p+2q=12\12p+5q=29\end{cases}$$

anonymous · Answer

Also, using the GF is overkill. You can probably just solve this using the analogue of undetermined coefficients for difference equations.

zarkon · Answer

$$S(n)=\frac{\sqrt{2}}{4}(1+\sqrt{2})^n-\frac{\sqrt{2}}{4}(1-\sqrt{2})n$$

zarkon · Answer

my $n$ on the end fell down  ;)

$$\Large S(n)=\frac{\sqrt{2}}{4}(1+\sqrt{2})^n-\frac{\sqrt{2}}{4}(1-\sqrt{2})^n$$