## zmudz one year ago 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.

1. anonymous

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$$.

2. anonymous

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}}$$.

3. anonymous

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*}

4. anonymous

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}$

5. anonymous

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.

6. anonymous

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}$

7. anonymous

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

8. Zarkon

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

9. Zarkon

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$