Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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?

share|improve this question
    
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
add comment

2 Answers

up vote 5 down vote accepted

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\} &&&&&&}$$

share|improve this answer
    
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
add comment

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}).

Added (since Brian has given a fuller answer):

  • $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}}.$$

share|improve this answer
    
+1 Loved the idea of breaking into cases that construct the universe of $a_n$! –  MichaelS Oct 14 '11 at 22:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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