# Build recurrence relation from a Combinatorial problem

$a_n$ is the number of sub sets of $A=[{-n,...,-1,1,...,n}]$.

The sub sets doesn't contains:

1. Two positive consecutive numbers.
2. Opposite numbers.

Note: $0\notin A$

Build recurrence relation and find initial conditions for $a_n$.

How do I approach this specific question? Is there a step-by-step approach to solve this kind of questions?

-
Be careful, the word subgroup has a meaning in mathematics, you should use "subset". Back to the problem: to find the recurence relation, you should figure what happens if you increase the $n$ by 1... –  N. S. Oct 14 '11 at 19:13
@user9176: Thanks, i've correceted it to sub sets. I'm familiar with the general theory of recurrence relations, and solved some problems, but I can't build a solve pattern, and I'm struggling with this specific question. –  MichaelS Oct 14 '11 at 19:16

I can’t give you a recipe, but I can work this problem in enough detail to show how I’d go about attacking such a problem.

Let $S_n = \{-n,\dots,-1,1,\dots,n\}$; $a_n$ is the number of ‘allowable’ subsets of $S_n$. The basic idea is to try to see what happens when we go from $S_n$ to $S_{n+1}$.

For starters, every allowable subset of $S_n$ is still an allowable subset of $S_{n+1}$; that accounts for $a_n$ allowable subsets of $S_{n+1}$. $S_{n+1}$ also has allowable subsets that contain $-(n+1)$; how many? If $A$ is any allowable subset of $S_n$, then $A\cup\{-(n+1)\}$ is an allowable subset of $S_{n+1}$, and if $A$ is any allowable subset of $S_{n+1}$ that contains $-(n+1)$, then $A\setminus\{-(n+1)\}$ is an allowable subset of $S_n$, so $S_{n+1}$ has $a_n$ allowable subsets that contain $-(n+1)$. Finally, $S_{n+1}$ also has allowable subsets that contain $n+1$ (but not, of course, $-(n+1)$). These are the hardest to count, because we can’t just add $n+1$ to an allowable subset of $S_n$: we can only add $n+1$ to those allowable subsets of $S_n$ that don’t contain $n$.

Temporarily let $b_n$ be the number of allowable subsets of $S_n$ that don’t contain $n$. We’ve just seen that $a_{n+1} = 2a_n+b_n$, so we’ll have the desired recurrence if we can express $b_n$ in terms of $a_n$ and perhaps some other $a_k$’s with $k<n$. Let $A$ be an allowable subset of $S_n$ that doesn’t contain $n$. If $-n\notin A$, then $A$ is actually an allowable subset of $S_{n-1}$. Conversely, every allowable subset of $S_{n-1}$ is an allowable subset of $S_n$ that doesn’t contain $n$, so $S_n$ has $a_{n-1}$ allowable subsets that contain neither $n$ nor $-n$. What if $-n\in A$? Then $A\setminus\{-n\}$ is an allowable subset of $S_{n-1}$. Conversely, if $A$ is an allowable subset of $S_{n-1}$, then $A\cup\{-n\}$ is an allowable subset of $S_n$ that contains $-n$ but not $n$. Thus, there are also $a_{n-1}$ allowable subsets of $S_n$ that contain $-n$ but not $n$. It follows that $b_n = 2a_{n-1}$ and hence that $a_{n+1} = 2a_n +2a_{n-1}$.

This is a second-order recurrence, so for initial conditions we need to specify both $a_1$ and $a_2$. The only forbidden subset of $S_1 = \{-1,1\}$ is $S_1$ itself; the other three subsets, $\{-1\},\{1\}$, and $\varnothing$, are all allowable. Thus, $a_1 = 3$. $S_2 = \{-2,-1,1,2\}$ has $2^4=16$ subsets, of which eight are forbidden: $S_2$ itself, all four of its $3$-element subsets, and the $2$-element subsets $\{-2,2\},\{-1,1\}$, and $\{1,2\}$. Thus, $a_2 = 16 - 8 = 8$.

At this point it’s a good idea to use the recurrence to calculate $a_3 = 2a_2+2a_1=22$ and check it by enumerating the allowable subsets of $S_3 = \{-3,-2,-1,1,2,3\}$ to verify that there are indeed $22$ of them. They are:

$$\matrix{\varnothing & \{-3\} & \{-2\} & \{-1\} & \{1\} & \{2\} & \{3\}\\ \{-3,-2\} & \{-3,-1\} & \{-3,1\} & \{-3,2\} & \{-2,-1\} & \{-2,1\} & \{-2,3\}\\ \{-1,2\} & \{-1,3\} & \{1,3\} & \{-3,-2,-1\} & \{-3,-2,1\} & \{-3,-1,2\} & \{-2,-1,3\}\\ \{-2,1,3\} &&&&&&}$$

-
I think $A\cup\{-(n-1)\}$ should be $A\cup\{-(n+1)\}$? –  joriki Oct 14 '11 at 20:27
@joriki: It should indeed; thanks. –  Brian M. Scott Oct 14 '11 at 20:45
@BrianM.Scott: Very appreciate the excellent answer! Thanks! –  MichaelS Oct 14 '11 at 22:14

Hint:

• Let $b_n$ be the number of subsets of $A_n$ which have $n$ as an element.
• Let $c_n$ be the number of subsets of $A_n$ which have $-n$ as an element.
• Let $d_n$ be the number of subsets of $A_n$ which have neither $n$ nor $-n$ as elements.
• Let $e_n$ be the number of subsets of $A_n$ which have both $n$ and $-n$ as elements.

You should be able to find for example

• $a_n$ in terms of $b_n$, $c_n$, $d_n$ and $e_n$
• $b_n$, $c_n$, $d_n$ and $e_n$ in terms of $b_{n-1}$, $c_{n-1}$, $d_{n-1}$ and $e_{n-1}$

Now eliminate $b,c,d,e$.

Note that you start with $a_0=1$ (the empty set) and $a_1=3$ ({ }, {1}, {-1}).

• $a_n = b_n +c_n + d_n - e_n$
• $e_n = 0$
• $c_n = b_{n-1}+c_{n-1}+ d_{n-1}= a_{n-1}$
• $d_n = b_{n-1}+c_{n-1}+ d_{n-1}= a_{n-1}$
• $b_n = c_{n-1}+ d_{n-1}$
So $a_n=c_{n-1}+ d_{n-1} + a_{n-1} +a_{n-1} -0 = 2a_{n-1}+2a_{n-2}$.
This is OEIS A028859 and has the closed form $$\frac{(1+\sqrt{3})^{n+2}-(1-\sqrt{3})^{n+2}}{4\sqrt{3}}.$$
+1 Loved the idea of breaking into cases that construct the universe of $a_n$! –  MichaelS Oct 14 '11 at 22:17