What the recurrence relation for this problem?

Question

For a positive integer $n$, let $a(n)$ denote the number of ways to write $n$ as an ordered sum of integers where each summand is at least $2$. For example, $6$ can be written $6, 4 + 2, 3 + 3, 2 + 4,\text{and} \ 2 + 2 + 2$, so $a(6) = 5$. Find a recurrence relation for $a(n)$. As always, clearly state for what values of $n$ your recurrence is valid, and give appropriate initial conditions.

Answer 1

Let use use $[t^k]( a_0 + a_1 t^1 + \cdots )$ to denote the operation extracting $a_k$, the coefficient of $t^k$, from a formal power series.

The number of ways to represent $n$ as a sum of numbers $\ge 2$ is given by:

$$\begin{align}a(n) &= \sum_{x_1\ge 2,\,x_1 = n} 1 + \sum_{x_1,x_2\ge 2,\,x_1+x_2=n} 1 + \cdots + \sum_{x_1,\cdots,x_k\ge 2\,x_1+\cdots+x_k=n} 1 + \cdots\\ &= [t^n](t^2 + t^3 + \cdots) + [t^n](t^2 + t^3 + \cdots )^2 + \cdots + [t^n](t^2 + t^3 + \cdots )^k + \cdots\\ &= [t^n]\sum_{k=1}^{\infty} \left(\frac{t^2}{1-t}\right)^k\\ &= [t^n] \frac{\frac{t^2}{1-t}}{1 - \frac{t^2}{1-t}}\\ &= [t^n]\frac{t^2}{1 - t - t^2} \end{align}$$ From this we get:

$$\begin{align} t^2 &= (1 - t - t^2) \sum_{n=0}^{\infty} a(n) t^n\\ &= a(0) + (a(1)-a(0)) t + \sum_{n=2}^{\infty}(a(n)-a(n-1)-a(n-2)) t^n \end{align}$$

which implies:

$$\begin{align} a(0) &= 0\\ a(1) - a(0) &= 0 \implies a(1) = 0\\ a(2) - a(1) - a(0) &= 1 \implies a(2) = 1\\ &\,\vdots\\ a(n) - a(n-1) - a(n-2) &= 0\quad\text{ for }n > 2. \end{align}$$

Compare this with the definition of Fibonacci number, we immedate see $a(n) = F_{n-1}$ for $n > 0$.

Answer 2

It never hurts to gather some data. Clearly $a(0)=a(1)=0$, and $a(2)=1$: the only ‘legal’ decomposition of $2$ is $2$. We can also see that $a(3)=1$, since the only legal decomposition of $3$ is $3$, but $a(4)=2$, since we can write $4=4$ or $4=2+2$. You’ve been given $a(6)=5$, and $5=5=3+2=2+3$, so $a(5)=3$. That’s still a bit skimpy, so we’ll do one more: $7$ can be written $7=5+2=4+3=3+4=2+5=3+2+2=2+3+2=2+2+3$, so $a(7)=8$. It often helps to organize the data in tabular form:

$$\begin{array}{rcc} n:&0&1&2&3&4&5&6&7\\ a(n):&0&0&1&1&2&3&5&8 \end{array}$$

That’s still pretty minimal, but with a little luck you might recognize the Fibonacci numbers on the bottom line, or at least recognize that we seem to have $a(n)=a(n-1)+a(n-2)$ for $n\ge 3$. It wouldn’t hurt to try to count the legal decompositions of $8$ to verify that there are $5+8=13$ of them:

$$\begin{align*} &8=6+2=5+3=4+4=3+5=2+6=\\ &4+2+2=2+4+2=2+2+4=\\ &3+3+2=3+2+3=2+3+3=\\ &2+2+2+2\;. \end{align*}$$

At this point we can strongly suspect that the desired recurrence is $$a(n)=a(n-1)+a(n-2)\;,\tag{1}$$ valid for $n\ge 3$, but that conjecture still has to be justified. At this point you should ask yourself: Is there some natural way to build decompositions of $n$ from decompositions of $n-1$ and of $n-2$, much as we built stacks of chips from smaller stacks in the other problem?

You could start by taking the data for $n=6,7$, and $8$ and trying to match up the $13$ decompositions of $8$ with the $8$ decompositions of $7$ and the $5$ decompositions of $6$ in some systematic way. I’ve done that below; see if you can find the pattern and then generalize it to explain why the recurrence $(1)$ must hold for $n\ge 3$.

$$\begin{array}{|l|l|l|} \hline 8&7\\ \hline 6+2&&6\\ \hline 5+3&5+2\\ \hline 4+4&4+3\\ \hline 3+5&3+4\\ \hline 2+6&2+5\\ \hline 4+2+2&&4+2\\ \hline 2+4+2&&2+4\\ \hline 2+2+4&2+2+3\\ \hline 3+3+2&&3+3\\ \hline 3+2+3&3+2+2\\ \hline 2+3+3&2+3+2\\ \hline 2+2+2+2&&2+2+2\\ \hline \end{array}$$