I need to build a recursive series to this problem: An = number of subsets of A= {-n,....,-1,1,.....,n} which Do not contain any two positive consecutive numbers and Do not contain שdditive inverse numbers note that 0 does not belong to the group.
as the title says, I need to build a recursive series and starting conditions.
Thanks,
Suppose for strong induction hypothesis that we know how to count $A_k$ for all $k<n$. We wish to count $A_n$ using this information.
Each subset being counted for $A_n$ will fall into exactly one of the following categories
In the first two cases, the subset ignoring $n$ and $-n+1$ will be a valid subset of $\{-n+2,\dots,-1,1,\dots,n-2\}$. By induction hypothesis we know how to count the number of subsets in each case as $A_{n-2}$.
In the second two cases, the subset ignoring $n$ and $-n$ will be a valid subset of $\{-n+1,\dots,-1,1,n-1\}$. By induction hypothesis we know how to count the number of subsets in each case as $A_{n-1}$.
Thus, $A_n = A_{n-1}+A_{n-1}+A_{n-2}+A_{n-2} = 2A_{n-1}+2A_{n-2}$
In order to have enough initial conditions to completely define the series, we will need then two initial values. $A_0=1$ (as $\emptyset$ is a valid subset of $\emptyset$ satisfying the conditions) and $A_1 = 3$ (as $\emptyset,\{-1\},\{1\}$ are all valid subsets of $\{-1,1\}$ satisfying the conditions).
If you do not like zero as a starting point (for some reason some people don't), then $A_2 = 8$ as $\emptyset, \{-2\},\{-1\},\{1\},\{2\},\{-2,-1\},\{-2,1\},\{-1,2\}$ are all valid subsets of $\{-2,-1,1,2\}$. (as an aside, this follows our expected pattern, as $A_2=8=2\cdot 1 + 2\cdot 3=2A_0+2A_1$. We expect, if we brute force a count for $A_3$ that it will be $2\cdot 8 + 2\cdot 3 = 22$)
(If you are looking for nonempty subsets satisfying the conditions, then the above work still applies. Just subtract one to remove the emptyset from the count)
Finding a closed form expression for $\begin{cases} A_n = 2A_{n-1}+2A_{n-2}\\ A_0=1\\ A_1=3\end{cases}$, we look to the characteristic polynomial, $x^2-2x-2=0$ which has roots $1-\sqrt{3}$ and $1+\sqrt{3}$
We expect then that $A_n = c_1(1-\sqrt{3})^n + c_2(1+\sqrt{3})^n$.
By using our initial conditions, we learn then that $1=c_1+c_2$ and $3=c_1(1-\sqrt{3})+c_2(1+\sqrt{3})$. Continuing to solve, we find $c_1=\frac{1}{2}-\frac{1}{\sqrt{3}}$ and $c_2=\frac{1}{2}+\frac{1}{\sqrt{3}}$ giving the final closed form:
$$A_n=(\frac{1}{2}-\frac{1}{\sqrt{3}})(1-\sqrt{3})^n + (\frac{1}{2}+\frac{1}{\sqrt{3}})(1+\sqrt{3})^n$$