Let g_n equal the number of lists of any length taken from {1,3,4} having elements that sum to n.

Question

For example, g_3 = 2 because the lists are (3) abd (1,1,1). Also g_4 = 4 because the lsits are (4), (3,1), (1,3), and (1,1,1,1). Define g_0 = 1. (a) Find g_1, g_2, and g_5 by complete enumeration. (b) Give a combinatorial proof that g_n = g_(n-1) + g_(n-3) + g_(n-4) for n >= 5, and show that this formula also works when n = 4. (c) Let G(x) be the generating function for {g_n} n>=0. Show that G(x) = 1/(1-x-x^3-x^4)

For part (a), I found through enumeration that g_1 has lists of only (1), g_2 has only one list as well, being (1,1), and g_5 has 6 lists being (1,1,1,1,1), (1,1,3), (1,3,1), (3,1,1), (1,4), and (4,1)

For part (b), I'm not sure where to go and how to actually approach the problem we are trying to present, I know that we show the left hand side and right hand side are equal by showing that they are both exactly equal to each other and solving the problem we have, just not quite sure what exactly I am trying to show.

For part (c) i use the generating function technique to get my G(x) to be equal to 1/(1-x-x^3-x^4).

I am really only stuck with part b here.

Answer 1

To derive the recurrence relation in part (b), suppose you have an arbitrary list whose parts are from $\{1,3,4\}$ and sum to $n$, and consider the three mutually disjoint cases:

• The list begins with 1. Then the rest of the list consists of parts from $\{1,3,4\}$ that sum to $n-1$.
• The list begins with 3. Then the rest of the list consists of parts from $\{1,3,4\}$ that sum to $n-3$.
• The list begins with 4. Then the rest of the list consists of parts from $\{1,3,4\}$ that sum to $n-4$.

We have partitioned the set of lists counted by $g_n$ into three disjoint sets of lists that have counts $g_{n-1}$, $g_{n-3}$, and $g_{n-4}$, respectively.