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.

  • 1
    $\begingroup$ 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. $\endgroup$ 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}$.

  • $\begingroup$ @FredJefferson: You’re welcome. I’ve never seen the term difference-partial sum bijection, so I can’t help with that, I’m afraid. $\endgroup$ Aug 24 '20 at 16:22
  • $\begingroup$ 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\}$). $\endgroup$ Aug 24 '20 at 16:26
  • $\begingroup$ @FredJefferson: I often find it helpful to look at small cases, writing out the sets explicitly, to see whether I can spot any systematic relationship; that’s actually what I did in this case. But a lot of it is just experience: I’ve been doing this for a long time, and by now I often recognize general situations or am reminded of some earlier problem. $\endgroup$ Aug 24 '20 at 16:32
  • $\begingroup$ 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}).$ $\endgroup$ Aug 24 '20 at 19:19
  • $\begingroup$ 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. $\endgroup$ Aug 24 '20 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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