How can I make sure the recurrence relation is correct?

Question

If $A_n$ represents the number of ways to write $n$ as an ordered sum of positive odd integers, then $A_n = A_{n-1} + A_{n-2}$.

For example, $A_2 = 1$ $(1+1)$, $A_3 = 2$ $(1+1+1)$, $(3)$, and $A_4 = 3$ $(1+1+1+1)$, $(1+3)$, $(3+1)$

The $A_{n-1}$ part looks straightforward to me. I just put a "$+1$" after every solution of $A_{n-1}$. But I couldn't understand the $A_{n-2}$ part. I tell myself that for each partition of $A_n$, I look at its rightmost number. If it's $1$, then I take it away, so the rest would correspond to a solution of $A_{n-1}$. And if it's not $1$, I subtract $2$ from that number, which will still remain an odd number, and the numbers would correspond to a solution of $A_{n-2}$. But I just couldn't convince myself. How can I make sure I can get all the solutions with this idea? And why can't I subtract $4$, or $6$ from the rightmost number?

Is there a better (or mathematical) way to look at this recurrence relation?

As an exercise, I changed the question to:

$A_n$ now represents the number of ways to write $n$ as an ordered sum of positive integers, where each summand is at least 2.

I found the recurrence relation was the same as above (but I'm not sure), and I also didn't know how to justify my answer.

I believe the two questions have the same logic behind, please help! Thanks!

Answer 1

Here we put the focus on the main problem: $A_n$ representing the number of ways to write $n$ as ordered sum of odd positive integers follows the recurrence relation \begin{align*} A_n&=A_{n-1}+A_{n-2}\qquad n\geq 3\\ A_1&=1, A_2=1 \end{align*}

First of all you are on the right track. The underlying ideas of your arguments are sound. Yet, the arguments should be reformulated somewhat to clarify the reasoning and to describe the cases more precise. We could argue as follows:

Let $A_n$ represent the number of ways to write $n$ as ordered sum of odd positive integers. There are exactly two possibilities for each of these representations. The right-most term of a representation is either $1$ or an odd value $\geq 3$.

• Right-most term $1$: In this situation we skip this term and obtain a representation of $n-1$ as ordered sum of odd positive integers. On the other hand, whenever we consider a representation of $n-1$ as ordered sum of odd positive integers we can add a term $1$ at the right-most position to obtain a valid representation of $n$.

• Right-most term odd $\geq 3$: In this situation we subtract $2$ from this term and obtain a valid representation of $n-2$. Again, on the other hand, whenever we have a valid representation of $n-2$ we add $2$ to the right-most term to obtain a valid representation of $n$ with right-most odd term $\geq 3$.

• Since there are no other cases left to consider we conclude $$A_n=A_{n-1}+A_{n-2}\qquad n\geq 3$$

Hint: Representations of this type are called compositions.