Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
What have you tried? Don't just machine gun questions at us. –  Alexander Gruber Apr 5 '13 at 5:06

2 Answers 2

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

share|improve this answer
    
(+1) I suspect that it’s over the OP’s head, but it’s a nicely organized explanation of the method that could help someone else a lot. –  Brian M. Scott Apr 5 '13 at 8:47

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

share|improve this answer
    
(+1) for the detailed narrative of guiding the user how to attack this sort of problem. –  achille hui Apr 5 '13 at 8:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.