# Proving injectivity for an algorithm computing a function between sets of different types of partitions [closed]

I am attempting to solve the following problem:

Let $$A$$ be the set of partitions of $$n$$ with elements $$(a_1, \dots, a_s)$$ such that $$a_i > a_{i+1}+a_{i+2}$$ for all $$i < s,$$ taking $$a_{s+1} = 0.$$ Define $$g_n = F_{n+2}-1$$ and let $$B$$ be the set of partitions of $$n$$ as $$b_1 \ge \dots \ge b_s$$ such that $$b_i \in \{g_n\}$$ for all $$i,$$ and if $$b_1 = g_k$$ for some $$k,$$ then $$g_1, \dots, g_k$$ all appear as some $$b_i.$$ Prove $$|A|=|B|.$$

Attempt: Let $$e_i$$ be the vector with $$1$$ at position $$i$$ and $$0$$ elsewhere. If $$b_1 = g_k,$$ let $$c=(c_k, \dots, c_1)$$ count how many times $$g_i$$ appears. We calculate $$f: B \to A$$ as follows:

Let $$c=(c_k,\dots,c_1), a=(0,\dots,0).$$ While $$c \ne 0,$$ let $$d_1 > \dots > d_k$$ be the indices such that $$c_{d_i} \ne 0.$$ Replace $$c, a$$ with $$c-(e_{d_1}+\dots+e_{d_k}), a+(g_{d_1} e_1 + \dots + g_{d_k} e_k)$$ respectively. After the while loop ends, let $$f(b)=a.$$

Let $$\sum a, \sum b, \sum c$$ be the sum of the components of $$a, b, c$$ respectively. Since $$\sum c$$ decreases after every loop, the algorithm terminates and $$f(b)$$ is well-defined. Since $$c_k g_k + \dots + c_1 g_1 + \sum a$$ does not change after every iteration, is $$\sum b$$ at the start and $$\sum a$$ at the end, we have $$\sum f(b) = \sum b = n,$$ so $$f(b)$$ is also a partition of $$n.$$ Now $$a = (g_k, \dots, g_1)$$ after the first loop, which satisfies the condition $$g_i > g_{i-1}+g_{i-2}$$ since $$g_i = F_{n+2}-1 = (F_{n+1}-1)+(F_n-1)+1 > g_{i-1}+g_{i-2}.$$ Furthermore, after every iteration of the loop, the difference $$a_i – (a_{i-1}+a_{i-2})$$ changes by $$0, g_{d_j}-g_{d_{j-1}} > 0,$$ or $$g_{d_j}-(g_{d_{j-1}}+g_{d_{j-2}}) > 0,$$ so we have $$a_i > a_{i-1} + a_{i-2}$$ at the end and hence $$f(b) \in A.$$ Thus, $$f: B \to A$$ is well-defined.

In order to prove the injectivity of $$f,$$ it suffices to prove each loop iteration as a mapping $$(c,a) \to (c’,a’)$$ is injective, which would imply the mapping $$(c,0) \to (0,a)$$ that the while loop creates is injective. Indeed, if $$f(b_1) = f(b_2) = a$$ with $$(c_1, 0), (c_2, 0)$$ being sent to $$(0, f(b_1)) = (0,a), (0, f(b_2)) = (0,a)$$ respectively, then we have $$(c_1, 0) = (c_2, 0) \Rightarrow c_1 = c_2 \Rightarrow b_1 = b_2.$$

Suppose $$d_1 > \dots > d_i, f_1 > \dots > f_j$$ are the non-zero indices of $$c_1, c_2$$ respectively and $$c_1 – (e_{d_1}+\dots+e_{d_i}) = c_2 – (e_{f_1}+\dots+e_{f_j}), a_1+g_{d_1}e_1 + \dots+ g_{d_i} e_i = a_2 + g_{f_1} e_1 + \dots + g_{f_j} e_j.$$ If $$x \ge 2$$ is an entry of $$c_1,$$ it decreases by $$1,$$ so the corresponding entry in $$c_2$$ after $$c_2$$ is modified is also $$x-1,$$ which means it must’ve been $$(x-1)+1 = x$$ before since $$x-1>0.$$ Thus, if the values of two positions of $$c_1, c_2$$ differ, one is $$1$$ and the other is $$0.$$ However, if $$c_1 = (1,0), a_1 = (3,1), c_2 = (0,1), a_2 = (4,1),$$ then $$(a_1, c_1), (a_2, c_2)$$ both get sent to $$((5,1), (0,0)).$$ I can rule out this specific example by arguing that one of the pairs is illegal and could not have come from any choice of initial $$c,$$ but I have no idea on how to do this in general.

What should I do next in order to show $$f$$ is injective? Furthermore, since the problem I’m trying to prove is correct, injectivity would imply $$f$$ is secretly a bijection. But I have no clue on how to even start on the surjectivity of $$f,$$ so I just constructed a similar algorithm for $$g: A \to B$$ in the hopes of proving $$g$$ is injective too. If I can show $$f$$ is injective I will probably know how to show $$g$$ is.

Here is an example of $$f, g$$ in practice:

Let $$n = 41, b = (12, 7, 7, 4, 4, 2, 2, 2, 1) \Rightarrow c = (1, 2, 2, 3, 1).$$

$$((1, 2, 2, 3, 1), (0,0,0,0,0)) \to ((0, 1, 1, 2, 0), (12, 7, 4, 2, 1)) \to ((0, 0, 0, 1, 0), (19,11,6,2,1)) \to ((21,11,6,2,1),(0,0,0,0,0)),$$ so $$f(b) = (21,11,6,2,1).$$

Let $$a = (21, 11, 6, 2, 1).$$

$$((21,11,6,2,1),(0,0,0,0,0)) \to ((9,4,2,0,0), (1,1,1,1,1)) \to ((2,0,0,0,0),(1,2,2,2,1)) \to ((0,0,0,0,0),(1,2,2,3,1)),$$ so $$g(a) = (12, 7, 7, 4, 4, 2, 2, 2, 1).$$