# parity preserving subsets

A parity-preserving subset $$\{\alpha_1,\cdots, \alpha_k\}$$ of $$\{1,\cdots, n\}$$ satisfies that $$\alpha_i \cong i \mod 2$$ and $$\alpha_i < \alpha_{i+1}\forall i.$$ Let $$p_n$$ be the number of parity-preserving subsets of $$\{1,\cdots, n\}, n\geq 0.$$ Show that $$\sum_{n\geq 0} a_nx^n = \dfrac{1+x}{1-x-x^2}.$$

It might be possible to do this using something called a difference-partial sum bijection, but I'm not sure how to do this. I know that $$a_1 = 2, a_2 = 3, a_3 = 5, a_4 = 8.$$ I know there is a recurrence $$a_n = a_{n-1} + a_{n-2}$$ for $$n\geq 2$$ but I'm not sure how to show it. If I can, though, I can work backwards using the fact that $$a_0 = 1$$ and $$a_n = a_{n-1}+a_{n-2}$$ for $$n\geq 2 \Rightarrow (1-x-x^2)\sum_{n\geq 0} a_nx^n = 1+x.$$ I think proving the recurrence using a bijection between sets of parity-preserving subsets could work, but I'm not sure how to define this bijection.

Edit: $$\emptyset$$ is considered parity-preserving.

• You should say explicitly that $\varnothing$ is counted as parity-preserving; that does not follow from the definition that you gave, but it’s required in order for your values for $a_1,a_2,a_3$, and $a_4$ to be correct. Aug 24 '20 at 4:46

The recurrence $$a_n=a_{n-1}+a_{n-2}$$ can be established as follows. Let $$A_n$$ be the family of parity-preserving subsets of $$\{1,\ldots,n\}$$. We can split $$A_n$$ into two disjoint subsets, $$A_n^-$$ and $$A_n^+$$: $$A_n^-$$ contains the members of $$A_n$$ that do not contain $$n$$, and $$A_n^+$$ contains the members of $$A_n$$ that do contain $$n$$. A little thought shows that $$A_n^-=A_{n-1}$$: the parity-preserving subsets of $$\{1,\ldots,n\}$$ that do not contain $$n$$ are precisely the parity-preserving subsets of $$\{1,\ldots,n-1\}$$. Thus, $$|A_n^-|=a_{n-1}$$, and we’ll be done if we can show that $$|A_n^+|=a_{n-2}$$.
This is the tricky part; there is a bijection between $$A_n^+$$ and $$A_{n-2}$$, but it’s not quite obvious. Start with any member $$S$$ of $$A_{n-2}$$. If the largest element of $$S$$ has the same parity as $$n$$, let $$\widehat S=S\cup\{n-1,n\}$$; otherwise, let $$\widehat S=S\cup\{n\}$$. It’s not hard to check that in both cases $$\widehat S\in A_n^+$$, and it’s also not hard to check that each member of $$A_n^+$$ is $$\widehat S$$ for some $$S\in A_{n-2}$$, so the map $$A_{n-2}\to A_n^+:S\mapsto\widehat S$$ is a bijection, and therefore $$|A_n^+|=a_{n-2}$$, and $$a_n=a_{n-1}+a_{n-2}$$.
• that's okay. Do you have any tips for finding bijections in general? For most combinatorial proofs, I usually consider including and excluding certain elements (e.g. $n$ in $\{1,\cdots, n\}$). Aug 24 '20 at 16:26
• I think I just figured out what the difference-partial sum bijection is. Let $P_n$ be the set of parity-preserving subsets of $\{1,\cdots, n\}$ and $D_n$ be the set of differences of $\{1,\cdots, n\},$ whose elements are the ordered pairs of the differences between consecutive elements that start with the first element of the subset. So basically, say you have a parity-preserving subset $\{\alpha_1,\cdots, \alpha_k\} := \sigma.$ Define $d(\sigma) := (\alpha_1,\alpha_2-\alpha_1,\cdots, \alpha_k - \alpha_{k-1}).$ Aug 24 '20 at 19:19
• Then $d^{-1}(\alpha_1,\alpha_2,\cdots, \alpha_k) = \{\alpha_1, \alpha_1 + \alpha_2,\cdots, \alpha_1 + \alpha_2+\cdots \alpha_k\}.$ In a sense, this is intuitive; differences are used to define $d$ and the inverse is defined in terms of partial or finite sums. Aug 24 '20 at 19:20